Образцы практических заданий к зачёту
1. Любым образом восстановите скобки и запятые так, чтобы получились формулы логики предикатов:
z P z y Ú Q x f a,
P g a b x Ú$xØ" y Q x h y a
$z Q x f a b ®" z Ø R z x y ÙØ Q z x y
ØØ$z" y $ x R a b x ÚØ Q g x y x ®ØØ$ z P x ÚØ Q h x y z b
2. Укажите области действия кванторов в формулах:
"x(P(g(x, y, b)) ®$yQ(x, h(y, x, a)))
$y(ØP(h(y, z)) Ù ((Ø"zQ(a, f(b, x, z), y) ®$x(R(x, y, g(x1)))) ® P(y)))
"х"y"z(R(g(x, y), a) ÚØQ(z, y)) ®$x(ØQ(z, x) ® ("yR(a, b, x) ÚØQ(x, y)))
$y((P(y, f(z)) Ú (Ø$x(Q(g(x), y) ®"z(ØQ(z, h(a)))) Ù R(x, h(y), z)))
(Ø"zPzÚØ$y(Q(g(x, z), y)) ®"x$y(R(x, y, h(z))) ®Ø$zØP(z, g(y))
3. Для каждой из схем формул образуйте несколько частных случаев:
"a"b$g (В ® (С ® (В Ù А)))
Ø$a (А «"b (В Ú С))
"b (А ÙØ$a (C®"g А))
(А Ù"a В) ®$b (А Ù В)
4. Укажите свободные вхождения переменных:
"xQ(x, f(y, x))) ®$z(ØP1хÙQ(y, h(a, z))),
$z(ØR(f(x, z), b) ÙPz)) ® ($x("yQ(y, x) ®R(z, x)))
"x"y(P(x, f(z)) ÉØ$z(ØQ(z, y))) ÚR(f(x), g(y, z))
(Ø$yR(y, g(z), h(x)) É$z"x(ØP(f(x, y) ÚQ(x, y, h(z)))
5. Проверьте, являются ли корректными последовательные переименования переменных, в ходе которых из формулы (а) получена формула (б):
1) (а) "х(ØPxÉ$уQ(x, y, z))
(б) "y(ØPyÉ$yQ(y, y, z));
2) (а) $хØ"zQ(f(x), y, z)
(б) $zØ"zQ(f(z), y, z);
3) (а) "х($y(PyÚØ"zR(g(x, y), h(z)) É"yØQ(h(z), g(x, y)))
|
|
|
(б) "z($x(PxÚØ"zR(g(z, x), h(z)) É"xØQ(h(z), g(z, x)));
4) (а) $х(Ø"zQ(f(x), y, z) É$x"yØQ(h(x, y), g(z)))
(б) $z(Ø"xQ(f(z), y, x) É$y"xØQ(h(y, x), g(z))).
6. Последовательностью корректных переименований переменных, получите из формулы (а) формулу (б):
1) (a) "x($yQ(y, f(x) ÉØ"z(Q(x, h(y, z))
(б) "z($xQ(x, f(z)) ÉØ"x(Q(z, h(y, x));
2) (a) "х("zR(h(x, y), z) É"yØQ(h(x, y), g(z)))
(б) "х1("xR(h(х1, y), x) É"xØQ(h(х1, x), g(z)));
3) (а) $xP(x, f(y)) É (Ø"x($y(f(y), x) É$zØR(h(z), g(x, y)))
(б) $zP(z, f(y)) É (Ø"z($x(f(x), z) É$xØR(h(x), g(z, y))).
7. Будут ли корректны следующие подстановки:
1) терма f(x, y) вместо всех свободных вхождений z в формулу
"yQ(f(z), y) É$xP(x, h(z));
2) терма g(h(x), y) вместо всех свободных вхождений перменнойу в формулу
$z((PyÙØQ(x, h(y), z)) ÉØ"x(PxÚØQ(y, x)));
3) терма x вместо всех свободных вхождений переменной z в формулу
Ø$x(QxÉØ"y(P(h(z))) Ú"y(R(z) Ú Q(x, g(y), z)).
8. Используя определение истинности, выпишите условия истинности следующих формул в модели M при означивании v:
|
|
|
1) РхÚØQ(g(x, y), z),
2) "х$уQ(f(x, y), z),
3) $x(R(f(x, z), x) ÉØ"z(Q(z, x)).
9. Укажите несколько означиваний, при которых в модели M3, где D есть множество людей, Q[M3] – «познакомиться с... через...», g[M3] – «друг», h[M3] – «сестра», а[M3] – Ленский, имеет место M3, v╞═Q(g(x), h(у), а).
10. Пусть в модели M4, где D есть множество точек, Q[M4] – «лежать на одной прямой», R[M4] – «образовывать треугольник, при соединении линиями», f[M4] – «находящийся между». Выяснить, верно ли, что
M4╞═"х"у(($zØQ(f(x, y), f(x, z), х) É R(x, f(x, y), f(x, z))).
11. Докажите, что эти формулы не являются общезначимыми.
1) ($хРхÙ$xQ(x, y)) É$x(РхÙ Q(x, y));
2) "х(РхÉ$уQ(х, у)) É"х"уQ(х, у);
3) "х(РхÉ"уРу).
12. Используя определение истинности и семантические леммы, докажите, что следующие формулы из приведенного выше списка общезначимых формул действительно являются таковыми:
– второго закона взаимовыразимости кванторов,
– законов отрицания кванторов,
– законов перестановки кванторов,
– законов вырожденных кванторов,
– законов на вынесение и пронесение кванторов.
13. Сформулируйте доказательтства теоремы эквивалентности для случаев, когда А имеет вид (В Ú С), (В É С), (В º С), $bВ.
|
|
|
14. Приведите эти формулы к ПНФ:
($уQ(x, a) ÉØ"z(R(z, f(y))) É$xØPx)
Q(x, g(y, z)) Ú"y($xØPxÉ$zR(x, z, g(z, a)))
$x(R(x, z) É"yPy) É"x($zR(x, z) É$yPy)).
15. Докажите с помощью семантических таблиц общезначимость следующих формул (поскольку это не сами формулы, а схемы формул, общезначимость будет относиться к любому их частному случаю):
1) "aА ÉАt;
2) АtÉ$aА;
3) $aА ºА, если А не содержит свободных вхождений a;[1]
4) $a (А Ù В) º (А Ù$aВ), если А не содержит свободных вхождений a;
5) $a (А Ú В) º ($aА Ú$aВ);
6) ("aА Ú"aВ) É"a (А Ú В);
7) "a (А Ú В) º (А Ú"aВ), если А не содержит свободных вхождений a;
8) "a (А É В) º ($aА É В), если В не содержит свободных вхождений a;
9) ($aА É$aВ) É$a (А É В);
10) $a (А É В) º (А É$aВ), если А не содержит свободных вхождений a;
11) $a (А É В) º ("aА É В), если В не содержит свободных вхождений a;
16. Проведите табличное построение для следующих формул и по одной из незамкнутых подтаблиц постройте контрмодели для каждой из них (в такой контрмодели все формулы, написанные в незамкнутой подтаблице слева, должны быть истинными, а все формулы, написанные справа, – ложными):
|
|
|
1) "a(А É В) É$a(А Ù В);
2) "х(РхÉ ("у(QуÉ (РхÉQу)) Ú"zPz);[2]
3) "a (А Ú В) É ("aА Ú"aВ);
4) $у($xQ(x, y) É"xQ(x, y)).
17. Докажите в АИП следующие формулы (если необходимо, используйте в доказательстве ранее доказанные формулы):
1) "x(Q(x, y) É R(z, x)) É ($xQ(x, y) É$xR(z, x));
2) "x(PxÙ Q(x, y)) º ("xPxÙ"xQ(x, y));
3) "у($xRxÉPy) из $xRxÉ"xPx;
4) $x(PzÙ Q(x, f(y)) º (PzÙ$xQ(x, f(y));
18. Постройте схемы доказательства для следующих схем формул (такая схема превращается в доказательство при придании значений метапеременным):
1) ($aА É$aВ) É$a (А É В);
2) $a (А É В) º (А É$aВ), где А не содержит свободных вхождений a;
3) ("aА Ú"aВ) É"a (А Ú В);
4) "aА É"bА;
5) "a(А º В) É ("aА º"aВ);
6) $aС из $a(А É В) и "aВ.
17. Докажите, что правило обобщения, правило индивидуации и варианты правил R"и R$ производны в АИП.
18. Приведем еще одну формулировку исчисления предикатов (АИП*) и предлагаем читателю доказать ее равнообъемность (дедуктивную эквивалентность) АИП. (Доказательство равнообъемности двух исчислений сводится к доказательству выводимости всех аксиом АИП* в АИП и доказательству проиводности правил вывода АИП* в АИП и наоборот.)
Определение: $aА ºDf Ø"aØА.
1. Аксиомы ИВ
2. Кванторные аксиомы
"aА ÉАt, где Аt есть А(a/t)
"a(А É В) É (А É"aВ), где А не содержит свободных вхождений a.
3. Правила вывода МР и правило обобщения (G): А/"aА.
4. Правило построения доказательства и определения теоремы те же, что и в АИП.
Дата добавления: 2018-05-01; просмотров: 238; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!