Занятие №3

Тема: Алгебра предикатов.

I.Ответьте на следующие вопросы.

1. Дайте определение n-местного предиката. Приведите примеры.

2. Что называется множеством истинности предиката?

3. Какие предикаты называются равносильными?

4. Дайте определение тождественно-ложного, тождественно-истинного, выполнимого предиката.

5. Дайте определения кванторов (существования , всеобщности ).

6. Какие операции можно выполнять в логике предикатов?

7. Что называется формулами алгебры предикатов?

8. Определите понятия связной и свободной переменных. Какие формулы называются замкнутыми?

9. Какие формулы логики предикатов называются равносильными? Запишите основные равносильности алгебры предикатов.

10. Дайте определения приведенных и предваренных нормальных формул алгебры предикатов.

II.Выполните следующие упражнения:

1. Установите, какие из следующих предложений являются предикатами, а какие - высказываниями:

а) ;

б) , ;

в) , ;

г) ;

д) , ;

е) , ;

ж) , ;

з) , .

2. Определите, какие из следующих предикатов являются тождественно-истинными на множестве действительных чисел R:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и) ;

к) .

3. Определить множество истинности следующих предикатов, заданных на множестве :

а) «x – простое число»;

б) «»

в) «»;

г) «»;

д) «»;

е) «».

4. Для следующих предикатов, определенных на множестве А, составить таблицу значений и определить множество истинности (ложности):

а) «», ;

б) «x делит y», ;

в) «», ;

г) «», ;

д) «», ;

е) «», ;

ж) «», ;

з) «», ;

и) «», ;

к) « - четное число», .

5. Выписать все подформулы следующих формул:

а) ;

б) ;

в) ;

г) .

6. Какие вхождения переменных являются свободными, а какие связными в следующих формулах:

а) ;

б) ;

в) ;

г) .

7. Пусть предикаты N(x), С(x), P(x), П(x), Ч(x), Д(x, y) имеют соответственно смысл: x – натуральное число, x – целое число, x – простое число, x - положительное число, x - четное число, x делит y. Сформулировать смысл следующих формул логики предикатов и указать, являются ли они тождественно истинными:

а) x (N(x) Þ C(x));

б) x (C(x) Ù П(x) Þ N(x));

в) x (P(x) Þ ($ y (Ч(x) Ù Д(x, y))));

г) x (Ø Ч(x) Þ (" y (P(x) Þ Ø Д(x, y)))).

д) x (P(x) Ù Ч(x)).

е) x (С(x) Þ Ч(x) Ú Ø Ч(x))

ж) x (N(x) Ú Ч(x) Þ П(x)).

8. Прочитайте следующие формулы (запишите на естественном языке) и установите их истинность (ложность) на соответствующих множествах:

а) , где «x делит y», ;

б) , где , «x делит y»,

«x – четное»;

в) , где «x – натуральное число»,

«x – простое число»;

г) , где «x - помидор»,

«x - овощ», «x - растение».

9. Запишите следующие предложения в виде формул алгебры предикатов, выделите в них субъекты и предикаты:

а) каждое рациональное число есть действительное число;

б) существует четное число, которое является простым;

в) для каждого числа х существует такое число у, что х < у.

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

10. Перед следующими предикатами поставьте соответствующие кванторы так, чтобы получились высказывания, истинные на множестве действительных чисел:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

11. Для следующих формул установите их истинность (ложность) на множестве А, если:

a) «», ;

b) «», ;

а) «», ;

б) «», ;

в) «», ;

12. Пользуясь кванторами, запишите четыре вида высказываний относительно одних и тех же свойств P и Q, различающихся характером общности:

a) общеутвердительное – «все P суть Q»;

b) частноутвердительное – «некоторые P суть Q»;

c) общеотрицательное – «ни одно P не суть Q»;

d) частноотрицательное – «некоторые P не суть Q».

13. Пусть , где N – множество натуральных чисел, , .

1. запишите формулу с одной свободной переменной x, истинную в m тогда и только тогда, когда:

a) ;

b) ;

а) x – простое число

б) ;

в) ;

г) .

2. запишите формулу с двумя свободными переменными x и y, истинную в m тогда и только тогда, когда:

a) ;

а) ;

б) ;

в) x делит y.

3. запишите формулу с тремя свободными переменными x, y, z, истинную в m тогда и только тогда, когда:

a) ;

b) ;

а) .

4. запишите замкнутую формулу

а) коммутативность сложения;

б) ассоциативность сложения;

в) дистрибутивность умножения относительно сложения;

г) коммутативность умножения;

д) ассоциативность умножения;

е) бесконечность множества простых чисел;

ж) то, что всякое четное число, большее 2, есть сумма простых чисел;

з) то, что уравнение имеет в точности два различных корня;

и) то, что система уравнений , не имеет решения;

к) то, что для всякого числа существует строго большее число.

14. Выполнимы ли следующие формулы:

a) ;

b) ;

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) .

15. Являются ли следующие формулы тождественно истинными (ложными), выполнимыми:

a) ;

b) ;

c) ;

d) ;

e) ;

а) ;

б) ;

в) ;

г) ;

д) .

16. Доказать тождественную истинность следующих формул:

a) ;

b) ;

c) ;

d) ;

e) ;

f) ;

g) ;

а) ;

б) ;

в) ;

г) .

17. Для следующих формул найти равносильную им приведенную форму:

a) ;

b) ;

c) ;

d) ;

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

18. Привести к пренексной нормальной форме следующие формулы:

a) ;

b) ;

c) ;

d)

e) ;

а) ;

б) ;

в) ;

г) ;

д) .