1. Найдите приведённую форму (ПФ) для следующих формул ИП:
а) ($ x (P(x) ® 
)); б) (a «(" y 
)); в) (R(x) ® ($ y (R(x) Ú Q(x, y))));
г) (P(x) ® ($ y (R(x) Ú Q(x, y)))); д) (R(x, y) «(" x P(x))); е) (Q(x) ® (Q(y) ® Q(x)));
ж) 
; з) 
; и) (
® b);
к) (" x (($ y P(x, y)) ® 
)); л) 
® 
);
м) ($ x ((" y Q(x,y)) ® ($ x (" y P(x,y)))); н) (U(p) Ú ($ x (V(x) ® U(x)))).
2. Какие из формул находятся в приведённой предварённой нормальной форме (ППНФ)?
а) (($ x P(x)) Ù )); б) (" x ($ y (P(y) Ú R(x))); в) (" x (($ y P(y)) Ú Q(x)));
г) ( ® b); д) a Ú T(x, y, z); е) (a Ù (" y )); ж) (S(x) Ú U(x, y));
з) ($ y (S(x) Ú U(x, y))); и) (" x ($ y (U(y) ® Q(x))); к) (" x ($ y (Q(y) Ú T(x))));
3. Приведите формулы к ППНФ:
а) (S(x) Ú U(x, y)); б) (($ x R(x)) Ù 
)); г) (
® E(y)); д) P(x, y);
е) (a «(" y )); ж) ($ x ((" y Q(x,y)) ® ($ x (" y P(x,y)))); з) 
;
з) (Q(x) ® (Q(y) ® a)); и) 
; к) (" x (($ y P(y)) Ú Q(y)));
л) ((P(y) Ú (" y P(y))) ® (
Ù P(y))); м) (R(x, y) «
) ® R(x, x).
ГЛАВА III. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ
Формальные теории ИВ и ИП
1. Докажите, что все аксиомы формального ИВ тождественно истинны.
2. Докажите, что тождественно истинны все аксиомы формального ИП.
3. Докажите следующие теоремы исчисления высказываний:
а) 
А Ù B ® B Ù A; б) 
B ® (A ® B Ù A); в) A Ú 
® Ú A; г) 
;
д) (A Ù B ® C) ® (A ® (B ® C)); е) (A ® B) ® ((C ® A) ® (C ® B)).
4. Докажите следующие теоремы исчисления предикатов:
(" z Q(z, t)) ® ($ t Q(t, p)), ($ x P(x, y)) ® ($ y P(y, x)), (" x P(x, y)) ® ($ y P(y, x)),
($ z Q(z)) ® ($ t Q(t)), R(x) ® ($ z R(z)), ((" x P(x, y)) Ù R(y)) ® (" t (P(t, y) Ù R(y))).
5. Докажите следующие теоремы исчисления предикатов:
(" x P(x, y)) «(" z P(z, y)), ($ x P(x, y)) «($ z P(z, y)),
(" x (" y P(x, y, z))) «(" y Î A (" x Î A P(x, y, z))),
($ x ($ y Î A P(x, y))) «($ y Î A ($ x P(x, y))),
«($ x 
(x, y)), ($ x P(x, y)) «
,
«(" x 
(x, y)), (" x P(x, y)) «
,
(" x P(x, y)) Ù (" x Q(x, y)) «(" x (P(x, y) Ù Q(x, y))),
($ x P(x, y)) Ú ($ x Q(x, y)) «($ x (P(x, y) Ú Q(x, y))),
((" x Р(х, y)) Ú R(y)) «(" x (P(x, y) Ú R(y))),
(($ x Р(х, y)) Ú R(y)) «($ x (P(x, y) Ú R(y))),
((" x Р(х, y)) Ù R(y)) «(" x (Р(x, y) Ù R(y))),
(($ x Р(х, y)) Ù R(y)) «($ x (Р(x, y ) Ù R( y ))),
(" х (R(y) ® Р(х, y)) «(R(y) ® (" x Р(х, y))),
($ х (R(y) ® Р(х, y))) «(R(y) ® ($ x Р(х, y))).
(R(y) не зависит от x)
6. Рассмотрим следующую теорию T:
алфавит: {x, Ú, (,)};
формулы: x – формула и, если A, B – формулы, то (A Ú B) – формула, других нет;
аксиомы: x;
правило вывода: 
;
Докажите, что
· формула доказуема в теории Т тогда и только тогда, когда она является дизъюнкцией нескольких экземпляров переменной x с любой расстановкой скобок;
· теория T непротиворечива;
· теория T разрешима.
Полна ли теория T в широком смысле? А в узком?
7. Расширим теорию T до теории S:
алфавит: {x, 
, Ù, Ú, 
(,)};
формулы: x и – формулы и, если A, B – формулы, то , (A Ù B), (A Ú B) – формулы, других формул нет;
аксиомы: x;
правило вывода: ;
Докажите, что
· формула доказуема в теории S тогда и только тогда, когда она является дизъюнкцией нескольких экземпляров переменной x с любой расстановкой скобок;
· теория S непротиворечива;
· теория S разрешима.
Полна ли теория S в широком смысле? А в узком?
8. Приведите пример полной теории (в узком, но не широком смысле; широком, но не узком смысле; в обоих смыслах).
9. Приведите пример противоречивой теории. Она разрешима? Полна ли она?
