Функции алгебры логики (булевы функции)
Таблица 1.5.1 – Значения булевых функций
№ п/п | Значения булевых функций в зависимости от значений аргументов x и y | Обозначение функции | Название функции | ||||
x | |||||||
y | |||||||
F0(x, y) | Константа ноль | ||||||
F1(x, y) | Конъюнкция, логическое умножение, И, &, AND | ||||||
F2(x, y) | Запрет по x, отрицание импликации | ||||||
F3(x, y) | Переменная x | ||||||
F4(x, y) | Запрет по y, отрицание импликации | ||||||
F5(x, y) | Переменная y | ||||||
F6(x, y) | Сумма по модулю 2, логическая неравнозначность, М2, XOR | ||||||
F7(x, y) | Дизъюнкция, логическое сложение, ИЛИ, OR | ||||||
F8(x, y) | Стрелка Пирса, отрицание дизъюнкции, ИЛИ-НЕ, NOT OR | ||||||
F9(x, y) | Эквивалентность | ||||||
F10(x, y) | Отрицание, инверсия y, НЕ, NOT | ||||||
F11(x, y) | Импликация от y к x | ||||||
F12(x, y) | Отрицание, инверсия x, НЕ, NOT | ||||||
F13(x, y) | Импликация от x к y | ||||||
F14(x, y) | Штрих Шеффера, отрицание конъюнкции, И-НЕ, NOT AND | ||||||
F15(x, y) | Константа единица |
Основные законы алгебры логики
1) Законы нулевого множества:
, , ,
т.е. конъюнкция любого числа переменных обращается в ноль, если хотя бы одна переменная имеет значение 0, независимо от значений других переменных.
2) Законы универсального множества:
, , ,
т.е. дизъюнкция любого числа переменных обращается в единицу, если хотя бы одна переменная имеет значение 1, независимо от значений других переменных.
3) Законы идемпотентности (повторения, тавтологии):
, .
4) Закон двойной инверсии:
, т.е. двойную инверсию можно снять.
5) Законы дополнительности:
· закон логического противоречия
, т.е. конъюнкция любой переменной и ее инверсии есть 0;
· закон исключенного третьего
, т.е. дизъюнкция любой переменной и ее инверсии есть 0.
6) Коммутативные законы (законы перемещения):
,
т.е. результаты выполнения операции конъюнкции и дизъюнкции не зависят от того, в каком порядке следуют переменные.
7) Ассоциативные законы (законы сочетания):
,
т.е. для записи конъюнкции или дизъюнкции скобки можно опустить.
8) Дистрибутивные законы (законы распределения):
· конъюнкции относительно дизъюнкции:
;
· дизъюнкции относительно конъюнкции:
.
9) Законы поглощения:
, .
10) Законы склеивания (распространения):
, .
11) Законы де Моргана (законы инверсии):
· для двух переменных:
, т.е. инверсия конъюнкции есть дизъюнкция инверсий;
, т.е. инверсия дизъюнкции есть конъюнкция инверсий;
· в общем виде:
или ,
т.е. инверсия функции есть функция от инверсий её аргументов и операций дизъюнкции и конъюнкции.