Материал: Дискретная математика. учебное пособие. Собенина О.В

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

.

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

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

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

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

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

  ЕГС;

   АГ;

  ДСБ;

  ДЕС;

  ДЕГ.

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

5.5. Дизъюнктивные и конъюнктивные нормальные формы

Покажем, что для каждой ПФ существует ей равносильная специального вида. Если Х – пропозициональная переменная, v есть 0 или 1, то выражение

называется литерой. Литеры X и называются контрарными.

Заметим, что ПФ тогда и только тогда, когда , то есть .

Следовательно, ПФ на наборе принимает значение 1, а на любом другом – значение 0. Аналогично ПФ принимает значение 0 только на наборе ( , ,..., ), а на всех остальных наборах – 1 [3].

Т еорема 5.5.1. Для любой ПФ имеет место равносильность

называемая дизъюнктивным разложением по переменной Х₁.

Доказательство.

Пусть – произвольная ПФ. Определим значения левой и правой частей равносильности при Х₁=1 и Х₁=0.

П ри Х₁=0 в левой части равносильности получаем ПФ , а в правой части –

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

Аналогично можно показать, что при Х₁=1 значением левой и правой частей равносильности является ПФ .