Доказать что формула в логическое следствие посылок

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

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

Необходимо усвоить следующие основные понятия. В математике, как и в обычной жизни, часто нужно решить, следует ли одно утверждение из нескольких других. Это приводит к понятию “логический вывод”. Пусть даны формулы 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. Даны формулы логики высказываний: F₁(PQ), F2ØQ, GØP.

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

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

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 истинна при всех интерпретациях.

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=

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

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

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.

где 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,

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

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

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

Источник

НАХОЖДЕНИЕ СЛЕДСТВИЙ ИЗ ПОСЫЛОК

1.22. Найдите все неравносильные между собой и не тождественно истинные формулы алгебры высказываний, являющиеся логическими следствиями следующих формул (посылок):

а) и ;

б) и Х;

в) и ;

г) и ;

д) и ;

е) и ;

ж) и ;

з) и ;

и) и ;

к) и ;

л) и Z.

Решение. а) Составляем конъюнкцию посылок и равносильными преобразованиями приводим ее к совершенной конъюнктивной нормальной форме:

.

Логическими следствиями из данных посылок будут все совершенные дизъюнктивные одночлены, входящие в полученную СКНФ, а также всевозможные конъюнкции этих одночленов по два, по три и т. д. Выписываем получающиеся формулы, придав им более удобную равносильную форму:

1) (первая посылка);

2) ;

3) ;

4) ;

5) ;

6) (вторая посылка);

7) .

1.23. Найдите формулу F (X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

а) и

б) и

в) и

г) и

д) и

е) и

Решение. а) Составляем таблицы истинности для формул, являющихся посылками:

X

Y

Z

V

Далее, в правом столбце цифрами отмечаем те строки, в которых все четыре посылки принимают значение 1. Этому требованию удовлетворяет лишь вторая строка, в которой l(Х)=0 и l(Y)=0. Следовательно, если мы найдем такую формулу F (X, Y), для которой F(0, 0) = 1, то такая формула будет логическим следствием четырех данных посылок. Ищем такую формулу, используя СДНФ и считая, что на всех других наборах значений переменных искомая формула обращается в 0:

Получаем .

1.24. Найдите следствие из посылок:

и

содержащее только переменные:

1.25. Найдите следствие из посылок и , содержащее только переменные:

1. 26. Найдите следствие из посылок задачи 1.23. а), содержащее только переменные X и V.

1.27.Найдите следствие из посылок:

зависящее только от переменных V, W и Z.

1.28. Найдите следствие из посылок:

содержащее только переменные:

1.29. Докажите, что описанный в решении задачи 1.23 а) способ отыскания логического следствия из данных посылок, содержащего только заданные пропозициональные переменные, позволяет найти самое сильное из следствий, т. е. такое следствие, что все другие следствия, связывающие указанные переменные, сами из него следуют.

1.30. Найдите все следствия из посылок: «Если сумма цифр целого числа делится на 3, то это число делится на 3 или на 9»; «Если целое число делится на 9, то оно делится на 3». Найденным следствиям придайте содержательный смысл.

Решение. Введем обозначения для простых высказываний:

X: «Сумма цифр целого числа делится на 3»;

Y: «Целое число делится на 3»;

Z: «Целое число делится на 9».

: «Если сумма цифр делится на 3, то число делится на 3 или на 9»;

: «Если число делится на 9, то оно делится на 3 или сумма цифр делится на 3»;

: «Если сумма цифр делится на 3 и число делится на 9, то оно делится на 3»;

: «Сумма цифр делится на 3 тогда и только тогда, когда число делится на 9 или число делится на 3»;

: «Если сумма цифр числа делится на 3, то число делится на 3»;

: «Если число делится на 9, то оно делится на 3»;

: «Если сумма цифр числа делится на 3 или число делится на 9, то число делится на 3».

1.31. Найдите все следствия из посылок и выразите их в содержательной форме: «Если последняя цифра целого числа четна, то число делится на 2 или на 4»; «Если целое число делится на 4, то оно делится на 2».

Указание. Запишите посылки в виде формул алгебры высказываний и сравните их с посылками предыдущей задачи.

1.32. Найдите все следствия из посылок: «Если целое число делится на 2 и на 5, то оно делится на 10»; «Целое число делится на 2 и не делится на 5». Выразите полученные следствия в содержательной форме.

Указание. Выразите посылки в виде формул алгебры высказываний и обратитесь к задаче 1.22, и.

Указание. См. задачу 1.22, з.

Решение. Введем обозначения для простейших высказываний, входящих в посылки:

X: «Четырехугольник — ромб»;

Y: «Четырехугольник — квадрат»;

Z: «Диагонали четырехугольника взаимно перпендикулярны»;

V: «Четырехугольник можно вписать в окружность».

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

Последняя посылка равносильна такой: и поэтому задача сводится к тому, чтобы из данных посылок получить следствие, зависящее лишь от переменных X и Y. Эта задача решена нами в задаче 1.23, а. Остается придать полученной формуле содержательный смысл: «Четырехугольник не является ни ромбом, ни квадратом».

Указание.См. задачу 1.26.

1.36. Даны посылки: «Если целое число п больше 1, то оно простое либо составное»; «Если целое число четное, то оно не простое»; «Если целое число больше 1 и не больше 2, то оно четное»; «Если целое число 2, то оно больше 1». Из этих посылок найдите следствие, связывающее высказывания: «Целое число больше 2», «Целое число четное» и «Целое число составное».

Указание. Выразите посылки в виде формул алгебры высказываний и обратитесь к задаче 1.27.

Указание. Выразите посылки в виде формул алгебры высказываний и обратитесь к задаче 1.28.

Источник