Математическая логика и теория алгоритмов

Через А, В, С иD обозначим соответственно высказывания «по­ ступок совершил J71, Л2, ЛЗ и ЛА». Тогда условие, что поступок мог совершить только один из четырех, запишется в виде пропозицио­ нальной формы: А=](А&В)&\А&С)&](А&0)& \B&Q& \BScD)& \C&D). которая означает, что никакие два из четырех высказываний не могут быть оба истинными. Заявление каждого из четырех означа­ ет: Д Д 1 С и 1 Z). Но так как истинно только одно из них, то, значит, никакие два из этих заявлений не являются одновременно истинными. Это условие запишется в следующем виде: в=\в&П)& ](D &lc)& ](l £)&]c)& ](1 C &1 D ). Берем конъюнкцию посылок А и В, находим для А&В сокра­ щенную к.н.ф.: 1 B8l] DSlCSl] А, которая означаег, что высказывания А, В, D ложны, а высказывание С; «Поступок совершил ЛЗ» - истинно. 9. Используя условия из рассмотренного примера, узнать, кто совершил поступок, если известно, что только один из них лжет. 10. С помощью метода резолюций доказать, что следующее множество дизъюнктов невыполнимо: 1 P v1 gvi?, PvR, Q^R, 1-/?. 11. Методом резолюций, используя метод исчерпания уровней, доказать, что следующее множество дизъюнктов невыполнимо: a)PvQvR, I P v R , 1(2, IR; 6)PvQ, IQvR, ^ P vQ, ^R. 12. Пусть S ~{P,Q,R,W, 1 Pvl 6^1 i?vl W}. Сколько резольвент будет порождено из S методом насыщения уровня до того, как будет получен пустой дизъюнкт? 13. Для S ={P,Q,R,W, 1 P v l Q v l Rvl W] получить пустой дизъ­ юнкт, используя лок-резолюцию. 14. Для .S" ={ Pvgvi?, 1PvR, I q , 1 i?} получить пустой дизъ­ юнкт, используя лок-резолюцию. 15. Найти сколемовские стандартные формы для следующих формул: а) 3x\/y\/z (P (x,y) =:>Q (x,z)); б) 3 X 3>'V Z ( P ( A :,3;) =>Q{x,z)); в) Vx3>'Vz(?(x,>') =>Q(x,z)); г) VxV>>3z(P(^:,>>) =>2(x,z)); 132