Математическая логика / Модуль 3. Умозаключения / Модуль 3. Практическое занятие 2

Модуль 3. Умозаключения

Занятие 2. Проверка формул на выводимость

Задание 1. Записать данное рассуждение в виде формулы логики высказываний. Выяснить, правилен ли вывод двумя способами: проверкой на общезначимость и проверкой на выводимость.

№1. Если бы Иван пришёл, то либо Марья, либо Дарья пришла бы. Но ни Марья, ни Иван не пришли. Следовательно, Дарья пришла.

Необходимо записать данное рассуждение в виде формулы логики высказываний.

p – «Иван пришёл»;

q – «Марья пришла»;

r – «Дарья пришла».

1. Для проверки на общезначимость будем составлять для полученной формулы таблицу истинности.

(*)

p	q	r	(1-1)	(2-2)	(3-3)	(4-4)	(5-5)	(6-6)	(*)
1	1	1	1	1	0	0	0	0	1
1	1	0	1	1	0	0	0	0	1
1	0	1	1	1	1	0	0	0	1
1	0	0	0	0	1	0	0	0	1
0	1	1	1	1	0	1	0	0	1
0	1	0	1	1	0	1	0	0	1
0	0	1	1	1	1	1	1	1	1
0	0	0	0	1	1	1	1	1	0

Вывод: Формула не общезначима. Вывод логически не следует из посылки

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

Вывод: Формула не выводима. Вывод логически не следует из посылок.

Самостоятельно:

№2. Если бы Иван пришёл, то или Марья пришла бы, или Дарья пришла бы. Но Марья пришла, а Дарья не пришла. Значит, Иван не пришёл.

Задание 2.

Данную формулу логики предикатов, проверить на выводимость.

№1. .

Пусть P(x) – x белый.

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

Интуиция подсказывает нам, что данная формула выводима. Докажем это, построив её вывод:

Ответ: формула выводима.

№2. .

Пусть P(x,y) – x любит y.

Тогда формула будет читаться так: «Если все кого-то любят, то есть такой, которого любят все».

Интуиция подсказывает нам, что данная формула выводима. Подберём для неё опровергающую модель.

На данном графе двуместного предиката P(x,y) сплошная стрелка означает, что P(x,y) есть ИСТИНА (т.е. x любит y), а пунктирная означает, что P(x,y) есть ЛОЖЬ (т.е. x не любит y). На графе 1-ый любит 2-го и 2-ой любит 1-го, т.е. каждый кого-то любит и утверждение в посылке выполняется. Но при этом 1-го не любит 1-ый, а 2-го не любит 2-ой, т.е. нет того, кого любили бы все и утверждение, записанное в заключении, не выполняется. Следовательно, формула содержательно опровергнута.

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

Ответ: формула не выводима.

Самостоятельно:

№3.

№4.

№5.

№6.

№7.

№8.