Формулы исчисления предикатов

1.Какое из выражений не будет формулой и почему ? Исправьте ошибки и определите, какими – свободными или связанными – будут все вхождения переменных в полученных формулах. Установите области действия всех кванторов.

а) ((a) U ($ x P(x));б) (a U ($ x P(x));г) (( x P(x, y)) U Q(x));д) (P(x) U Формулы исчисления предикатов (y));

д) (P(x) U Q(y, z)); е) ($ t Q(x) ® ( z P(z, t))); ж)(($ x P(x, y)) « ( y P(x, y)));

з) ( x Формулы исчисления предикатов ); и) (a ® ($ y R(x))); к) Формулы исчисления предикатов ; л) Формулы исчисления предикатов .

2.Определите, какими – свободными или связанными – будут все вхождения переменных в формулах, установите области действия всех кванторов:

а) ((a U b) ® ($ x P(x, y))); б) ( Формулы исчисления предикатов ® ( x P(x, y))); в) P(x) U ($ x P(x));

в) ((( P(x, y)) U P(x, x)) ® ($ y (P(x, y) U Q(x, y))))); г) ($ x (P(x) U (a ®b)) U P(x));

д) ( x ($ y (P(z, y) U ( z Q(z, x)))) ® R(x, z)); е) ( Формулы исчисления предикатов U ( z P(x, z))).

3.Формулы какого вида записываются одним символом алфавита ИП ? Какое наименьшее количество символов алфавита ИП потребуется, чтобы записать следующую по сложности формулу ИП ? Формулы какого вида остаются формулами, если дописать некоторый один символ алфавита ИП ? Есть ли формулы ИП, записываемые четырьмя, символами алфавита ИП ? А пятью ?

4.В следующих выражениях всеми способами так расставьте скобки, чтобы получились формулы:

а) $ y P x, y U S x ; б) a U b ® c; в) a Uy P x;г) a Uy R y ® Q x, y ;

д) Формулы исчисления предикатов ® a ® $ x P x, y ® Q x ;е) R x «z R z U P x, x .

5.Задайте предикаты и запишите в виде формул ИП следующие утверждения:

а) найдётся целое число x, для которого при любом действительном y существует такое целое число z, что y ³ z;

б) если xy, то для любого z верно z?xz?y;

в) если целое число x , а y – действительное, и x ³ y, то найдётся целое число z и действительное t со свойством z Формулы исчисления предикатов t;

г) если 52, то найдётся такое целое число, которое больше своего квадрата при условии, что его квадрат меньше нуля;

д) любое целое число из отрезка [0; 1] меньше всякого нецелого числа, большего 10;

е) в том случае, когда число больше своего квадратного корня, можно утверждать, что это число неотрицательное;

е) для того, чтобы произвольное целое число было положительным необходимо и достаточно, чтобы это число совпадало со своим модулем;

ж) 0Формулы исчисления предикатов или же найдётся Формулы исчисления предикатов ³ 0;

з) если квадрат целого числа положителен, то из того, что это число больше двух следует, что корень из него неположителен при условии, что любое неотрицательное число неположительно;

6.Задайте предикаты и запишите в виде формул ИП следующие утверждения:

а) нулеван положе корефана или же найдётся корефан помарчее нулевана;

б) любая понтажная чечка вихлястей непонтажной штуковинки;

в) найдётся ксёлик, для которого при любом игулике существует ксёлик полаханней игулика;

г) в том случае, когда мозлик болдажнее своего тюлика, этот мозлик болдажнее и кувальчика;

д) для того, чтобы дрючка была понтажной необходимо и достаточно, чтобы эта дрючка была незавязной;

е) если вырик и мамлютка зашканные, то найдётся вырик и мамлютка незамастые.

Интерпретации формул

1.Найдите ошибки в следующих интерпретациях формул:

а) ($ x P(x, y)), J = (M = N, a = 1, P(x, y) = (xy));

б) (a ® (( x P(x)) ® P(y))), J = (M = {0}, a = 5, P(x , y) = (x ? y));

в) ($ x P(x, y)), J = (M = N, P(x) = (x1));

г) (a ® (( x P(x)) ® P(y))), J = (M = {0}, a = 1, P(x) = (x0));

д) (($ x P(x, y)) ® ( y (P(x, y) U Q(y)))), J = (M = {1}, P(x, y)=(x | y), Q(y)=(y = 1));

е) ($ x P(x, y)), J = (M = R, P(x, y) = ( Формулы исчисления предикатов2));

ж) (P(x) ® Q(x, y)), J = (M = R, x = 1, y = 1+i, P(x) = (x2), Q(x, y)=(y = 1));

з) (P(x, y) ® P(y, x)), J = (M = R, x = 1, y = 1, P(x, y) = (xy), P(y, x)=(y = 1));

и) ( x (P(x, y) ® ($ y (P(y, y) U P(y, x))))), J = (M = R, x = 1, y = 0, P(x, y) = (x | y)).

2.Вычислите значения формул при интерпретациях:

а) ( x Q(x, y)), J = (M = N, y = 1, Q(x, y) = (x ³ y));

б) ( x Q(x, y)), J = (M = {0, 1}, y = 0, Q(x, y) = (xy));

в) ( x (Q(x, y) ® P(x)), J = (M = N, y = 2, Q(x, y) = (x = y), P(x) = (x ¹ 1));

г) ( x (Q(x, y) ® P(x)), J = (M = N, y = 2, Q(x, y) = (x = y), P(x) = (x ³ 1));

д) (b ® (($ x R(x)) ® R(y))), J = (M = {0, 1}, b = 0, y = 1, R(x) = (x ¹ 0));

е) (b ® (($ x R(x)) ® R(y))), J = (M = {0, 1}, b = 1, y = 1, R(x) = (x1));

ж) (($ x R(x, y)) ® R(y, x))), J = (M = {0, 1}, y = 1, ,x = 1, R(x, y) = (xy));

з) (($ x R(x, y)) ® R(y, x)), J = (M = {0, 1}, y = 0, x = 1, R(x, y) = (xy));

и) (P(x) ® ($ y P(y))), J = (M = R, x = 0, P(x) = (x0));

к) (P(x) ® ($ y P(y))), J = (M = R, x = 1, P(x) = (x0)).

3.Классифицируйте формулы: а) (P(x) U Q(x)); б) (Q(x) ® Q(y)); в) (a U ($ x R(x, y)));

г) (a « ($ x P(x, y))); д) (($ x Q(x)) U ( y (Q(y) U Q(x)))); е) (( y R(y)) ® R(x));

ж) ($ x ( y (P(x, y) ® Q(x)))); з) (( x ( y S(x, y))) ® S(z, z)); и) (P(x) ® Формулы исчисления предикатов );

к) Формулы исчисления предикатов ; л) (( x R(x)) ® R(y));м) (P(x) ® (a ® P(x))).

4.Являются ли следующие формулы тождественно истинными ?

а) (P(x) ® P(y));б) (($ x R(x)) U Формулы исчисления предикатов );в) (( x S(x)) ® ($ y S(y))); г) (a U P(x));

д) (a U (P(x) U Формулы исчисления предикатов ));е) (( x ( y Q(x, y))) ® ( x Q(x, x)));ж) (R(x) ® ( x R(x)));

з) ( x ((P(x) ® Формулы исчисления предикатов (x)) ® Формулы исчисления предикатов )); и) ( Формулы исчисления предикатов U A(x));

к) Формулы исчисления предикатов ® Формулы исчисления предикатов ; л) (($ x (P(x) ® Q(x))) « (( x P(x)) ® ($ x Q(x))).

5.Являются ли следующие формулы выполнимыми ?

а) (P(x) U Q(x)); б) (Q(x) « Q(y)); в) ( x (R(x) U S(x))); г) ($ x (P(x, y) U R(x))); д) ( x (($ y P(x, y)) U R(z))); е) Формулы исчисления предикатов ; ж) Формулы исчисления предикатов ® ($ x P(x));

з) (( x (P(x) ® a)) U ($ x (P(x) ® Формулы исчисления предикатов )));и) (( z T(z)) U (a U Формулы исчисления предикатов ).

6.Расставьте скобки так, чтобы полученные формулы не были выполнимыми:

а) $ x P(x) U Формулы исчисления предикатов ;б) R(x) ®y P(y) ® R(x);в)x S(x) ® S(y);е) a U P(x); д)x S(x) ® Формулы исчисления предикатов ;е) $ y Q(y, x) ® Q(x, y) Ux Q(x, x) U Формулы исчисления предикатов .

7.Приведите примеры выполнимых формул ИП, но тождественно ложных при любой интерпретации на а)одноэлементном множестве; б)двухэлементном множестве.

8.Существует ли формула ИП, истинная при интерпретации на любом двухэлементном множестве, но ложная при интерпретации на любом трёхэлементном множестве ?

Случайные записи:

Лекция 9: Логика. Исчисления высказываний и исчисление предикатов


Похожие статьи:

Добавьте постоянную ссылку в закладки. Вы можете следить за комментариями через RSS-ленту этой статьи.
Комментарии и трекбеки сейчас закрыты.