Булевы функции - раздел Математика, Курс лекций: Элементы дискретной математики 1. Булевы Функции Одной Переменной. Будем, Как Обычно, Обозн...
1. Булевы функции одной переменной. Будем, как обычно, обозначать независимую переменную символом х. Если независимых переменных несколько, будем их нумеровать: х1,х2, ..., х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-элементного множества на 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
Высказывания
1. Понятие высказывания. Предложение, о котором имеет смысл говорить, что оно истинно или ложно, называется высказыванием.
Высказываниями являются, например, следующие предложения:
Новости и инфо для студентов