Примеры. Пусть М есть множество натуральных числе N

Пусть М есть множество натуральных числе N.

Тогда выражение «х – простое число», «х – четное число», «х – больше 10» являются одноместными предикатами. При подстановке вместо х натуральных числе получаются высказывания: «2 – простое число» и т.д.

Пример 2-местных предикатов:

x>y

x делит нацело у

x+y=2

Можно считать, что высказывание – нульместный предикат, т.е. предикат, в котором нет переменной для замены.

Предикат с заменяемыми переменными х1 … хn будем обозначать заглавной латинской буквой. После которй в скобках указаны эти переменные. Например, Р(х1,х2).

В логике предикатов дополнительно вводятся 2 новые операции:

1. " - квантор общности

2. $ - квантор существования

Пример. Пусть дано выражение «существует х такой, что х+у=10». На множестве натуральных чисел это предложение определяет одноместный предикат, хотя его можно представить следующим образом.

Если обозначить предикат «х+у=10» через S(x,y) (предикат двухместный), то P(y) можно записать так: «существует х такой, что S(x,y)»

В этом случае говорят, что предикат Р(у) получен из предиката S(x,y) навешиванием квантора существования.

Пример 2. Выражение «для всех х справедливо, что y>-x^2 определяет на множестве целых чисел одноместный предикат Q(y).

Если y>-x^2 обозначить Т(х,у) то можно записать так: Q(y)=("x)T(x,y).

Формулы логики предикатов

Термом называется:

1) переменная или константа

2) выражение вида f(t1,…,tn), t1…tn – термы, а f – n местный функциональный символ.

Терм – выражение, полученное из переменных и констант с помощью символов функций.

Атомарной формулой называется выражение вида r(t1…tn) где t1…tn – термы, r – символ н-местного предиката.

Формулой логики предикатов первого порядка – называется:

1) Атомарная формула

2) выражение вида (F)Ù(G), (F1)Ú(G), Ø(F), (F)Þ(G), (F)Û(G) где F and G – формулы логики предикатов.

("y)(F), ($x)(F), y, x – пременные.

Кванторы приоритетней логических связок. Вхождение переменной в формулу называется связанной если переменная стоит непосредственно за квантором или входит в область действия квантора по этой переменной. В противном случае вхождение переменной в формулу называется свободным.

F=t(x)Ù("y) [ S(x,y)Þ($x)(r(x,y)Út(y))]

Переменная называется свободной в формуле если имеется хотя бы одно свободное вхождение переменной в формулу.

Интерпретации используются когда необходимо соотнести формулы логики предикатов с их смысловым содержанием. Интерпретацией на непустом множестве М называется функция которая:

1) константе ставит в соответствие элемент множества М

2) символу н-местной функции ставит в соответствии н-местную функцию заданную на множестве М

3) Символу н-местного предиката ставит соответствии н-местный предикат заданный на множестве М.

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

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

1. Тот, кто посещает занятия, сдает экзамены на хорошо и отлично.

2. Тот, кто много знает, получает на экзамене хорошие отличные оценки.

3. Не существует того кто посещает занятия и не тратит много времени на учебу.

4. Каждый не тратит много времени на учебу или много знает.

Предикаты:

· Р(х) – х посещает занятие

· С(х) – х сдает экзамены на хорошо и отлично

· М(х) – х много знает

· Т(х) – х тратит много времени на учебу

Формулы логики предикатов:

("x)[P(x)ÞC(x)]

("x)[M(x)ÞC(x)]

Ø($x)[P(x)ÙØT(x)]

("x)[ØT(x)ÚM(x)]

Задание. Представить утверждения в виде формул логики предикатов

1. Любой отличник сможет стать президентом

2. Отличники всегда посещают лекции

3. Каждый, кто не узнает много интересного, не посещает лекции

4. Не существует того, кто узнает много интересного и мало знает

5. Каждый или мало знает или сможет стать президентом.

Равносильность и законы логики первого порядка.

Формулы F(x1…xn) и G(x1…xn) называются равносильными, если для любой инерпретации фи с областью М высказывания (фиF)(х1..хn) и (фиG)(х1..хn) при любых х1..хn из М одновременно истинны или одновременно ложны.

Законы логики предикатов:

1. HÛG = (HÞG)Ù(GÞH) – исключение эквивалентностей

2. HÞG=ØHÚG - исключение импликации

3. HÚG=GÚH - законы коммутативности

4. HÙG=GÙH

5. (HÚG)ÚS=HÚ(GÚS) - ассоциативности

6. (HÙG)ÙS=HÙ(GÙS)

7. HÚ(GÙS)=(HÚG)Ù(HÚS) - дистрибутивности

8. HÙ(GÚS)=(HÙG)Ú(HÙS)

9. HÚ1=1

10. HÚ0=H

11. HÙ1=H

12. HÙ0=0

13. HÚØH=1 - исключенного третьего

14. HÙØH=0 - противоречия

15. Ø(ØH)=H - двойного отрицания

16. Ø(HÚG)=ØHÙØG - Де Моргана

17.Ø(HÙG)=ØHÚØG

18. (HÙG)Ú(HÙØG)=H - склеивания

19. (HÚG)Ù(HÚØG)=H

20. HÚ(HÙG)=H - поглощения

21. HÙ(HÚG)=H

22. HÚH=H - иденпотенции

23. HÙH=H

24. HÞG=ØGÞØH - контрапозиции

25. ("x)(H(x)ÙG(x))=("x)H(x)Ù("x)G(x)

26. ($x)(H(x)ÚG(x))=($x)H(x)Ú($x)G(x)

27. ("x)("y)H(x,y)=("y)("x)H(x,y)

28. ($x)($y)H(x,y)=($y)($x)H(x,y)

29. Ø("x)H(x)=($x)ØH(x)

30. Ø($x)H(x)=("x)ØH(x)

31. ("x)(H(x)ÚG)=("x)H(x)ÚG

32. ($x)(H(x)ÙG)=($x)H(x)ÙG, G не содержит х

33. (Q1x)(Q2z)(H(x)ÚG(z))=(Q1x)H(x)Ú(Q2z)G(z)

34. (Q1x)(Q2u)(H(x)ÙG(u))=(Q1x)H(x)Ù(Q2u)G(u), где Q1, Q2 кванторы $ или ", u не входит Н(х), а х не входит в G(u).

35. ("x)H(x)=("z)H(z)

36. ($x)H(x)=($z)H(z)

В логике высказываний применялись два способа доказательства равносильности формул: построение таблицы истинности и преобразования с помощью законов логики. В логике предикатов используется только второй способ.