Математика \ Дискретная математика

Булевы функции. Основные формулы булевой алгебры. Аналитическая запись булевых функций в булевом базисе. Дешифраторы. Мультиплексоры, страница 2

- штрих Шеффера (И-НЕ). Если хотя бы один аргумент равен 0, то функция равна 1. Функция равна 0, если все аргументы равны 1;

- дизъюнкция (ИЛИ). Если хотя бы один аргумент равен 1, то функция равна 1. Функция равна 0, если все аргументы равны 0;

- стрелка Пирса (ИЛИ-НЕ). Если хотя бы один аргумент равен 1, то функция равна 0. Функция равна 1, если все аргументы равны 0.

Вопрос: Нужно ли помнить таблицы истинности?

Ответ: смотря какие. За незнание таблиц истинности функций: константа ноль, константа единицы, аргумент , инверсия аргумента , сумма по модулю два, а также функций «И», «ИЛИ», «И-НЕ» (функция Шеффера), «ИЛИ-НЕ» (функция Пирса) любого числа аргументов я торжественно расстреливаю злодеев из рогатки железными гайками перед строем, а после этого еще топчу тела ногами.

Основные формулы булевой алгебры

Для доказательства формул можно пользоваться табличным методом. При его использовании строятся таблицы истинности для левой и правой частей доказываемого соотношения. Если эти таблицы совпадают, то имеет место тождество.

Свойства конъюнкции, дизъюнкции и отрицания.

, ,

, .

Для последнего соотношения нет аналога в обычной алгебре , но в булевой алгебре это тождество. Проверим его справедливость табличным методом:


0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

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

Существование последних двух тождеств (распределительных законов) делает законы булевой алгебры полностью двойственными. Это означает, что если существует какое–либо равенство, то существует и второе равенство, в котором символы дизъюнкции заменены символами конъюнкции, а символы конъюнкции – символами дизъюнкции.

Пример. Справедливо равенство , в силу свойства двойственности справедливо и равенство . Эти тождества называются соотношениями Блека – Порецкого.