История

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.

7

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

Метод равносильных преобразований формул (или метод цепочек равносильностей) используется для нахождения формулы, равносильной данной и обладающей теми или иными требуемыми свойствами. Он состоит в том, что для данной формулы А строится конечная последовательность формул A,А₁,А₂,...,А_n, такая, что АА₁,А₁A₂,...,A_n-1A_n, а формула A_n есть искомая формула. Благодаря транзитивности отношения равносильности формул из этого следует, что АА_n.

Метод основан на предложении 5, с помощью которого заменяют некоторое вхождение в формулу А ее подформулы на вхождение равносильной подформулы и получают формулу А₁ и т.д. Для использования метода равносильных преобразований формул необходимо изначально иметь достаточно большой набор “равносильностей” (пар равносильных формул). Их можно, в частности, получать из общезначимых формул с помощью предложения о связи общезначимости эквиваленции с равносильностью ее частей.

Определение. 

Приведенные ниже формульные схемы будем называть важнейшими общезначимыми формульными эквиваленциями (нумерация формульных схем соответствует списку важнейших общезначимых формульных схем):

(14) (AB)  (AB)&(BA);           (33) A(BC)  (ABAC);

(15) AB  AB;                              (34) A&A  A;

(16) AB  (A&B);                         (35) AA  A;

(17) A&B  (AB);                        (36) A&(AB)  A;

(18) A&B  (AB);                         (37) AA&B  A;

(19) AB  (A&B);                         (38) A&(BB)  A;

(20) AB  AB;                              (39) A(B&B)  A;

(21) A&B  B&A;                                 (40) A&B&B  B&B;

(22) AB  BA;                                  (41) ABB  BB;

(23) (AB)  (BA);                          (42) (A&B)  AB;

(24) A&(B&C)  (A&B)&C;                 (43) (AB) A&B;

(25) A(BC)  (AB)C;                  (44) (AB)  A&B;

(26) (A(BC))  ((AB)C);       (45) (AB)  (AB)&(A&B);

(27) A&(BC)  A&BA&C;              (46) A  A;

(28) A(B&C)  (AB)&(AC);         (47) A  A;

(29) A(BC)  (AB)(AC);      (51) (A(BC))  (B(AC));

(30) A(BC)  (ABAC);         (52) A(BC)  A&BC;

(31) AB&C  (AB)&(AC);       (54) AB  BA.

(32) ABC  (AB)(AC);

Применяя предложение 2 к общезначимым формульным схемам (14) - (47), (51), (52), (54), получим соответствующий набор равносильных формул, который (учитывая свойство симметричности отношения равносильности формул) оказывается вполне достаточным для получения любой верной равносильности.

Пример. 

Установить общезначимость закона Дунса Скота A(AB).

Решение.

            _{(15)             (15)                                   (46)                            (25)        (41)}    A(AB)A(AB)(A)(AB)A(AB)(AA)BAA,

в результате получена общезначимая формула (48).

Таким образом, данный метод основан на применении предложения “о связи общезначимости эквиваленции с равносильностью членов этой эквиваленции”к общезначимым равносильным формулам (14—47), (51), (52), (54), (55), в результате чего мы получаем равносильные формулы, которые на основании предложения о замене можно использовать для упрощения формул (в частности, с целью доказательства их общезначимости). Например, так как эквиваленция (15) (AB)  (AB) является общезначимой формулой, то имеет место равносильность (AB) (AB).

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

 

Предложение 1 (о полноте набора связок {,,&}).

Для всякой формулы языка нулевого порядка найдется равносильная ей формула, не содержащая других связок, кроме ,  и &.

 

Пример.

Удалите логические связки  и  из формулы (A(AB)).

Решение.

Применяя рассуждения, использованные в доказательстве предложения, получим: ((A(AB))&((AB)A)) ((A(AB))&((AB)A)).

8