рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Булевы функции

Булевы функции - раздел Математика, Курс лекций: Элементы дискретной математики 1. Булевы Функции Одной Переменной. Будем, Как Обычно, Обозн...

1. Булевы функции одной переменной. Будем, как обычно, обозначать независимую переменную символом х. Если независимых переменных несколько, будем их нумеровать: х12, ..., хn.

Рассмотрим возможные функции от переменной х ÎD = {0, 1} (такая переменная называется логической переменной). При этом нас будут интересовать лишь те функции, значения которых лежат также в D= {0, 1}. Таких функций не много. В самом деле, можно указать, например, степенную функцию: f(х) = хn. Но эта функция в данном случае ничем не отличается от тождественной функции f(х) = х, так как значение 0 она переводит в 0, а значение 1 в 1. Построим таблицу функции f(х) = х (табл. 11.7), для чего слева перечислим значения аргумента (0 и 1), а справа — соответствующие значения функции.

Другой более интересной функцией является отрицание. Эта функция обозначается х и читается «не х». Она действует следу­ющим образом: если х = 0, то = 1, и наоборот, если х = 1, то = 0 (табл. 11.8).

Таблица 11.7   Таблица 11.8   Таблица 11.9   Таблица 11.10
x f(х) = х   х f(х) = x f(х) = 1   х f(х) = 0
     
     

Кроме этих двух функций можно указать еще только две функции, отображающие множество {0, 1} в себя. Это постоянные f(х) = 1 и f(х) = 0 (табл. 11.9 и 11.10).

Других функций от одной логической переменной, отображающих {0, 1} в себя, не существует. В самом деле, любая такая функция определяется двумя значениями (f (0) и f (1)), причем каждое из этих значений может быть равно либо 0, либо 1. Таким образом, каждая такая функция — это двухбуквенное слово f (0) f (1), образованное из {0, 1}, как из алфавита. Число таких слов, а следовательно, и число интересующих нас функций, равно, как мы знаем, 22 = 4. Ровно столько функций мы и перечислили, а все возможные двухбуквенные слова, которые можно образовать из {0, 1}, записаны в правых частях таблиц (см. табл. 11.7—11.10).

Итак, если x: — логическая переменная, то существует только четыре функции f(х), отображающие область определения D = {0, 1} в себя: две постоянные, одна тождественная и одна — отрицание. Эти функции называют булевыми функциями одного переменного (Джон Буль (1815— 1864) — английский ученый.. Каждую из этих функций можно задать аналитически, т.е. с помощью формул, например f(х) = х, или таблично.

Заметим еще, что так же, как в непрерывном анализе, одну и ту же функцию можно задать с помощью разных формул. Например, функциюf(х) = 0 можно задать и формулой f(х) =.

Имея всего четыре функции, трудно построить исчисление, столь же содержательное, как анализ непрерывных функций. Перейдем поэтому к изучению функций, зависящих от нескольких логических переменных, значения которых лежат в D = {0, 1}. Такие функции называют булевыми функциями нескольких переменных. В этом случае также получим конечное множество функций, но запас их достаточно велик, чтобы построить содержательный математический аппарат.

– Конец работы –

Эта тема принадлежит разделу:

Курс лекций: Элементы дискретной математики

Рис... Если A Igrave В то разность А В называется дополнением множества А до... U А Egrave В Говорят при этом что множество U разбито на два множества на А и Аналогичному разбиению можно подвергнуть множество А или множество или то и...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Булевы функции

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Элементы дискретной математики
Здесь рассмотрены начальные понятия дискретной или конечной математики, т. е. математики, не связанной с понятиями бесконечности, предела и непрерывности. Дискретная математика имеет широкий спектр

Лекция 1. Начала теории множеств.
Цель: Изучить основные понятия теории множеств. План: 1. Понятие множества 2. Операции над множествами. 3. Отображения множеств. 3. Вопросы для контроля

Лекция 2. Комбинаторика
Цель: Изучить основные понятия комбинаторики План: 1. Метод математической индукции. 2. Перестановки 3. Размещения 4. Сочетания 5. Разбиения

Два правила перечисления в комбинаторике
В комбинаторике существует два правила, облегчающих перечисления. Это правило суммы и правило произведения. Аналогичные правила есть и в теории вероятностей. Правило суммы

Комбинаторные задачи
1. Сколько есть вариантов расстановки 6 различных книг на полке? 2. Сколько есть вариантов 6-значных чисел, содержащих цифры 1,1,1,3,3,5? 3. Сколько есть вариантов из 3 команд, за

Перестановки без повторений
Перестановками без повторений или просто перестановками из элементов п различных типов называются их последовательности, отличающиеся друг от друга только порядком входящих в н

Перестановки с повторениями
Перестановками с повторениями из т элементов n различных типов, среди которых k1 одинаковых элементов 1-го типа, k2 одинаковых

Размещения без повторений
Размещениями без повторений или просто размещениями элементов n различных типов по m называются их последовательности из m различных элементов, отличающиеся друг

Размещения с повторениями
Размещениями с повторениями элементов n различных типов по т называются их последовательности из т элементов, отличающиеся друг от друга самими элементами или

Сочетания без повторений
Сочетаниями без повторений или просто сочетаниями элементов n различных типов по т называются их неупорядоченные наборы из m различных элементов, отличающиеся дру

Сочетания с повторениями
Сочетаниями с повторениями элементов n различных типов по т называются их неупорядоченные наборы из т элементов, отличающиеся друг от друга только самими элементами.

Сочетания с повторениями и ограничением на встречаемость элементов каждого типа
Отдельным случаем являются сочетания с повторениями элементов п различных типов по т элементов, когда элемент каждого типа должен встречаться в каждом сочетании по кр

А. Неупорядоченные разбиения с фиксированными размерами частей
Неупорядоченное разбиениеn -элементного множества X — это любое семейство {X1, X2,…, Xk}, где 1≤k≤

Числа Стирлинга второго рода
Число разбиений n-элементного множества на k блоков произвольного размера (на k непустых подмножеств) выражается числом Стирлинга второго рода S(n, k) (

Доказательство.
Разобьем все множество разбиений на два класса. В первый поместим разбиения, в которых последний элемент входит в отдельный блок, таких разбиений будет S(n – 1, k – 1), во втор

I. Определения.
А. Для чисел Стирлинга второго рода — символ .

Неупорядоченные разбиения (все)
I. Определения. А. р(п) — число разбиений целого числа n на целые слагаемые независимо от их порядка. Например, 5=1+4=2+3=1+1+3=1+2+ + 2 = 1 + 1 + 1 + 2 = 1 + I + 1

Биномиальные коэффициенты (числа сочетаний без повторений )
I. Определения. А. или

Числа разбиений с фиксированными частями
I. Определения. А. - или E(n; m1, m2,

Вопросы для контроля знаний и подведения итога прочитанной лекции
1. В чем суть метода математической индукции? 2. В чем состоят два основных правила перечисления в комбинаторике? 2. Что называют перестановкой без повторений? 3. Что наз

Высказывания
1. Понятие высказывания. Предложение, о котором имеет смысл говорить, что оно истинно или ложно, называется высказыванием. Высказываниями являются, например, следующие предложения:

Булевы функции двух переменных.
Пусть х1 и х2 — логические переменные. Рассмотрим функцию от х, и

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги