Семантический способ решения

Синтаксический способ.

Возьмём аксиому 3 II-ой группы исчисления высказываний и заменим C на ù C, а U на ù U получим: ^ (Z ® ù C) ® ((Z ® ù U) ® (Z ® ù C Ù ù U) - (1) также выводимую формулу. Выполним подстановку ù (C Ú U)

ò (1)

получим: Z

^ (ù (C Ú U) ® ù C) ® ((ù (C Ú U) ® ù U) ® (ù (C Ú U) ® ù C Ù ù U)) - (2)

Обозначим: A = ù (C Ú U) ® ù C; B = ù (C Ú U) ® ù U;

N = (ù (C Ú U) ® ù U) ® (ù (C Ú U) ® ù C Ù ù U) - докажем что эти формулы доказуемы. Выполним подстановку C Ú U

ò (1 акс.IV гр)

U

получим: ^(C® C Ú U) ® (ù (C Ú U) ® ù C) заметим, что условием этой импликации является 1-ая аксиома III-ей группы и по правилу заключения формула A доказуема. Заменим в формуле A C на U, а U на C получим, что формула B также доказуема. Применяя правило заключения к доказуемой формуле (2) и помня что A доказуема, получим, что N также доказуема. Применяя правило заключения к формуле N и исходя из доказуемости B, получим доказуемость исходной формулы. В этом примере синтаксический способ доказательства требует некоторых навыков в использовании правил вывода и аксиом, а также кажется более трудоёмким и сложным чем семантический, хотя на самом деле всё определяется данным примером. Рассмотрим другой пример.

По подозрению в совершённом преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий - известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом ложь.

Браун: “ Я совершил это. Джон не виноват.”

Джон: “ Браун не виноват. Преступление совершил Смит”.

Смит: “Я не виноват, виновен Браун”.

Определите имя старика, мошенника и чиновника и кто из них виноват, если известно что преступник один.

Обозначим высказывания: Б - виноват Браун, Д - виноват Джон, С - виноват Смит. Тогда утверждения, высказанные задержанными примут вид:

1. Б Ù ù Д; 2. ù Б Ù С; 3. Б Ù ù С и истинной должна быть общая дизъюнкция всех утверждений: А=(Б Ù ù Д) Ú (ù Б Ù С) Ú (Б Ù ù С).

Составим таблицу истинности для всех вариантов высказываний, утверждений и общей дизъюнкции.

Таблица 11

номер вариа-нта	Б	Д	С	Б Ù ù Д	ù Б Ù С	Б Ù ù С	А

Проведём анализ вариантов, когда А-истинно.

Варианты: 2,3 и 5 отпадают, т.к. в этих случаях существует одновременно два преступника, а это противоречит условию задачи (“преступник один”).

Вариант 4 также отпадает, т.к. в этом случае два утверждения, высказанные задержанными одновременно истинны, а это противоречит условию (“правду говорит только один старик”).

Отсюда следует, что верным остаётся 7-ой вариант, соответствующий всем условиям задачи и следовательно преступник Смит. В этом варианте 2-ое утверждение, высказанное задержанным Джоном является истинным, следовательно Джон-старик(“старик говорил правду”) и остаётся утверждать, что чиновник-Браун.

Дата добавления: 2015-06-27