Доказательство логических следствий в логике высказываний

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

Необходимо усвоить следующие основные понятия. В математике, как и в обычной жизни, часто нужно решить, следует ли одно утверждение из нескольких других. Это приводит к понятию “логический вывод”. Пусть даны формулы F₁,F₂,...,F_n и формула G. Товорят, что G есть логическое следствие формул F₁,F₂,...,F_n (или G логически следует из F₁,F₂,...,F_n) тогда и только тогда, когда для всякой интерпретации I, в которой F₁ÙF₂Ù...ÙF_n истинна, G также истинна. F₁,F₂,...,F_n называются аксиомами (или постулатами или посылками) G.

Следует знать и уметь пользоваться следующими теоремами о выводе логического следствия:

Теорема 1. Пусть даны формулы F₁,F₂,...,F_n и формула G. Тогда G есть логическое следствие F₁,F₂,...,F_n тогда и только тогда, когда ((F₁ÙF₂Ù...ÙF_n)G) общезначима.

Теорема 2. Пусть даны формулы F₁,F₂,...,F_n и формула G. Тогда G есть логическое следствие F₁,F₂,...,F_n тогда и только тогда, когда (F₁ÙF₂Ù...ÙF_nÙØG) противоречива.

Теоремы 1 и 2 очень важны. Из них вытекает: доказательство того, что отдельная формула есть логическое следствие конечного множества формул, эквивалентное доказательству того, что некоторая связанная с ними формула общезначима или противоречива. Если G есть логическое следствие формул F₁,F₂,...,F_n, то формула ((F₁ÙF₂Ù...ÙF_n)G) называется теоремой, а G называется также заключением теоремы. В математике, так же, как и в других областях, многие проблемы могут быть сформулированы как проблемы доказательства теорем.

Рассмотрим примеры решения типичных упражнений и задач

1. Даны формулы логики высказываний: F₁(PQ), F2ØQ, GØP.

Показать, что G есть логическое следствие F₁ и F₂.

Решение. Метод 1. Используем метод истинностных таблиц, чтобы показать, что G истинна в каждой модели формулы (PQ)ÙØQ. (Когда интерпретация I удовлетворяет формуле F, I называется моделью F). Из табл.3.4 мы видим, что есть только одна модель для (PQ)ÙØQ, а именно {ØP, ØQ}.

Таблица9.4 - Истинностная таблица (PQ)ÙØQ и ØP.

P Q	PQ	ØQ	(PQ)ÙØQ	ØP
0 0 0 1 1 0 1 1

Формула ØP истинна в этой модели. Таким образом, по определению логического следствия заключаем, что ØР есть логическое следствие (PQ) и ØQ.

Метод 2. Используем теорему 1. Это может быть сделано просто путем расширения истинностной таблицы в табл.9.4, т.е. путем вычисления истинностных значений формулы ((PQ)ÙØQ)ØP. Табл.3.5 показывает, что ((PQ)ÙØQ)ØP истинна при всех интерпретациях.

Таблица 9.5 - Истинностная таблица для ((PQ)ÙØQ)ØP

P Q	PQ	ØQ	(PQ)ÙØQ)	ØP	((PQ)ÙØQ)ØP
0 0 0 1 1 0 1 1

Следовательно, ((PQ)ÙØQ)ØP общезначима и, согласно теореме 1, ØP есть логическое следствие (PQ) и ØQ.

Мы можем также доказать общезначимость формулы путем преобразования ее в конъюнктивную нормальную форму:

((PQ)ÙØQ)ØP=Ø((PQ)ÙØQ)ÚØP=

=Ø((ØPÚQ)ÙØQ)ÚØP=Ø((ØPÙØQ)Ú(QÙØQ))ÚØP=

=Ø((ØPÙØQ)ÚЛ)ÚØP=Ø(ØPÙØQ)ÚØP=(PÚQ)ÚØP=

=QÚ (PÚØP)=QÚU=U.

Таким образом, ((PQ)ÙØQ)ØP общезначима.

Метод 3. Используем теорему 2. В этом случае мы докажем, что формула ((PQ)ÙØQ)Ù(Ø(ØP))=(PQ)ÙØQÙP противоречива. Как и в методе 2, можно использовать метод истинностных таблиц, чтобы показать, что (PQ)ÙØQÙP ложна в каждой интерпретации. Из табл.11.6 мы заключаем, что (PQ)ÙØQÙP противоречива и, согласно теореме 2, ØP есть логическое следствие формул (PQ) и ØQ.

Таблица 9.6 - Истинностная таблица для (PQ)ÙØQÙP

P Q	PQ	ØQ	(PQ)ÙØQÙP
0 0 0 1 1 0 1 1

Мы можем также доказать противоречивость формулы (PQ)ÙØQÙP путем ее преобразования в дизъюнктивную нормальную форму:

(PQ)ÙØQÙP=(ØPÚQ)ÙØQÙP=(ØPÙØQÙP)Ú(QÙØQÙP)=

=(ЛÙØQ)Ú(ЛÙP)=ЛÚЛ=Л. Таким образом, (PQ)ÙØQÙP противоречива.

2. Покажем применение логики высказываний при решении задач в словесной формулировке. Допустим, что если конгресс отказывается принять новые законы, то забастовка не будет окончена, если только она не длится более года и президент фирмы не уходит в отставку. Закончится ли забастовка, если конгрес отказывается действовать и забастовка только что началась?

Решение. Сперва преобразуем утверждения в символы:

Р: Конгресс отказывается действовать.

Q: Забастовка оканчивается.

R: Президент фирмы уходит в отставку.

S: Забастовка длится более года.

Тогда факты, данные в примере, могут быть представлены следующими формулами:

F₁: (P(ØQÚ(RÙS))) Если конгресс отказывается принять новые законы, то забастовка не будет окончена, если она не длится более года и президент фирмы не уходит в отставку.

F₂: P Конгресс отказывается действовать.

F₃: ØS Забастовка только что началась.

Можно ли заключить из фактов F₁, F₂ и F₃, что забастовка не будет окончена, т.е. можно ли показать, что ØQ есть логическое следствие F₁, F₂ и F₃? По теореме 1 это эквивалентно тому, что ((P(ØQÚ(RÙS)))ÙPÙØS)ØQ ¾ общезначимая формула. Истинностные значения указанной формулы при всех интерпретациях приведены в табл. 9.7.

Таблица 9.7 - Истинностная таблица для (F₁ Ù F₂ Ù F₃)ØQ,

где F₁(P(ØQÚ(RÙS))), F₂Р, F₃ØS

P	Q	R	S	F1	F2	F3	ØQ	(F1ÙF2ÙF3)ØQ

Из табл 9.7 видно, что не существует интерпретации, при которой данная формула ложна. Следовательно, формула ((P(ØQÚ(RÙS)))ÙPÙØS)ØQ общезначима. Поэтому ØQ есть логическое следствие F₁,F₂ и F₃, т.е. мы можем получить заключение ØQ из F₁,F₂ и F₃. Следовательно, забастовка не будет окончена.

Из приведенных примеров видно, что логика высказываний может применяться ко многим задачам. Метод состоит в том, чтобы сначала записать задачи формулами, а затем доказать, что формулы общезначимы или противоречивы. Процедуру доказательства противоречивости формулы путем ее преобразования в ДНФ и получение противоречивой формулы (Л) иногда называют методом умножения, потому что процесс преобразования очень похож на раскрытие скобок в произведении сумм.

Мы показали использование метода истинностных таблиц и метода умножения для доказательства общезначимости (или противоречивости).

Контрольные вопросы и задания по теме:

1. Логическое следствие в ЛВ.

2. Теоремы 1 и 2 об установлении логического следствия.

3. Методы установления истинности или противоречивости формул ЛВ.

4. Докажите, что (ØQØP) есть логическое следствие(PQ).

5. Если конгресс отказывается принять новые законы, то забастовка не будет окончена, кроме случая, когда она длится более года и президент фирмы уйдет в отставку. Допустим, что конгресс отказывается действовать, забастовка оканчивается и президент фирмы не уходит. Длилась ли забастовка более года?

6. Даны утверждения

F₁: PS,

F₂: SU,

F₃: P,

G: U.

Является ли G логическим следствием F₁,F₂ и F₃?

7. Покажите, что Q есть логическое следствие (PQ) и P. Это так называемое правило модус поненс (modus ponens).

# Формализация высказываний средствами логики первого порядка.