Логика предикатов. ДМ.13

1. Дискретная математика

2. Предикаты

Предикат – это функция
вида
Р(х1, х2, …, хn)=y,
Здесь х1, х2, …, хn предметные переменные; y
- значение предиката.

3. Предикаты

x1 M 1 , x2 M 2 , ..., xn M n
где M 1 , M 2 , ..., M n
предметные множества,
M 1 M 2 ... M n
поле предиката.

4. Предикаты

Переменная y – может принимать
значения из множества
В={0, 1}.
Здесь 0 – «нет», «ложь»;
1 – «да», «истина».

5. Предикаты

Например:
1) на множестве N задан предикат
Р(х) – «х является четным
числом».
Тогда Р(1)=0, Р(2)=1.
2) На множестве N×N задан
предикат Q(x,y) – «x≤y».
Тогда
Q(1,1)=1; Q(1,2)=1; Q(3,2) =0.

6. Предикаты

Подмножество I множества М
называется областью
истинности предиката Р, если
наборы значений предметных
переменных из множества I
обращают предикат P в 1.

7. Предикаты

Например:
Для предиката Q(x,y) область
истинности I – множество всех
точек плоскости с
натуральными координатами,
лежащие на диагонали
первого координатного угла и
выше.

8. Предикаты

9. Предикаты

Над предикатами можно совершать
знакомые нам логические операции:
Конъюнкцию, дизъюнкцию,
отрицание, импликацию, и т. д.
Например:
Р(х,у) – «х<y», R(x,y) – «x=y».
Тогда ⌐ Р(х,у) – «х≥у»,
Р(х,у)V R(x,y) – «х≤у» и т. д.

10. Предикаты

При этом область истинности
полученных предикатов изменяется
по тем же правилам:
I P I P ;
I P R I P
и так далее.
IR;

11. Предикаты

Однако в логике предикатов есть
операция, которая отсутствуют в
логике высказываний.
Квантификация или квантирование
В результате этой операции на
переменную предиката навешивается
квантор (переменная связывается
квантором). Переменная при этом
становится связанной. Переменная,
не связанная называется свободной.

12. Предикаты

Существуют два вида
кванторов:
Квантор общности «для
любого, для каждого».
Квантор существования
«существует, найдется».

13. Предикаты

Предикатная формула:
xP x
истинна тогда и только тогда,
когда предикат Р(х)=1 при
любом х,
ложна тогда и только тогда,
когда найдется х, при
котором предикат Р(х)=0.

14. Предикаты

Предикатная формула:
xP x
истинна тогда и только тогда,
когда найдется х, при
котором предикат Р(х)=1,
ложна тогда и только тогда,
когда предикат Р(х)=0 при
любом х.

15. Замечание

Когда в предикате Р(х)
переменная х связывается
квантором, она перестает влиять
на значение предиката и
предикат становится
высказыванием, принимающим
фиксированное значение
Истина или Ложь.

16. Предикаты

Например: Р(х) – «х является
четным числом» на множестве N
Тогда xP x 0
так как есть х=3, при котором
Р(3)=0.
Тогда xP x 1
так как есть х=2, при котором
Р(2)=1.

17. Предикаты

Если предикат имеет более 1
переменной, то ее квантификация
приводит к уменьшению числа
переменных на 1.
Например:
предикат Q(x,y) – «x≤y» на
множестве N×N.

18. Предикаты

xQ x, y R( y )
новый предикат от одной
переменной у – «любое
натуральное число х меньше либо
равно у».
При у=1 это не так (любой х ≤1) ,
xQ x,1 R(1) 0,
При у=2 это не так (любой х ≤2),
xQ x,2 R(2) 0,

19. Предикаты

Таким образом, предикат
R( y) xQ x, y 0
то есть является функцией константой

20. Предикаты

xQ x, y W ( y)
новый предикат от одной
переменной у – «найдется
натуральное число х меньше либо
равно у».
При у=1 это так (найдется х ≤ 1) ,
xQ x,1 W (1) 1,
При у=2 это так (найдется х ≤2),
xQ x,2 W (2) 1,

21. Предикаты

Таким образом, предикат
W( y) xQ x, y 1
то есть тоже является функцией
-константой

22. Предикаты

Кванторы можно навесить на все
переменные предиката. Тогда
предикат станет высказыванием.
Например:
предикат Q(x,y) – «x≤y».

23. Предикаты

x yQ x, y 0
так как неверно то, что любой
натуральный х меньше либо
равен любого натурального у.
Например, при х=5, у=2.

24. Предикаты

x yQ x, y 1
так как верно то, что любой
натуральный х меньше либо
равен некоторого
натурального у.
Например, при х=1, у=1; при
х=2, у=2, …

25. Предикаты

y xQ x, y 0
так как неверно то, что
найдется такой натуральный
у, который будет больше либо
равен любого натурального х.
Это связано с тем, что
натуральное множество не
ограничено сверху.

26. Предикаты

x yQ x, y 1
так как верно то, что найдется
такой натуральный х,
который будет меньше либо
равен любого натурального у.
Этот х=1. Если бы неравенство
было строгое, высказывание
было бы ложным.

27. Предикаты

y xQ x, y 1
так как верно то, что любой
натуральный у, больше либо
равен некоторого
натурального х.
Например, у=1, х=1;
у=2, х=2,…

28. Предикаты

x yQ x, y 1
так как верно то, что найдутся
такие натуральные х и у, что
х меньше либо равен этого у.
Например х=3, у=7.

29. Логика предикатов

Логика предикатов, как и
логика высказываний, – свод
правил, по которым строятся
формулы связывающие
простые предикаты в
предикатные формулы и
порядок определения
истинности/ложности этих
формул.

30. Логика предикатов

Равносильные предикатные
формулы – те, у которых
область истинности совпадает.

31. Логика предикатов

Интерпретация – это
сопоставление каждому
предикатному символу в
формуле определенного
предиката.

32. Логика предикатов

Пусть формулы F и G содержат
одно и тоже множество
свободных переменных.
Формулы F и G равносильны в
данной интерпретации –
если они выражают один и тот
же предикат.

33. Логика предикатов

Например:
P x, y : x y; Q x, y : x y.
Тогда предикатные формулы:
F P x, y и G Q x, y
являются равносильными в данной
интерпретации, так как
P x, y Q x, y .
При других интерпретациях предикатов P и Q
формулы могут не быть равносильными.

34. Логика предикатов

Формулы F и G равносильны
на множестве М – если они
равносильны во всех
интерпретациях на этом
множестве.

35. Логика предикатов

Например: F xP x , G xP x
Равносильны в любой
интерпретации на множестве М,
если М состоит из одного
элемента. Если
a M : P a 0, xP x 0 и xP x 0.
Если
a M : P a 1, xP x 1 и xP x 1.
На другом множестве формулы F и G могут не
быть равносильными.

36. Логика предикатов

Формулы F и G равносильны в
логике предикатов – если они
равносильны на всех
множествах.

37. Логика предикатов

Например:
F P x P x ,
G P x P x .
Тогда F и G равносильны на любых
множествах и при любых
интерпретациях предиката P(x).
F G

38. Равносильные формулы

Для предикатных формул
сохраняются все равносильности
(эквивалентности) алгебры логики.
Например, закон де Моргана:
P x Q x P x Q x
P x Q x P x Q x

39. Свойства операций над предикатами

Перенос квантора через отрицание
xP x x P x
1
xP x x P x
2
Здесь и далее, знак равносильности ≡
заменен знаком равенства.

40. Свойства операций над предикатами

Вынос квантора за скобки
xP x Q x P x Q 3
xP x Q x P x Q 4

41. Свойства операций над предикатами

Вынос квантора за скобки
xP x Q x P x Q 5
xP x Q x P x Q 6

42. Свойства операций над предикатами

Закон коммутативности для
одноименных кванторов:
x yP x, y y xP x, y 7
x yP x, y y xP x, y 8

43. Свойства операций над предикатами

Коммутативность дает
возможность использовать более
краткую запись:
x y zP x, y,z x, y, zP x, y,z 9
x y zP x, y, z x, y, zP x, y, z 10

44. Равносильные формулы

Проверить равносильность формулы в
логике предикатов, не так просто, как в
логике высказываний. Высказывание
может принимать значения 0 и 1.
Формула с 2 высказываниями
содержит 2² возможных значений, и так
далее.
Предикат имеет бесконечное
множество интерпретаций.

45. Истинность в логике предикатов

Предикатная формула F
называется выполнимой
(непротиворечивой), если
существует интерпретация
входящих в нее предикатов, в
которой F принимает значение
истина. То есть ее область
истинности не пуста.

46. Истинность в логике предикатов

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

47. Истинность в логике предикатов

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

48. Истинность в логике предикатов

Например:
F P x P x 1
Тождественно истинная формула.
G P x P x 0
Тождественно ложная формула

49. Истинность в логике предикатов

Замечание 1
Формула F – общезначима тогда и
только тогда, когда
¬F – противоречива.
Замечание 2
Формула F – выполнима тогда и
только тогда, когда
¬F – не является общезначимой.

50. Истинность в логике предикатов

Замечание 3
Если F и G – равносильные
формулы в логике предикатов, то
формула
W=F~G
общезначима и выполняется
равенство:
I F IG

51. Истинность в логике предикатов

Замечание 4
Если формула
W=F→G
общезначима, то выполняется:
I F IG

52. Истинность в логике предикатов

Замечание 5
Если y не входит в формулу P(x),
то следующие формулы
являются общезначимыми:
xP x P y ;
P y xP x .

53. Истинность в логике предикатов

Квантор общности является
обобщением конъюнкции,
поэтому справедлива формула:
x P x Q x
11
xP x xQ x .

54. Истинность в логике предикатов

Квантор существования
является обобщением
дизъюнкции, поэтому
справедлива формула:
x P x Q x
12
xP x xQ x .

55. Истинность в логике предикатов

Замечание 6
Если в формулах (11) и (12)
поменять местами кванторы, то
получаются выражения, истинные
лишь в одну сторону:
x P x Q x
13
xP x xQ x .

56. Истинность в логике предикатов

xP x xQ x
14
x P x Q x .
В таких случаях говорят, что
левая часть утверждения более
сильная, чем правая.

57. Истинность в логике предикатов

В таком случае, надо
воспользоваться правилом:
xP x yP y zP z tP t ...
xP x yP y zP z tP t ...
То есть, если переменная
связана квантором, то неважно,
как она называется.

58. Истинность в логике предикатов

В выражениях (13) и (14) надо
сделать замену переменной, после
чего воспользоваться формулами
(4) и (5):
xP x xQ x
xP x yQ y
15
x y P x Q y .

59. Истинность в логике предикатов

xP x xQ x
xP x yQ y
x y P x Q y .
16

60. Префиксная нормальная форма

Префиксной нормальной формой
(ПНФ) называется формула,
имеющая вид:
Q1 x1Q2 x2 ...Qn xn F
где Q1 , Q2 ,...Qn кванторы,
F – предикатная формула,
имеющая вид ДНФ.