Раздел 2. Исчисление предикатов

Задача 2. 1

Выразить перечисленные ниже символьные высказывания словами, если Р(х)- одноместный предикат, определенный на множестве М:

1. "х P(x)

2. $x P(x)

3. "x_ùP(x)

4. $x_ùР(x)

Задача 2. 2

Что произойдет с экстенсионалом предиката А(x), который определен как неравенство x*x<2*x-1, если обе стороны этого неравенства умножить на k, где k:

1. k>0

2. k<0

3. k=0

Задача 2. 3

Пусть R(x) - "x -действительное число",

Q(x) - "x -рациональное число". Используя эти символы, записать формульно:

1. все рациональные числа действительны

2. ни одно рациональное число не является действительным

3. некоторые рациональные числа являются действительными

4. некоторые рациональные числа не являются действительными

Задача 2. 4

Введены следующие предикаты:

J(x)- "x - судья",

L(x)- "x - юрист",

S(x)- "x - жулик",

Q(x)- "x - старик",

V(x)- "x - бодрый",

P(x)- "x - политик",

C(x)- "x - член парламента",

W(x)- "x - женщина",

U(x)- "x - домашняя хозяйка",

А(x, y) - "x восхищается y",

j - Джонс.

Найти соотвествие между словестным описанием и формулами:

1. Все судьи - юристы

2. Некоторые юристы - жулики

3. Ни один судья не является жуликом

4. Некоторые судьи - старики, но бодрые

5. Судья Джонс не стар и не бодр

6. Не все юристы судьи

7. Некоторые юристы, являющиеся политиками, члены парламента

8. Ни один член парламента не бодр

9. Все старые члены парламента - юристы

10. . Некоторые женщины одновременно являются юристами и членами парламента

11. Ни одна женщина не является одновременно политиком и домашней хозяйкой

12. Некоторые женщины - юристы, являются одновременно и домашними хозяйками

13. Все женщины - юристы, восхищаются каким-либо судьей

14. Некоторые юристы восхищаются только судьями

15. Некоторые юристы восхищаются женщинами

16. Некоторые жулики не восхищаются ни одним юристом

17. Судья Джонс не восхищается ни одним жуликом

18. Существуют как юристы, так и жулики, которые восхищаются судьей Джонсом

Только судьи восхищаются судьями

a. $x $y (L(x)/\S(y)/\A(x, j)/\A(y, j)/\J(j))

b. "x (J(x)® "y (A(x, y) ®J(y)))

c. "x (C(x) ® _ù "(x))

d. "x (C(x)/\Q(x) ®L(x))

e. $x (W(x)/\L(x)/\C(x))

f. $x (W(x)/\L(x)/\U(x))

g. "x (W(x) ® _ù(P(x)/\U(x)))

h. "x (W(x)/\L(x) ®$y (J(y)/\A(x, y)))

j. "x (J(x) ®L(x))

k. $x (L(x)/\ $y (W(y)/\A(x, y)))

l. $x (L(x)/\S(x))

m. $x (S(x)/\ "y (L(y)/\ _ùA(x, y)))

n. "x (J(x) ® _ùS(x))

o. "x (J(j)/\ _ùA(j, x)/\S(x))

p. $x (J(x)/\Q(x)/\"(x))

q . $x (L(x)/\ $y (W(y)/\A(x, y)))

r. J(i)/\ _ùQ(j)/\ _ù"(j)

s. _ù"x (L(x) ®J(x))

t. $x (L(x)/\P(x)/\C(x))

Задача 2. 5

Перевести на язык формул следующие фразы:

1. если всякое число делится на всякое число, то оно четное

2. для каждого действительного числа х существует такое у, что для каждого к, если сумма к и 1 меньше у, то сумма х и 2 меньше 4

3. найдется такое четное число, которое делится на любое число, если это любое число - простое

4. наибольший общий делитель чисел а и b делится на всякий их общий делитель

5. для того, чтобы любое число было простым, необходимо, чтобы оно не делилось на любое нечетное число

6. для всякого действительного числа существует большее действительное число

7. существуют такие действительные числа х, у, к, что сумма чисел х и у больше, чем произведение чисел х и к.

8. если произведение конечного числа сомножителей равно 0, то по крайней мере один из сомножителей равен 0

Задача 2. 6

Введены следующие предикаты:

P(x) - "х - простое число"

E(x) - "х - четное число"

O(x) - "х - нечетное число"

D(x, y) - "у делится на х"

Перевести формулы на русский язык:

1. P(7)

2. E(2)/\P(2)

3. "x (D(2, x) ®E(x))

4. $x (E(x)/\D(x, 6))

5. "x (_ùE(x) ®_ùD(2, x))

6. "x (E(x)/\"y (D(x, y) ®E(y)))

7. "x (P(x) ®$y (E(y)/\D(x, y)))

8. "x (O(x) ®*y (P(y) ®_ùD(x, y)))

Задача 2. 7

Доказать следующие эквивалентности:

1. = $x (A(x) ®B(x))¬®"x (A(x) ®$x B(x))

2. = $x (A(x) ¬®B(x)) ¬®"x (A(x)\/B(x)) ® $x (A(x)/\B(x))

Задача 2. 8

Доказать следующие тавтологии:

1. = "x A(x)® $x A(x)

2. = _ù"x A(x)¬® $x_ùA(x)

3. = $x A(x) ¬®_ù"x_ùA(x)

Задача 2. 9

Получить предикатные выражения в правильной нормальной форме:

1. "x(("y F(x, y)/\ "y G(x, y, z))\/ "y$z H(x, y, z))

2. $x(_ù($y P(x, y) ®$z Q(z) ®R(x)))

Задача 2. 10

Привести к конъюктивной нормальной форме выражение:

"x (P(x) ®("y (P(y) ®P(f(x, y)))) /\

/\ _ù (""y (Q(x, y) ®P(y))))

Задача 2. 11

Построить истинностные таблицы для следующих формул (предикаты определены на множестве из двух элементов):

1. "x(P(x) ®Q)\/(Q/\P(y))

2. "x(S(x) ®L)¬® $x(S(x) ®L)

3. "x $y((B(x)/\D(y))\/(B(x) ®C))

4. "x P(x) ¨S)/\(P(y)\/S)

5. ($x D(x)/\A) ¨( $x E(x)\/A)

6. ("x A(x) ®Q) \/ (Q®$x A(x))

7. (A(y)\/Q)¨( $x A(x)/\Q)

Задача 2. 12

Дано: D={a, b}, P(a, a)=и, P(a, b)=л, P(b, a)=л, P(b, b)=и Определить истинностные значения формул:

1. "x $y P(x, y)

2. $x "y P(x, y)

3. "x "y (P(x, y) ®P(y, x))

4. "x "y P(x, y)

5. $y _ùP(a, y)

6. "x P(x, x)

7. "x $y (P(x, y)/\P(y, x))

8. $x "y (P(x, y) ®P(y, x))\/P(x, y)

Задача 2. 13

Проверить на логичность следующие рассуждения:

1. Каждый студент честен. Джон не честен. Значит, Джон не студент.

2. Святого Франциска любит каждый, кто любит кого-нибудь. Каждый кого-нибудь да любит. Следовательно, Святого Франциска любит каждый.

3. Ни одно животное не бессмертно. Кошки - животные. Значит, некоторые кошки не бессмертны.

4. Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев.

5. Все политики - лицедеи. Некоторые лицедеи - лицемеры. Значит, некоторые политики - лицемеры.

6. Глупец был бы способен на это. Я на это не способен. Значит, я не глупец.

7. Если кто-нибудь может решить эту задачу, то и какой-нибудь математик мог бы. Саша - математик, а не может. Значит, проблема не разрешима.

8. Всякий математик может решить эту задачу, если кто-нибудь может ее решить. Саша - математик, а не может решить. Значит, проблема неразрешима.

9. Всякий, кто может решить эту задачу - математик. Саша не может ее решить. Следовательно, Саша не математик.

10. Всякий, кто может решить эту задачу - математик. Ни один математик не может решить эту задачу. Следовательно, она неразрешима.

11. Если какое-нибудь число, лежащее строго между 1 и 101, делит 101, то простое число, меньшее 11, делит 101. Ни одно простое число, меньшее 11, не делит 101. Значит, ни одно число между 1 и 101 не делит 101.

12. Если всякий предок предка данного индивидуума есть также предок того же индивидуума и никакой индивидуум не есть предок самого себя, то должен существовать некто, не имеющий предков.

13. Для любого человека найдется человек, который старше его. Если - x потомок y, то x не старше y. Все люди потомки Адама. Следовательно, Адам не человек.

14. Для любого множества x существует множество y такое, что мощность y больше мощности x. Если x включено в y, то мощность x не больше мощности y. Всякое множество включено в V. Следовательно, V не множество.

15. Все пресмыкающиеся имеют 4 ноги, либо вообще не имеют ног. У лягушки 4 ноги. Значит, она пресмыкающееся.

16. Всякий студент, сдавший сессию вовремя, получает стипендию. Петров стипендию не получает. Следовательно, он не студент.

17. Все птицы несут яйца. Ни один крокодил не является птицей. Следовательно, крокодилы не несут яиц.

18. Преподаватель доволен, если все его студенты сдают экзамен с первой попытки. Никто не может сдать логику с первой попытки. Следовательно, преподаватель логики всегда недоволен.

19. Всякий пятикурсник получает диплом, если он сдал все экзамены. Диплом получили не все. Значит, кто-то не сдал все экзамены.

20. Ни один человек не любит насекомых. Пауки - не насекомые. Значит, их кто-то любит.

21. Все учителя рисования - мужчины. Все уроки в младших классах проводят женщины. Следовательно, в младших классах не учат рисованию.

22. Всякий, кто окончил школу, может говорить по-английски. Никто в семье Мюллера не говорит по-английски. Людей без среднего образования не принимают в институт. Следовательно, ни один из Мюллеров не учится в институте.

23. Все бензоколонки рентабельны. Все пункты приема посуды убыточны. Предприятие не может быть одновременно и рентабельным, и убыточным. Следовательно, ни на одной бензоколонке не принимают бутылки.

24. Всякий, кто находится в здравом уме, может понимать математику. Ни один из сыновей Тома не может понимать математику. Сумасшедшие не допускаются к голосованию. Следовательно, ни один из сыновей Тома не допускается к голосованию.

25. Всякий парикмахер в N бреет всех тех и только тех, кто не бреется сам. Следовательно, в N нет ни одного парикмахера.

26. Каждый атлет силен. Каждый, кто силен и умен, добивается успеха в жизни. Петр атлет. Петр умен. Следовательно, он добьется успеха в жизни.

Задача 2. 14

Восстановите пропущенные посылки или заключение так, чтобы следующие рассуждения были логичны:

1. Только храбрецы достойны любви. Ему везет в любви. Он не храбрец.

2. Взрослых пускали только с детьми. Меня пустили. Значит, я либо ребенок, либо пришел с ребенком.

Задача 2. 15

Справедливы следующие утверждения:

1. знание структуры данных необходимо для совершенствования дисциплины ума;

2. только опыт программирования может создать дисциплинированный ум;

3. для того, чтобы написать компилятор, надо иметь возможность анализировать задачи;

4. недисциплинированный ум не может анализировать задачи;

   всякий, кто писал структурные программы, может рассматриваться как опытный программист.

Можно ли из этих предположений определить справедливость нижеследующих утверждений:

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

7. знание структур данных является частью опыта программирования;

8. анализ задач не возможен теми, кто игнорирует структуры данных;

9. опытный программист, который писал структурные программы, в состоянии анализировать задачи и имеет дисциплинированный ум, является программистом, который мог бы написать компилятор.

Задача 2. 16

Записать посылки в виде формул и применить все известные методы для доказательства правильности заключений.

Посылки: 1. дракон счастлив, если все его дети могут летать;

2. зеленый дракон может летать;

3. дракон зеленый, если, по крайней мере, один из его родителей зеленый, а иначе он ярко-розовый.

Заключения: 1. Зеленые драконы счастливы.

2. Бездетные драконы счастливы (здесь вам могут понадобиться некоторые очевидные пропущенные посылки).

3. Что делать ярко-розовому дракону для того, чтобы быть счастливым?

Задача 2. 17

Пользуясь символами, введенными для предикатов, и арифметическими знаками (например, "+" и "<"), перевести на язык формул:

1. Если произведение конечного числа сомножителей равно нулю, то по меньшей мере один из сомножителей равен нулю (Px обозначает "х есть произведение конечного числа сомножителей", а Fxy - "х есть один из сомножителей числа у").

2. Наибольший общий делитель чисел a и в делится на всякий их общий делитель (Fxy обозначает "х есть один из делителей числа у", а Gxyz - "z есть наибольший общий делитель чисел х и у").

3. Для всякого действительного числа х существует большее действительное число y(Rx).

4. Существуют такие действительные числа х, у, z, что сумма чисел х и у больше, чем произведение чисел х и z.

5. Для каждого действительного числа х существует такое у, что для каждого z, если сумма z и 1 меньше у, то сумма х и 2 меньше 4.

Задача 2. 18

Пусть А0, А1, ..., Аn, ... представляет собой последовательность действительных чисел. С помощью ограниченных кванторов перевести в символическую форму:

1. Утверждение, что а есть предел этой последовательности; 2. Утверждение, что эта последовательность имеет предел; 3. Утверждение, что эта последовательность есть последовательность Коши (т. е. что если дано е>0, то существует такое положительное число k, что из n, m>k вытекает úAn - Amú < e).

Написать отрицание каждой из формул.

Задача 2. 19

Построить выводы, соответствующие следующим рассуждениям:

1. Ни один республиканец или демократ не является социалистом. Норман Томас - социалист. Следовательно, он не республиканец.

2. Всякое рациональное число есть действительное число. Существует рациональное число. Следовательно, существует действительное число.

3. Ни один первокурсник не любит второкурсников. Все, живущие в Даскомбе, - второкурсники. Следовательно, ни один первокурсник не любит никого из живущих в Даскомбе.

4. Некоторые первокурсники любят всех второкурсников. Ни один первокурсник не любит никого из студентов предпоследнего курса. Следовательно, ни один второкурсник не является студентом предпоследнего курса.

5. Некоторым нравится Элвис. Некоторые не любят никого, кому нравится Элвис. Следовательно, некоторых любят не все.

6. Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекались к ответственности. Следовательно, некоторые люди, привлекавшиеся к ответственности, не являются торговцами наркотиками.

7. Все первокурсники встречаются со всеми второкурсниками. Ни один первокурсник не встречается ни с одним студентом с предпоследнего курса. Существуют второкурсники. Следовательно, ни один второкурсник не является студентом предпоследнего курса.

8. Все рациональные числа являются действительными числами. Некоторые рациональные числа - целые числа. Следовательно, некоторые действительные числа - целые числа.