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

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

Две формулы алгебры высказываний 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 ₃;

8) Приравняем «истине» значение формулы 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.

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

Ù Ù Ù Е Ù Г Ù С;

Ù Ù Ù Ù А Ù Г;

Ù Ù Ù Д Ù С Ù Б;

Ù Ù Ù Д Ù Е Ù С;

Ù Ù Ù Д Ù Е Ù Г.

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