Логика предикатов. Определение предиката

1.

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

2. Определение предиката

Предика́т (лат. praedicatum — заявленное, упомянутое,
сказанное) — любое математическое высказывание, в
котором есть, по меньшей мере, одна переменная.
Это функция
P( x1 ,..., xn ) : M n {0,1}

3. Примеры предикатов

Пример 1
Пример 2

4. Пример 1

Кванторы
1. Общности
1, если x M
xP( x)
0, иначе
1, если x M
2. Существования xP( x)
0, иначе
Если в формуле для переменной нет квантора,
она называется свободной, иначе связанной.

5. Пример 2

Примеры кванторов
Пример 1
Пример 2
Пример 3

6. Кванторы

Равносильность формул логики
предикатов
Пусть формулы F и G имеют одно и то же множество
свободных переменных.
1. Формулы F и G равносильны в данной
интерпретации, если на любом наборе значений
свободных переменных они принимают
одинаковые значения.
2. Формулы F и G равносильны на множестве, если
они равносильны во всех интерпретациях,
заданных на этом множестве.
3. Формулы F и G равносильны, если они
равносильны на любых множествах.

7. Примеры кванторов

Правила для кванторов
Перенос квантора через отрицание
xP( x) x P( x)
xP( x) x P( x)
• Вынесение квантора за скобки
Пусть А(x) содержит свободную переменную x
B-не содержит свободную переменную x
x( A( x) B) xA( x) B
x( A( x) B) xA( x) B
x( A( x) B) xA( x) B
x( A( x) B) xA( x) B

8. Пример 1

Правила для кванторов
Если B(x),то
x( A( x) B( x)) xA( x) xB( x)
x( A( x) B( x)) xA( x) xB( x)
Перестановка одноименных кванторов
x yP( x, y ) y xP( x, y )
x yP( x, y ) y xP( x, y )
Переименование связанной переменной
Заменяя свободную переменную формулы
другой переменной, не входящей в эту
формулу, всюду в области действия квантора,
получаем формулу, равносильную данной.

9. Пример 2

Выполнимость. Общезначимость.
• Формула A( x1 ,...xn ) выполнима в данной
интерпретации, если существует набор
свободных переменных
формулы
a1 ,...
a | A( x1 ,...xn ) | a ,... a 1
• Формула А истинна в данной интерпретации,
если
n
a1 ,...an
1
n
A( x1 ,...xn ) | a1 ,... an 1
• Формула А общезначима, если она истинна в
любой интерпретации.
• Формула А выполнима , если существует
интерпретация, в которой она выполнима.