Задача по логике (Доказать в исчислении высказываний (буквы обозначают произвольные формулы))
Описание файла
PDF-файл из архива "Доказать в исчислении высказываний (буквы обозначают произвольные формулы)", который расположен в категории "". Всё это находится в предмете "математическая логика и теория алгоритмов" из 4 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "математическая логика и теория алгоритмов" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Доказать в исчислении высказываний (буквы обозначают произвольные формулы):((ZX)& (XY)) ((XY)Z)Решение.Преобразуем левую часть формулы, используя определение конъюнкции & ( ) :((Z X ) & (X Y )) ((Z X ) (X Y ))Преобразуем правую часть формулы, используя определение дизъюнкции :( X Y ) Z ( X Y ) Z (X Y ) ZСледовательно, исходная формула имеет вид:((Z X ) (X Y )) ((X Y ) Z ) .Для доказательства эквивалентности необходимо доказать, что:1.
| ((Z X ) (X Y )) ((X Y ) Z ) и2. | ((X Y ) Z ) ((Z X ) (X Y )) .1. Доказательство | ((Z X ) (X Y )) ((X Y ) Z ) .Согласно теореме дедукции, достаточно доказать, что Z выводимо из гипотез1) ((Z X ) (X Y )) и 2) (X Y ) , а затем дважды применитьтеорему дедукции: если Г, А ⊢ В, то Г ⊢ А→В.12((Z X )(X Y ))(X Y )3 ((Z X )(X Y ))((Z X )(X Y ))гипотеза 1гипотеза 2секвенция 34(Z X )(X Y )modus ponens для 1,35(X Y )(X Y )секвенция 36(Z X )(X Y )секвенция 1 для 4,57((Z X )(X Y ))((X Y )(Z X ))секвенция 78(X Y )(Z X )modus ponens для 6,79(Z X )modus ponens для 2,810Z (Z X )секвенция 511( Z (Z X ))((Z X )Z )секвенция 712(Z X )Zmodus ponens для 10,1113Zmodus ponens для 9,122.
Доказательство | ((X Y ) Z ) ((Z X ) (X Y ))Согласно теореме дедукции, для этого достаточно доказать вывод формулы((Z X ) (X Y )) из гипотезы (X Y ) Z .Т.к. согласно секвенции 4| ((Z X ) (X Y )) ((Z X ) (X Y )) , то будемдоказывать, что ((X Y )Z ) | (Z X )(X Y ) , т.е. будем строитьвывод формулы (X Y ) из гипотез 1) (X Y )Z и 2) (Z X ) .1(X Y ) Zгипотеза 12Z Xгипотеза 23(X Y ) X4((X Y ) X ) (X (X Y ))секвенция 1 из 1 и 2секвенция 75X (X Y )modus ponens для 3,46X (X Y )секвенция 57(X Y ) (X Y )секвенция 48X (X Y )секвенция 1 из 6,79 ( X (X Y )) ((X (X Y )) (X Y ))секвенция 910(X (X Y )) (X Y )modus ponens для 8,911(X Y )modus ponens для 5,10Следовательно, доказано ((X Y )Z ), (Z X ) | (X Y ) .Дважды применяя теорему дедукции получим:|((X Y )Z ) ((Z X )((X Y )) .Согласно секвенции 4 | ((Z X ) (X Y )) ((Z X ) (X Y )) .Применяя секвенцию 1, получаем:|((X Y )Z ) ((Z X )(X Y )) , что и требовалось доказать..