Функции алгебры логики (булевы функции)

Таблица 1.5.1 – Значения булевых функций

№ п/п Значения булевых функций в зависимости от значений аргументов x и y Обозначение функции Название функции
  x    
  y    
F0(x, y) Константа ноль
F1(x, y) Функции алгебры логики (булевы функции) - student2.ru Конъюнкция, логическое умножение, И, &, AND
F2(x, y) Функции алгебры логики (булевы функции) - student2.ru Запрет по x, отрицание импликации
F3(x, y) Функции алгебры логики (булевы функции) - student2.ru Переменная x
F4(x, y) Функции алгебры логики (булевы функции) - student2.ru Запрет по y, отрицание импликации
F5(x, y) Функции алгебры логики (булевы функции) - student2.ru Переменная y
F6(x, y) Функции алгебры логики (булевы функции) - student2.ru Сумма по модулю 2, логическая неравнозначность, М2, XOR
F7(x, y) Функции алгебры логики (булевы функции) - student2.ru Дизъюнкция, логическое сложение, ИЛИ, OR
F8(x, y) Функции алгебры логики (булевы функции) - student2.ru Стрелка Пирса, отрицание дизъюнкции, ИЛИ-НЕ, NOT OR
F9(x, y) Функции алгебры логики (булевы функции) - student2.ru Эквивалентность
F10(x, y) Функции алгебры логики (булевы функции) - student2.ru Отрицание, инверсия y, НЕ, NOT
F11(x, y) Функции алгебры логики (булевы функции) - student2.ru Импликация от y к x
F12(x, y) Функции алгебры логики (булевы функции) - student2.ru Отрицание, инверсия x, НЕ, NOT
F13(x, y) Функции алгебры логики (булевы функции) - student2.ru Импликация от x к y
F14(x, y) Функции алгебры логики (булевы функции) - student2.ru Штрих Шеффера, отрицание конъюнкции, И-НЕ, NOT AND
F15(x, y) Константа единица

Основные законы алгебры логики

1) Законы нулевого множества:

Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru ,

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

2) Законы универсального множества:

Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru ,

т.е. дизъюнкция любого числа переменных обращается в единицу, если хотя бы одна переменная имеет значение 1, независимо от значений других переменных.

3) Законы идемпотентности (повторения, тавтологии):

Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru .

4) Закон двойной инверсии:

Функции алгебры логики (булевы функции) - student2.ru , т.е. двойную инверсию можно снять.

5) Законы дополнительности:

· закон логического противоречия

Функции алгебры логики (булевы функции) - student2.ru , т.е. конъюнкция любой переменной и ее инверсии есть 0;

· закон исключенного третьего

Функции алгебры логики (булевы функции) - student2.ru , т.е. дизъюнкция любой переменной и ее инверсии есть 0.

6) Коммутативные законы (законы перемещения):

Функции алгебры логики (булевы функции) - student2.ru ,

т.е. результаты выполнения операции конъюнкции и дизъюнкции не зависят от того, в каком порядке следуют переменные.

7) Ассоциативные законы (законы сочетания):

Функции алгебры логики (булевы функции) - student2.ru ,

т.е. для записи конъюнкции или дизъюнкции скобки можно опустить.

8) Дистрибутивные законы (законы распределения):

· конъюнкции относительно дизъюнкции:

Функции алгебры логики (булевы функции) - student2.ru ;

· дизъюнкции относительно конъюнкции:

Функции алгебры логики (булевы функции) - student2.ru .

9) Законы поглощения:

Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru .

10) Законы склеивания (распространения):

Функции алгебры логики (булевы функции) - student2.ru , Функции алгебры логики (булевы функции) - student2.ru .

11) Законы де Моргана (законы инверсии):

· для двух переменных:

Функции алгебры логики (булевы функции) - student2.ru , т.е. инверсия конъюнкции есть дизъюнкция инверсий;

Функции алгебры логики (булевы функции) - student2.ru , т.е. инверсия дизъюнкции есть конъюнкция инверсий;

· в общем виде:

Функции алгебры логики (булевы функции) - student2.ru или Функции алгебры логики (булевы функции) - student2.ru ,

т.е. инверсия функции есть функция от инверсий её аргументов и операций дизъюнкции и конъюнкции.

Наши рекомендации