6.4. Равносильность формул

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

Две формулы алгебры высказываний F₁ и F₂ называются равносильными (эквивалентными), если их таблицы истинности совпадают. Равносильность формул будем обозначать через F₁≡F₂. Нужно различать символы ↔ и ≡. Символ ↔ является символом формального языка, с помощью которого строятся формулы; символ ≡ заменяет слово «равносильно». Заметим, что отношение равносильности есть отношение эквивалентности. При этом справедливы утверждения:

1. Если две ПФ равносильны и одна из них содержит переменные, которых нет в другой, то ПФ от этих переменных не зависит (такие переменные называются фиктивными).

2. Если две ПФ равносильны, то их отрицания также равносильны.

3. Если в двух равносильных ПФ все вхождения некоторой переменной заменить любой формулой, то полученные новые ПФ будут равносильны.

Для любых формул X, Y, Z справедливы следующие равносильности (законы алгебры высказываний):

1. , (коммутативность);

2. , (ассоциативность);

3. , (дистрибутивность);

4. , (идемпотентность);

5. , (з-ны поглощения);

6. (закон двойного отрицания);

7. , (законы де Моргана);

8. , , , , , (законы, определяющие действия с константами);

9. , (исключение импликации и эквиваленции);

10. (исключение дизъюнкции);

11. (исключение конъюнкции).

12. Любая равносильность может быть легко доказана либо с помощью таблиц истинности, либо равносильными преобразованиями. Докажем, например, один из законов де Моргана.

.

Для этого составим таблицы истинности для ПФ, стоящих в левой и правой частях выражения, и сравним их.

Х	Y
0	0	1	1
0	1	0	0
1	0	0	0
1	1	0	0

Любая равносильность может быть легко доказана либо с помощью таблиц истинности, либо равносильными преобразованиями.

Пример. Доказать равносильность

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

Понятия «равносильность» и «тавтология» связаны между собой следующим образом.

Теорема. F₁≡F₂ тогда и только тогда, когда F₁↔F₂ является тавтологией.

Справедливость этой теоремы вытекает непосредственно из определений ≡ и тавтологии.

Пример. Доказать .

Покажем, что соответствующая эквиваленция является тавтологией.

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

Пример. XY  Y = .

XY (XY)  (YX)  ( Y)  ( X) .

То есть операцию эквиваленции всегда можно заместить операций импликации и конъюнкции или дизъюнкции и отрицания.

Пример. XY  XY .

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

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

Правила замены и подстановки расширяют возможности эквива­лентных преобразований формул сложных высказываний.

Пример. Дано F=(X₁X₂) ((X₂X₃) (X₁X₂ X₃).

Выполним преобразования для упрощения алгебраического выражения.

1. Удалим всюду логическую связку :

F= ;

2. Приведем отрицание к по закону де Моргана:

F=X₁ X₂   X₃;

3. Выполним преобразование по закону дистрибутивности:

F=( X₁ )  X₂   X₃;

4. Удалить член (X₁ ), так как (X₁ )=1:

F= X₂  X₃;

5. Выполним преобразование по закону дистрибутивности:

F= (X₂X₃)  (  X₃);

6. Удалим ( X₃ )=1:

F= (X₂X₃);

7) Применим закон ассоциативности:

F=( X₂)X₃;

7. Приравняем «истине» значение формулы X, т.к. ( X₂)=1:

F=1X₃=1.

Пример. Дано рассуждение «или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В)».

Формула сложного высказывания имеет вид:

А АСАВС;

1) преобразуем формулу, используя закон де Моргана, получим:

А(АВ)АСАВС;

2) применим закон идемпотентности:

А(АВ)AАСАВС;

3) применить закон дистрибутивности по переменной А:

А((АВ)АСВС);

4) применим закон дистрибутивности по переменной С:

А((АВ) С (АВ));

5) введем константу 1:

А((АВ) 1 С (АВ));

6) применить закон дистрибутивности для подформулы (АВ), получим:

А(АВ)  (1С);

7) удалим (1С), получим:

А (АВ);

8) применить закон поглощения, получим:

А.

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

Пример. Шесть школьников – Андрей, Борис, Григорий, Дмитрий, Евгений и Семен – участвовали в олимпиаде. Двое из них решили все задачи. На вопрос, кто решил все задачи, последовали ответы: 1) Андрей и Дмитрий; 2) Борис и Евгений; 3) Евгений и Андрей; 4) Борис и Григорий; 5) Семен и Андрей. В четырех из этих ответов одна часть неверна, другая верна. В одном – обе части неверны. Кто решил все задачи?

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

A= «Андрей решил все задачи»;

Б= «Борис решил все задачи»;

Г= «Григорий решил все задачи»;

Д= «Дмитрий решил все задачи»;

Е= «Евгений решил все задачи»;

С= «Семен решил все задачи».

Так как в одном из ответов обе части неверны, а в остальных – одна, то необходимо составить пять формул, отражающих пять различных высказываний:

  ( ЕБ )  ( АЕ )  ( ГБ ) 

 ( АС );

  ( ДА )  ( АЕ )  ( ГБ ) 

 ( АС );

  ( ДА )  ( ЕБ )  ( ГБ ) 

 ( АС );

  ( ДА )  ( ЕБ )  ( АЕ ) 

 ( АС );

  ( ДА )  ( ЕБ )  ( АЕ ) 

 ( ГБ ).

Если допустить, что 1 и 1, то первая формула может быть записана так:

  ( ЕБ ) Е  ( ГБ ) С ,

т. к. член А0.

Если допустить, что 1 и 1, то вторая формула может быть записана так:

  ( ДА )  А Г ( АС ),

т. к. члены Е 0 и Б 0.

Если допустить, что 1 и 1, то третья формула может быть записана так:

  ДБ  ( ГБ )С ,

т. к. члены А 0, Е=0, и А0.

Если допустить, что 1 и 1, то четвертая формула может быть записана так:

 ( ДА ) Е( АЕ )( АС ), т. к. член Б 0.

Если допустить, что 1 и 1, то пятая формула может быть записана так:

  Д ( ЕБ )  Е  ( ГБ ),

т. к. член А 0.

Применив законы дистрибутивности, идемпотентности и поглощения эти формулы можно упростить так:

  ЕГС;

   АГ;

  ДСБ;

  ДЕС;

  ДЕГ.

По условиям задачи только два участника решили все задачи. Поэтому формулы, содержащие по три пропозициональных переменных без отрицания, не отвечают поставленным условиям, а одна, содержащая только две переменных без отрицания, отвечает условиям задачи. Это    АГ. Следовательно, все задачи на олимпиаде решили Андрей (А) и Григорий (Г).