2. Приведем соответствующие формулы:
а) x£y&Øy£x,
б) x<y&("z)(x<z&z£y®z=y),
в) ("y)(x£y),
г) ($z)("y)[z£y&("u)(z<u&u£x®u=x)]
д) (x<y&y<z)Ú(z<y&y<x).
3. Приведем соответствующие формулы:
а) ("y)(x|y),
б) z|x&z|y&("u)(u|x&u|y®u|z),
в) x|z&y|z&("u)(x|u&y|u®z|u),
г) Ø(x=1)&("y)(y|x®y=1Úy=x).
Предикаты «x – четное число» и «x меньше y» невыразимы формулой сигнатуры s.
Докажем это. Пусть P –
множество простых чисел. Рассмотрим отображение j:P®P такое, что j(2)=3,
j(3)=2
и j(p)=p для всех простых чисел p, отличных от 2 и 3.
Отображение j
расширим на все множество натуральных чисел N следующим
образом: Пусть n=2a3bp1g1…pkgk, где p1,…,pk – простые числа,
отличные от 2 и 3. Положим:
j(n)=3a2bp1g1…pkgk и j(1)=1.
Например, j(2)=3, j(12)=18, j(42)=42, j(60)=90. Отображение j
сохраняет предикат делимости. Это означает, что
u|vÛj(u)|j(v)
для любых u,vÎN. Индукцией по
построению формулы можно доказать, что для любой формулы F(x1,…xn)
сигнатуры s и
любых натуральных чисел а1,…аn высказывание F(а1,…аn) истинно тогда и только тогда, когда истинно F(j(a1),…,j(an)). Предположим
теперь, что предикат «x
– четное число» определяется формулой G(x).
Тогда высказывание G(2)
истинно тогда и только тогда, когда G(3) истинно. Но G(2)
истинно, а G(3) ложно.
Полученное противоречие доказывает, что предикат «x – четное число» невыразим формулой
сигнатуры s.
Аналогично доказывается невыразимость предиката «x меньше y».
4. Соответствие формул предикатам
содержится в следующей таблице:
Формула |
а |
б |
в |
г |
д |
Предикат |
в |
б |
а |
д |
г |
5. Приведем соответствующие формулы:
а) ($x)P(x),
б) ("x)("y)(P(x)&P(y)®x=y),
в) ($x)[P(x)&("y)P(y)®x=y)],
г) ($x)($y)[x¹y2&P(x)&P(y)],
д) ("x)("y)("z)[P(x)&P(y)&P(z)&®x=yÚx=zÚy=z],
е) ($x)($y)[x¹y&P(x)&P(y)&("z)(P(z)®x=zÚy=z)].
6. Приведем соответствующие формулы:
а) pl(x)&pl(y)&($z)(p(z)&zÎx&zÎy),
б)pl(x) )&pl(y)&[(
$z)p(z)&zÎx&zÎy)®($u)(l(u)&uÎx&uÎy)],
в)l(x)&l(y)&($z)(p(z)&zÎx&zÎy),
г) l(x)&l(y)&($u)(pl(u)&xÎu&yÎu)&Ø($v)(p(v)&vÎx&vÎy),
д)l(x)&l(y)&l(z)&($u)($v)($w)[p(u)&p(v)&p(w)&uÎx&uÎy&vÎx&vÎz&wÎy&wÎz&u¹v&u¹w&v¹w].
7. Приведем решение залачи 7.3. Пусть T(x) означает «x – таможенник», B(x) –»x
въезжает в страну», Л(x)
– «x высокопоставленное
лицо», H(x) – «x способствует провозу наркотиков», O(x,y) – «x
обыскивает y». Тогда
рассуждение 7.3 может быть переведено на язык логики первого порядка
F1=("x)[B(x)&ØЛ(x)®($y)(T(y)&O(y,x))],
F2=($x)[B(x)&H(x)&("y)(O(y,x)®H(y))],
F3=Ø($x)[Л(x)&H(x)),
G=($x)(T(x)&H(x).
8. Формуле F(x,y)
соответствуют следующие предикаты:
а) «x меньше y
и между ними находится в точности один элемент»,
б) «x меньше
или равно y»,
в) «x=1 и y=4»,
г) «x¹x»,
т.е. тождественно ложный предикат.
9. Формуле F(x) соответствуют следующие предикаты:
а)»x – простое
число»,
б) «x – равно
2»,
в) «x равно 1».
10. Формуле F(x) соответствуют следующие предикаты:
а) «x – равно
0»,
б) «x – равно
1»,
в) «x – равно
1».
11. Формуле F(x) соответствуют следующие предикаты:
а) «x – равно
2»,
б) «x – равно 3»,
в) «x – равно
2».
Предикат «x=4»
соответствует формуле F(x) при интерпретации P(x)=«x=4», D(x,y)=«x больше или
равно y», а предикат «x – четное число» соответствует этой формуле при
интепретации P(x)=«x – четное число» и D(x,y)=«x=x».
12. Формулы равносильны только в
случаях г и е.
13. Приведем решение задачи 13в. Пусть
F=("x)[("y)P(x,y)®($z)(P(x,z)&Q(z))] и
G=("x)($u)[P(x,u)®Q(u)].
Применим к формуле F последовательно законы 20 и
26, получим формулу
F1=("x)[($y)ØP(x,y)Ú($z)(P(x,z)&Q(z).
Затем, пользуясь законом 33, в
формуле ($y)ØP(x,y) y
заменим на u, а в
формуле ($z)(P(x,z)&Q(z)) z заменим тоже на u. Формула F1 после этих замен
превратится в формулу
F2=("x)[($u)ØP(x,u)Ú($u)(P(x,u)&Q(u))].
Применив закон 23, вынесем
квантор вперед:
F3=("x)($u)[ØP(x,u)Ú(P(x,u)&Q(u))]
Используя последовательно законы
12,16 и 1, получим формулу:
F4=("x)($u)[ØP(x,u)ÚQ(u)].
Осталось заметить, что в силу
закона 20 формула ØP(x,u)ÚQ(u) равносильна формуле P(x,u)®Q(u). Равносильность F и G доказана.
14. Указание. Воспользоваться
алгоритмом приведения к ПНФ (см.§6).
15. Указание. Воспользоваться
алгоритмом приведения к СНФ (см.§6).
16. Приведем решение задачи 16в. Надо
построить интерпретацию, при которой формулы из K истинны, а формула из G ложна. Рассмотрим множество
M={1,2,3} и
интерпретацию j:(jP)(x)=«x=1», (jQ)(x)=«x=2», (jR)(x)=«x=1 или x=2»,
(jS)(x,y)=«x=1 и y=2».
Легко проверить, что j
–
искомая интерпретация.
17. Логическим следствием будет только
утверждение б.
18.
Приведем решение задачи 18.1. Пусть St(x)
означает, что «x –
студент
нашей группы», M(x) – «x –
член клуба «Спартак»«, Sp(x) – «x занимается спортом». Тогда рассуждение
18.1 переводится на язык логики первого порядка последовательностью формул:
F1=("x)(St(x)®M(x)),
F2=($x)(M(x)&Sp(x)),
G=($x)(St(x)&Sp(x)).
Рассмотрим множество M={1,2,3} и интерпретацию j: (jSt)(x)=«x=1», (jM)(x)=«x=1 или x=2», (jSp)(x)=«x=2». Легко видеть,
что j(F1)=j(F2)=1 и j(G)=0.
|