Кванторы. Кванторные операции над предикатами

1.

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

2.

Кванторные операции над предикатами

3.

Кванторные операции над предикатами

4.

Кванторные операции над предикатами

5.

Кванторные операции над предикатами

6.

Кванторные операции над предикатами

7.

Кванторные операции над предикатами

8.

Численные кванторы
«по меньшей мере n» («хотя бы n»),
«не более чем n»,
«n и только n»,
где n – натуральное число
выражения, называемые численными кванторами, имеют
чисто логический смысл;
могут быть заменены равнозначными выражениями, не
содержащими числительных и состоящими только из
логических терминов и знака =

9.

Численные кванторы

10.

Численные кванторы

11.

Численные кванторы

12.

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

13.

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

14.

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

15.

Формулы логики предикатов
Выполняются раньше отрицания (имеют более
высокий приоритет)
xP( x) Q( x)
( xP( x)) Q( x)

16.

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

17.

Формулы логики предикатов
A( x, y )
Обе свободные
y ( B( x) xQ( x, y ))
у -связанная,
х -и связанная и свободная
xB( x) xQ( x, y )
х -связанная,
у -свободная

18.

Интерпретация формул логики предикатов

19.

Интерпретация формул логики предикатов

20.

Интерпретация формул логики предикатов

21.

Интерпретация формул логики предикатов

22.

Интерпретация формул логики предикатов

23.

Интерпретация формул логики предикатов

24.

Интерпретация формул логики предикатов

25.

Интерпретация формул логики предикатов

26.

Интерпретация формул логики предикатов

27.

Классификация формул логики предикатов

28.

Классификация формул логики предикатов

29.

Классификация формул логики предикатов

30.

Классификация формул логики предикатов

31.

Классификация формул логики предикатов

32.

Равносильность формул логики предикатов

33.

Равносильность формул логики предикатов

34.

Равносильность формул логики предикатов

35.

Равносильность формул логики предикатов

36.

Равносильность формул логики предикатов

37.

Равносильность формул логики предикатов

38.

Равносильность формул логики предикатов

39.

Равносильность формул логики предикатов

40.

Равносильность формул логики предикатов

41.

Использование
формул логики предикатов
в теории доказательств
41

42.

Логика предикатов
Все люди смертны
Сократ – человек
__________________
Сократ смертен
( х)(Ч(х) С(х))
Ч(с)
__________________
С(с)
Ч(х): х – человек
С(х): х – смертен
Х – предметная область
с Х
42

43.

Логика предикатов
Ч С
Ч
__________________
С
43

44.

Удаление квантора всеобщности
Удаление квантора существования
Введение квантора существования
Правило подстановки
(свободной переменной)
44

45.

( х)(Ч(х) С(х))
Ч(с)
__________________
Ч(t) С(t)
Ч(с)
__________________
С(с)
С(с)
Ч(с) С(с)
Ч(с)
__________________
С(с)
45

46.

Введение квантора всеобщности
Смена квантора
46

47.

Введение новой переменной:
47

48.

Пример 1
48

49.

Пример 1
49

50.

Пример 2
50

51.

Пример 2
51

52.

Пример 2
52

53.

Пример 2
53

54.

54

55. Типы суждений

55

56. Типы суждений

56

57. Типы суждений

57

58. Типы суждений

58

59.

59

60.

1) за квантором общности чаще всего следует логическая связка
импликации, а за квантором существования - конъюнкции;
2) если формула содержит подформулу, то внутренняя формула не должна
содержать кванторов, связывающих ту же переменную, что и квантор
формулы;
3) значения всех предметных переменных и постоянных должны
принадлежать одной области определения предиката или функции;
4) по возможности, квантор существования ставить ближе к началу
60

61.

слово “все” обычно опускается
“Рыбы дышат жабрами”
не в каждом случае слова “все” понимаются как “каждый”.
“Все песчинки образуют кучу песка”
не каждая песчинка образует кучу песка.
употреблять квантор всеобщности нельзя
“Собакам и кошкам вход запрещен”.
“Если х - собака и х - кошка, то х - вход запрещен”.
“Если х - собака или х - кошка, то х - вход воспрещен”.
61

62.

62

63.

63

64.

Пример
64

65.

Пример
65

66.

Пример
66

67.

Пример
67

68.

Пример
68

69.

Пример
69

70.

Пример
70

71.

Пример
71

72.

Пример
72

73.

Пример
73

74.

x( P( x))
x( P( x))
x( P( x)) x( P( x))
P(a)
P(b)
74

75. Сколемовская нормальная форма (СНФ)

y x( P( x, y))
P( x, b)
x y( P( x, y))
P( x, f ( x))
75

76. Сколемовская нормальная форма (СНФ)

1. Формула логики предикатов представляется в ПНФ.
2. Последовательно (слева направо) вычеркивается каждый квантор существования
(например y ),
заменяются все вхождения переменной y на новый еще не использованный
функциональный символ f ,
в качестве аргументов f берутся все переменные, связанные предшествующими y
кванторами всеобщности.
Функциональный символ f называется сколемовской функцией.
76

77. Сколемовская стандартная форма (СНФ)

x y z u w( P( x, y ) R( z, u, ) & Q(u, w))
y z u w( P(c, y ) R( z , u, ) & Q(u, w))
y z w( P(c, y ) R( z , f ( y, z ), ) & Q( f ( y, z ), w))
y z ( P(c, y ) R( z, f ( y, z ), ) & Q( f ( y, z ), g ( y, z, )))
77

78. Сколемовская стандартная форма (СНФ)

x( P3 ( x) P1 ( x) y ( P5 ( y ) P4 ( x, y )))
x( P2 ( x) P3 ( x) y ( P4 ( x, y ) P2 ( y )))
x( P2 ( x) P1 ( x))
___________________________________
x( P5 ( x) P2 ( x))
Пример
78

79. Сколемовская стандартная форма (СНФ)

x( P3 ( x) P1 ( x) y ( P5 ( y ) P4 ( x, y )))
x( P2 ( x) P3 ( x) y ( P4 ( x, y ) P2 ( y )))
x( P2 ( x) P1 ( x))
___________________________________
x( P5 ( x) P2 ( x))
1) P3 ( x) P1 ( x) P5 ( f ( x))
6) P1 ( x) P2 ( x)
2) P3 ( x) P1( x) P4 ( x, f ( x))
7) P5 ( x) P2 ( x)
3) P2 (a )
4) P3 (a )
5) P4 (a, y) P2 ( y)
Пример
79

80. Сколемовская стандартная форма (СНФ)

1) P3 ( x) P1 ( x) P5 ( f ( x))
2) P3 ( x) P1( x) P4 ( x, f ( x))
3) P2 (a )
4) P3 (a )
5) P4 (a, y) P2 ( y)
6) P1 ( x) P2 ( x)
7) P5 ( x) P2 ( x)
8) P1(a) (3 6)
9) P3 (a) P4 (a, f (a)) (2 8)
10) P2 ( f (a)) P3 (a) (5 9)
11) P3 (a) P5 ( f (a))(7 10)
12) P3 (a) P1 (a) (1 11)
13) P1 (a) (4 12)
14) (8 13)
Пример
80

81. Применение логики предикатов к математической практике

81

82. Применение логики предикатов к математической практике

82

83. Аристотелева силлогистика и методы рассуждений

83

84. Аристотелева силлогистика и методы рассуждений

84

85. Аристотелева силлогистика и методы рассуждений

85

86. Аристотелева силлогистика и методы рассуждений

86

87. Аристотелева силлогистика и методы рассуждений

87

88. Теоретико-множественная интерпретация аристотелевой силлогистики

88

89. Теоретико-множественная интерпретация аристотелевой силлогистики

89

90. Теоретико-множественная интерпретация аристотелевой силлогистики

S
0
0
0
0
1
1
1
1
M
0
0
1
1
0
0
1
1
P
0
1
0
1
0
1
0
1
1
1
0
1
1
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
1
1
1
0
1
0
1
0
0
0
0
1
0
1
0
90

91. Теоретико-множественная интерпретация аристотелевой силлогистики

91

92. Теоретико-множественная интерпретация аристотелевой силлогистики

пример неправильного силлогизма
92

93. Теоретико-множественная интерпретация аристотелевой силлогистики

S
0
0
0
0
1
1
1
1
M
0
0
1
1
0
0
1
1
P
0
1
0
1
0
1
0
1
1
1
1
0
1
1
1
0
0
0
0
1
0
0
0
1
1
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
0
0
0
0
1
0
1
0
93