Булевы выражения

Импликация

Идемпотентность (отсутствие степеней коэффициентов)

6.Закон двойного отрицания (инволюционный закон):

Х = Х

7. Свойства констант 0 и 1:

X * 1 = X;	X v 1 = 1;
X * 0 = 0;	X v 0 = X;
0 = 1;	1 = 0;

8. Закон де Моргана:

Х1*Х2 = Х1 v Х2;

Х1 v Х2 = Х1 * Х2;

9.Закон противоречия:

Х*Х = 0

10.Закон исключения третьего:

Х v Х = 1

11. Поглощение:

Х v X*Y = X

12. Склеивание:

X*Y v X*Y = X;

Х v X*Y = X v Y

А®В = А v B

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

Одна и та же логическая функция может быть записана различным образом. Например, функция F(x1, x2) может быть записана следующими эквивалентными выражениями:

Эквивалентность выражений легко проверить подстановкой в них значений х1 и х2, или с помощью логических преобразований. Для исключения неоднозначности записи логические функции представляют в унифицированных формах. Такими формами являются дизъюнктивная и конъюнктивная. В них используются элементарные дизъюнкции и конъюнкции.

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

Например,

.

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

Например,

.

В элементарные дизъюнкции и конъюнкции не могут входить одинаковые переменные, а так же переменные с их отрицаниями. Такие дизъюнкции и конъюнкции должны преобразовываться. При этом они упрощаются или обращаются в 0 или 1.

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

Дизъюнктивная нормальная форма (ДНФ) – это форма, в которой логическая функция представляется в виде дизъюнкции элементарных конъюнкций.

Например,

Конъюнктивной нормальной формой (КНФ) – называется такая форма, в которой логическая функция представляется в виде конъюнкции элементарных дизъюнкций.

Например,

.

И все же, использование нормальных форм не устраняет полностью неоднозначности записи логических функций.

Например,

Может быть записана так:

Среди нормальных форм выделяют такие, в которых функции записываются единственным образом. Их называют совершенными. Применяются совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Они имею две отличительные особенности:

1. все элементарные конъюнкции и дизъюнкции имеют одинаковый ранг;

2. в элементарные конъюнкцииили дизъюнкции входят все те переменные или их отрицания, от которых зависит функция.