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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

Х	Y

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

Используя закон поглощения, дистрибутивный закон и закон, определяющий действие с 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:

8) Получим

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.

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

Ù Ù ÙЕÙГÙС;

Ù Ù Ù ÙАÙГ;

Ù Ù ÙДÙСÙБ;

Ù Ù ÙДÙЕÙС;

Ù Ù ÙДÙЕÙГ.

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