2.3. Понятие формулы и свойства операций

Как и в элементарной алгебре, в математической логике из элементарных операций можно строить формулы.

Например, x₁  x₂   x₁  x₂ — формула.

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

Две различные формулы называются эквивалентными, если соответствующие им функции равны.

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

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

Обозначим x₁  x₂ любую из операций ,  или . Существенно только, чтобы символ «» имел в тождестве везде один и тот же смысл. В этом случае непосредственно проверяется, что имеют место свойства 1) и 2):

1) ассоциативность

((x₁  x₂)  x₃) = (x₁  ( x₂  x₃));

2) коммутативность

(x₁  x₂) = (x₂  x₁);

Для дизъюнкции и конъюнкции также выполняются дистрибутивные законы:

((x₁  x₂)  x₃) = (x₁  x₃)  ( x₂  x₃));

((x₁  x₂)  x₃) = (x₁  x₃)  ( x₂  x₃));

Имеет место закон двойного отрицания

x = x.

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

Законы де Моргана:

(x₁  x₂ ) = ( x₁  x₂) ;

(x₁  x₂ ) = (  x₁ x₂).

Законы идемпотентности:

x  x = x ; x  x = x.

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

x  0 = x ; x  1 = 1;

x  0 = 0; x  1 = x.

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

x  x = 1.

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

x  x = 0.

Закон силлогизма

( ( x  у)  (у  z))  (x  z).

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

2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.

Рассмотрим разложения булевых функций по дизъюнктивным и конъюнктивным наборам переменных.

Введем обозначения

x^σ = x ∙   x ∙,

где  — параметр, равный либо 0, либо 1 и используется обычное умножение. Очевидно, что

x при  = 0,

x^ =

x при  = 1.

Такое представление выражает следующий факт: x^ = 1 тогда и только тогда, когда x = .

Введем также следующие обозначения:

_{(i1.i2….in)} x_i = x₁  x₂ … x_n;

&_{(i1,i2,…in)} x_i = x₁ & x₂ &… &x_n.

Теорема 2.1 Каждую функцию математической логики можно представить в виде

F(x₁, x₂, …,x_n) = _{(1, 2,…,n)} x₁^1 & x₂^2 &… & x_n^n &

& F(₁, ₂, …, _n), (2.1)

где дизъюнкция берется по всевозможным наборам значений переменных x₁, x₂, …, x_n.

Доказательство. Рассмотрим произвольный набор значений ₁, ₂, …, _n и покажем, что левые и правые части (2.1) принимают на нем и только на нем одно и тоже значение. Левая часть (2.1) дает F(₁, ₂, …, _n). Соответственно правая :

_{(1,2,…,n)} ₁^1 & ₂^2 &… & _n^n & F(₁, ₂,…, _n).

Конъюнкция ₁^1 & ₂^2 &… & _n^n = 1 тогда и только тогда, когда ₁ = ₁, ₂ = ₂, …,_n = _n. Следовательно, на этом и только на этом наборе ₁, ₂,…, _n имеет место тождество

₁^1& ₂^2 &…& ₂^n & F(₁, ₂, …, _n) = F(₁, ₂, …, _n).

При этом остальные дизъюнктивные члены в (2.1) обращаются в нуль.

Разложение (2.1) называется совершенной дизъюнктивной нормальной формой (С.Д.Н.Ф.), если оно берется по всем наборам ₁, ₂, …,_{n ,} для которых выполнено

F(₁, ₂, …,_n) = 1.

В силу этого определения С.Д.Н.Ф. записывается в виде

F(x₁, x₂, …, x_n) = _{(1, 2,…, n)} x₁^1 &x₂ ^2 & … & x_n^n.

Функция [F(x₁, x₂, …, x_n)]^*, равная F(x₁, x₂, …, x_n) называется двойственнной функцией по отношению к функции F(x₁, x₂, …, x_n).

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

Таблица 2.3 — Пример двойственной функции

x1	x2	F(x1,x2)	x1	x2	[F(x1,x2)]^*
0	0	1	1	1	0
0	1	0	1	0	0
1	0	1	0	1	1
1	1	1	0	0	0

Очевидно, если вернуться к старому набору переменных, то получим

[F(x₁, x₂, …, x_n)]* = F^* (x₁, x₂, …, x_n).

Из определения двойственности следует, что

F^** = (F^*)^* = F.

Обозначим через x₁, x₂, …, x_n все различные символы переменных, встречающиеся в множествах

(x₁₁, x₂₁, …, x_n1), (x₁₂, x₂₂, …, x_n2), …, (x_1m, x_2m, …, x_nm).

Следующая теорема определяет принцип двойственности для булевых функций.

Теорема 2.2 Если

Φ(x₁, x₂, …, x_n) = F(F₁(x₁₁, x₂₁, …, x_n1), F₂(x₁₂, x₂₂, …, x_n2), …, F_m(x_1m, x_2m, …, x_nm)),

то Φ^*(x₁, x₂, …, x_n) =F^*( F^*₁(x₁, x₂, …, x_n), F^*₂(x₁₂, x₂₂, …, x_n2), …, F^*_m(x_1m, x_2m, …, x_nm)).

Доказательство.

Φ^*(x₁, x₂, …, x_n) = Φ(x₁, x₂, …, x_n) =

= F(f₁(x₁₁, x₂₁, …, x_n1),F₂(x₁₂, x₂₂, …, x_n2), …,F_m(x_1m, x_2m, …, x_nm)) =

= F(F₁^*(x₁₁, x₂₁, …, x_n1), F₂^*(x₁₂, x₂₂, …, x_n2), …, F_m^* (x_1m, x_2m, …, x_nm)) =

= F^*(F^*₁(x₁, x₂, …, x_n), F^*₂(x₁₂, x₂₂, …, x_n2), …, F^*_m(x_1m, x_2m, …, x_nm)),

что и требовалось.

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

Непосредственно проверяется, что:

• Функция x двойственна x;

• Функция x двойственна x.;

• Функция 0 двойственна1;

• Функция 1 двойственна 0;

• Функция x₁  x₂ двойственна x₁ & x₂;

• Функция x₁ & x₂ двойственна x₁  x₂ ;

Рассмотрим примеры.

F(x_1, x₂) = x₁ & x₂  x₁ & x₂ ; F*(x_1, x₂) = x₁  x₂ & x₁  x₂ ;

F(x_1, x₂) = (x₁ & x₂) ; F^*(x_1, x₂) = x₁  x₂;

F(x_1, x₂) = (x₁  x₂) ; F^*(x_1, x₂) = x₁ & x₂;

Используя принцип двойственности, можно записать выражение, двойственное С.Д.Н.Ф., в свою очередь, полученной к двойственной функции F^* (x₁, x₂, …, x_n). Такое выражение получило название С.К.Н.Ф. — совершенной конъюнктивной нормальной формы. Рассмотрим его подробнее.

По определению С.Д.Н.Ф. имеем

F^* (x₁, x₂, …, x_n) = _{(1, 2,…, n)} x₁^1 & x₂ ^2 & … & x_n^n.

Применим к этой функции принцип двойственности:

F^**(x₁, x₂, …, x_n) = &_{(1, 2,…, n)} x₁^1  x₂ ^2  … x_n^n.

Левая часть есть F(x₁, x₂, …, x_n), а правую можно преобразовать, учитывая, что конъюнкции берутся по всем наборам значений переменных, для которых F^*(₁, ₂, …, _n) = 1. Легко заметить, что значения F(x₁, x₂, …, x_n) не изменятся, если взять соответ­ствующие конъюнкции по таким наборам значений переменных, для которых, в силу принципа двойственности, F(₁, ₂, …, _n) = 0. Заменяя в этом выражении ₁ на 1 и выполнив обратную замену во всех дизъюнкциях, окончательно получим

F(x₁, x₂, …, x_n) = &_{(1, 2,…, n)} x₁^1  x₂ ^2  … x_n^n,

где дизъюнкции берутся по всем тем наборам значений переменных, для которых F(₁, ₂, …, _n) = 0.

Пример. Построить С.К.Н.Ф. для функции x₁ → x₂.

Имеем x₁ → x₂ = x₁^1 x₂^0 = ^x₁  x₂.