- •Математическая логика и теория алгоритмов
- •Воронеж 2011
- •1. Логика высказываний
- •1.1. Алгебра высказываний
- •Операции над высказываниями
- •1.1.2. Правила записи сложных формул
- •1.1.3. Таблицы истинности
- •1.1.4. Равносильность формул
- •1.1.5. Дизъюнктивные и конъюнктивные нормальные формы
- •1.1.6. Логическое следствие
- •1.2. Исчисление высказываний
- •1.2.1. Алгоритмы проверки общезначимости и противоречивости в исчислении высказываний
- •1.2.2. Метод резолюций в исчислении высказываний
- •1.2.3. Метод резолюций для хорновских дизъюнктов
- •Задачи и упражнения
- •2. Логика и исчисление предикатов
- •2.1. Логика предикатов
- •2.2. Алгебра предикатов
- •2.2.1. Логические операции
- •2.2.2. Правила записи сложных формул
- •2.2.3. Законы алгебры предикатов
- •2.2.4. Предваренная нормальная форма
- •2.2.4.1. Алгоритм приведения формулы к виду пнф
- •2.2.5. Сколемовская стандартная форма
- •2.2.5.1. Алгоритм Сколема
- •2.3. Исчисление предикатов
- •2.3.1. Интерпретация формул
- •2.3.2. Правила вывода
- •2.3.3. Метод дедуктивного вывода
- •2.3.4. Метод резолюций в исчислении предикатов
- •2.4. Проблемы в исчислении предикатов
- •2.5. Логическое программирование
- •Задачи и упражнения
- •3. Элементы теории алгоритмов
- •3.1. Рекурсивные функции
- •3.1.1. Базовые функции
- •3.1.2. Элементарные операции
- •Выразим с помощью схемы примитивной рекурсии:
- •3.2. Машина Тьюринга
- •3.2.1. Описание машины Тьюринга
- •3.2.2. Примеры машин Тьюринга
- •3.3. Конечные автоматы
- •4. Неклассические логики
- •4.1. Пропозиционные логики
- •4.2. Алгоритмические логики
- •Задачи и упражнения
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
1.1.4. Равносильность формул
Различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие равносильности формул.
Две формулы алгебры высказываний F1 и F2 называются равносильными (эквивалентными), если их таблицы истинности совпадают. Равносильность формул будем обозначать через F1≡F2. Нужно различать символы ↔ и ≡. Символ ↔ является символом формального языка, с помощью которого строятся формулы; символ ≡ заменяет слово «равносильно». Заметим, что отношение равносильности есть отношение эквивалентности. При этом справедливы утверждения:
Если две ПФ равносильны и одна из них содержит переменные, которых нет в другой, то ПФ от этих переменных не зависит (такие переменные называются фиктивными).
Если две ПФ равносильны, то их отрицания также равносильны.
Если в двух равносильных ПФ все вхождения некоторой переменной заменить любой формулой, то полученные новые ПФ будут равносильны.
Для любых формул X, Y, Z справедливы следующие равносильности (законы алгебры высказываний):
, (коммутативность);
, (ассоциативность);
, (дистрибутивность);
, (идемпотентность);
, (з-ны поглощения);
(закон двойного отрицания);
, (законы де Моргана);
, , , , , (законы, определяющие действия с константами);
, (исключение импликации и эквиваленции);
(исключение дизъюнкции);
11. (исключение конъюнкции).
Любая равносильность может быть легко доказана либо с помощью таблиц истинности, либо равносильными преобразованиями. Докажем, например, один из законов де Моргана.
.
Для этого составим таблицы истинности для ПФ, стоящих в левой и правой частях выражения, и сравним их.
-
Х
Y
0
0
1
1
0
1
0
0
1
0
0
0
1
1
0
0
Пример. Доказать равносильность
Используя закон поглощения, дистрибутивный закон и закон, определяющий действие с 1, получим
Понятия «равносильность» и «тавтология» связаны между собой следующим образом.
Теорема. F1≡F2 тогда и только тогда, когда F1↔F2 является тавтологией.
Справедливость этой теоремы вытекает непосредственно из определений ≡ и тавтологии.
Пример. Доказать .
Покажем, что соответствующая эквиваленция является тавтологией.
З нание законов алгебры высказываний позволяет выполнять равносильные преобразования любых логических формул, сохраняя их значения для любых наборов пропозициональных переменных. Ниже на примерах рассмотрены равносильные преобразования основных логических операций.
Пример. XY Y = .
XY (XY) (YX) ( Y) ( X) .
То есть операцию эквиваленции всегда можно заместить операций импликации и конъюнкции или дизъюнкции и отрицания.
Пример. XY XY .
Выполненные примеры показывают, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей вместо импликации или эквиваленции только две логических операции: дизъюнкцию и отрицание или конъюнкцию и отрицание. Этот факт показывает, что множество логических связок дизъюнкции и отрицания, конъюнкции и отрицания формируют функционально полные алгебраические системы. Они достаточны для выражения любой логической функции
Если формула F содержит подформулу Fi, то замена подформулы Fi в формуле F на эквивалентную ей формулу Fj не изменяет значения формулы F при любом наборе пропозициональных переменных. Если необходима подстановка в формулу F вместо формулы Fi новой формулы Fj, то эту операцию нужно выполнить всюду по символу Fi .
Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний.
Пример. Дано F=(X1X2) ((X2X3) (X1X2 X3).
Выполним преобразования для упрощения алгебраического выражения.
Удалим всюду логическую связку :
F= ;
Приведем отрицание к по закону де Моргана:
F=X1 X2 X3;
Выполним преобразование по закону дистрибутивности: F=( X1 ) X2 X3;
Удалить член (X1 ), так как (X1 )=1:
F= X2 X3;
Выполним преобразование по закону дистрибутивности: F= (X2X3) ( X3);
Удалим ( X3 )=1: F= (X2X3);
7) Применим закон ассоциативности: F=( X2)X3;
8) Приравняем «истине» значение формулы X, т. к. ( X2)=1: F=1X3=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.
Применив законы дистрибутивности, идемпотентности и поглощения эти формулы можно упростить так:
ЕГС;
АГ;
ДСБ;
ДЕС;
ДЕГ.
По условиям задачи только два участника решили все задачи. Поэтому формулы, содержащие по три пропозициональных переменных без отрицания, не отвечают поставленным условиям, а одна, содержащая только две переменных без отрицания, отвечает условиям задачи. Это АГ. Следовательно, все задачи на олимпиаде решили Андрей (А) и Григорий (Г).