Правило равносильных преобразований

Пусть для формул A и B справедливо утверждение A º B. Пусть C_A – формула, содержащая A в качестве своей подформулы. Пусть C_B получается из C_A заменой A на B. Тогда C_A º C_B.

Пример 4.5.

Пусть A = x É y, B = Ø x V y.

Равносильность 12 позволяет утверждать, что A º B.

Пусть C_A = (x É y) & z, т.е. A есть подформула C_A. Тогда C_B = (Ø x V y) & z и C_A º C_B, т.е. (x É y) & z º (Ø x V y) & z.

Двойственность. Принцип двойственности.

Символы &, V называются двойственными.

Формула А^* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, V на двойственные.

Например,

A = x V(y &Ø z);

A ^* = x & (y VØ z).

Теорема 4.1. (Принцип двойственности).

Если A º B, то A ^* º B ^*.

Принцип двойственности можно использовать для нахождения новых равносильностей. Например, для 1-го закона поглощения (равносильность 6а) имеем:

A &(A V B) º A.

Следуя принципу двойственности, получим новую равносильность:

A V A & B º A (2- ой закон поглощения).

Булева алгебра (алгебра логики). Полные системы булевых функций

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

Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.

Система булевых функций { f ₁, f ₂, …, f_n } называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {Ø, &, V} является полной. Также полными являются следующие системы функций:

а) {Ø, V}; б) {Ø, &}; в) {Ø, É}.

Полнота систем {Ø, V} и {Ø, &} следует из полноты системы {Ø, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A & B ºØ(Ø A VØ B); A V B º Ø(Ø A &Ø B).

Поэтому система {Ø, &, V} может быть сокращена на одну функцию:

Полнота системы {Ø, É} следует из полноты системы {Ø, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию:

A É B ºØ A V B.