Предварённо-приведённая нормальная форма

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. Приведите пример противоречивой теории. Она разрешима? Полна ли она?