Булевы функции двух переменных. - раздел Математика, Курс лекций: Элементы дискретной математики ...
Пусть х1и х2 — логические переменные. Рассмотрим функцию от х, и х2:
f(х1,х2). (11.8)
Так как каждая из переменных х1, х2 может принимать только два значения: 0 и 1,
то областью определения функции (11.8) являются четыре варианта сочетаний: 00, 01, 10 и 11. Приняв эти сочетания за координаты точек на плоскости х1Ох2, получим четыре вершины единичного квадрата (рис. 11.10). Таким образом, функцию (11.8) можем считать заданной на множестве вершин единичного квадрата, и это множество она отображает во множество {0, 1}. Например, функция f(х1, х2) может быть равна единице во всех вершинах, кроме начала координат, а в начале координат обращаться в нуль.
Легко найти общее число всевозможных функций f(хь х2) со значениями в 0, 1}. В самом деле, перенумеруем вершины единичного квадрата в каком-нибудь порядке. В каждой вершине функция f(х1,, х2) может принимать одно из двух значений: 0 или 1. Задать функцию — значит указать, в каких вершинах она принимает значение 0 и в каких 1. Таким образом, наша функция — это четырехбуквенное слово, образованное из алфавита {0, 1}. Число таких слов равно 24= 16. Следовательно, можно построить только 16 различных функций двух логических переменных со значениями в {0, 1}. Перечислим эти функции.
Таблица 11.11
Таблица 11.12
х1
х2
f(х1,х2)=0
х1
х2
f(х1,х2)=1
Таблица 11.13
Таблица 11.14
х1
х2
f(х1,х2)= х1
х1
х2
f(х1,х2)= х2
Таблица 11.15
Таблица 11.16
х1
х2
f(х1,х2)=
х1
х2
f(х1,х2)=
Таблица 11.17
Таблица 11.18
х1
х2
х1 Ùх2
х1
х2
х1Úх2
Прежде всего отметим две простейшие функции — постоянные: f(х1,х2)=0 и f(х1,х2)= 1 (табл. 11.11 и 11.12).
Еще две тоже очень простые функции f(х1,х2)= х1и f(х1,х2)= х2 (табл. 11.13 и 11.14). Аналогично строятся функции f(х1,х2)= , и f(х1,х2)= (табл. 11.15 и 11.16).
Все эти функции уже встречались при рассмотрении функции одной логической переменной. Перейдем теперь к более интересным функциям двух логических переменных.
Конъюнкция.Так называется функция f(х1,х2), которая принимает значение, равное единице, тогда и только тогда, когда оба аргумента равны 1 (табл. 11.17). Конъюнкция обозначается х1Ùх2 или х1 ,х2, читается «х1 и х2» (Иногда конъюнкцию обозначают знаком &. До сих пор не установилось единое обозначение и для других функций. Так, например, для отрицания существуют еще два знака). Легко видеть, что конъюнкцию можно определить также равенством х1Ùх2 = min(х1|, х2). Таким образом, чтобы конъюнкция была равна нулю, необходимо (и достаточно), чтобы хоть один аргумент был равен нулю.
Дизъюнкция. Так называется функция f(х1,х2), которая принимает значение 0 тогда и только тогда, когда оба аргумента равны 0 (табл. 11.18). Дизъюнкция обозначается х1Úх2, и читается «х1 или х2». Легко видеть, что дизъюнкцию можно определить равенством х1Úх2, = mах(х1, х2). Таким образом, чтобы дизъюнкция была равна единице, достаточно (и необходимо), чтобы хоть один из аргументов был равен единице.
Рис... Если 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. Понятие высказывания. Предложение, о котором имеет смысл говорить, что оно истинно или ложно, называется высказыванием.
Высказываниями являются, например, следующие предложения:
Булевы функции
1. Булевы функции одной переменной. Будем, как обычно, обозначать независимую переменную символом х. Если независимых переменных несколько, будем их нумеровать: х1
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов