18. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов.
Логика предикатов – это высказывание, зависящее от параметров. Таким образом, предикат - это высказывание-функция, значение (истина/ложь) которого зависит от параметров.
х >2 |
Р(х)= {ИЛ |
х > y ; |
P(2,6)= Л |
|
P(6,0)= И |
|
Предикатная форма может строится из следующих элементов: |
1)х, у, ….. – переменные
2)Р( ), Q( ) – предикаты
3)А, В, … - константы
4)┐, &, V, →, ≡ логические связи
5)
,
- кванты (существование и т. д.)
Формулы
Правильно построенные формулы логики предикатов - это комбинации атомных предикатов и констант с логическими связками. Они определяются рекурсивно над множеством атомных предикатов с помощью связок ך, → , скобок и одной дополнительной связки
формулы:
1.Атомные предикат есть формула.
2.Если Р - формула, то ך(P) - тоже формула.
3.Если Р, Q - формулы, то (P→ Q) - тоже формула.
4.Если Р - формула, то ( x)P - тоже формула.
5.Никаких других формул нет.
Влогике предикатов для сокращения формул используются записи:
• P V Q для (ךP) → Q,
•P&Q для ך(P →ךQ),
•P→ Q для (P → Q)&(Q → P),
• (
x)P для ך((
x)ךP).
Связки , называются кванторами. Присоединение квантора с переменной к предикатной формуле называется навешивание квантора на переменную х. Переменная при этом называется связанной и вместо нее подставлять константы уже нельзя.
Например, Афоризм Козьмы Пруткова ―Нет столь великой вещи, которую не превзошла бы величиной еще большая― формально может быть записан так: ך( xך y P(y, x)), где x y принимают значения на множестве всех вещей. Этот предикат имеет эквивалент: ( x yP(y, x)), что дает эквивалентную формулировку афоризма: ―Для любой вещи всегда найдется еще большая―.
тся теорией первого порядка, в которой кванторы навешиваются на предметные переменные.
Формальные теории первого порядка представляют собой яркий пример формальных теорий с аксиоматикой и правилами вывода и обладают следующим свойством: в них кванторы могут связывать только предметные константы, а не предикаты. Будем рассматривать теорию, в которой используются две логические связки ( ך, → ) и кванторные символы ( , ). Множество аксиом представлено следующими схемами:
A1.
A2.
A3.
A4.
A5.
A → (A → B),
(A → (B → C)) → ((A → B) → (A → C)),
(ךA → ךB) → (B → A),
x F(x) → F(y),
F(y) → x F(x).
В любой теории первого порядка имеются следующие правила вывода:
A, A → B (R1) |
B → A(x) (R2) |
A(x) → B (R3) |
||
|
|
|
|
|
B |
B → x A(x) |
|
x A(x) →B |
|
Покажем на примере, как с помощью нашей теории доказывается знаменитый аристотелевский силлогизм:
Все люди смертны. Сократ - человек. Следовательно, Сократ смертен.
Все, кто обладает свойством P, обладает свойством Q. y обладает свойством P. Следовательно, y обладает свойством Q.
Обосновать силлогизм на языке предикатов - это значит записать его три утверждения на этом языке и показать, что из посылок (первых двух утверждений) выводимо заключение (третье утверждение).
P( ) – быть человеком
Q( ) – быть смертным
x(P(x) → Q(x))
P(y) .
Q(y)
Формальный вывод заключения из посылок состоит в следующем:
1.В первую аксиому A4 вместо F(x) подставим P(x) →Q(x). Получим: x(P(x) →Q(x))
→ (P(y) →Q(y)).
2.Из предыдущей формулы и первой посылки по правилу заключения R1 следует, что формула:
P(y) →Q(y).
3. Из предыдущей формулы и второй посылки по правилу заключения R1 выводима формула Q(y), ч.т.д.
19. Ограниченные предикаты
(
(
x є Х)P(x)
x є Х )P(x)
(1)
(2)
Как и в логике высказываний, в логике предикатов имеются эквивалентные соотношения, позволяющие преобразовывать предикатные формулы.
x [ (x є Х) →P(x) ]
x [ (x є Х )& P(x) ]
( x: R(x)) P(x)
( x: R(x))P(x)
Эквиваленты
x [R(x) →P(x) ]
x [R(x)& P(x) ]
Эквиваленты
(1)
(2)
если выполняется R(x), то выполняется Р(х)
Для ограниченных предикатов выполняются законы Де Моргана, связанные с внесением отрицания под квантор.
ך( x :R(x)) P(x)= ( x: R(x))ךP(x)
ך( x: R(x)) P(x) = ( x: R(x))ךP(x)
Пример:
Кто не рискует, тот не пьет шампанское
Q(x) – пить шампанское
P(x) – рисковать
x(┐P(x) → ┐Q(x)) Эквивалент: ( x: ┐P(x)) ┐Q(x);
Понятие терма.
┐(
x: ┐P(x) Q(x)
Множество объектов, о которых даются утверждения, называется предметной областью, а сами отношения между n объектами - n-местными предикатами. С математической точки зрения n-местный предикат - это функция P(x1, . . . , xn) от n переменных, причем переменные принимают значения из предметной области, а функция P принимает два значения .
Нечетность - одноместный предикат. Если его обозначить через P1(x).
n-местным предикатом P(x1, x2, ..xn) называется функция P: Mn → {True,
False}, определенная на наборах длины n элементов некоторого множества M и принимающая значения в области True, False. Множество М называется предметной областью предиката, а x1, x2, ..xn - предметными переменными.
Термом будем называть переменную или константу предметной области М или функцию, принимающую значения в предметной области. Пусть t1, t2, ..tn- термы. Атомный предикат - это n-местная функция F(t1, t2, ..tn), принимающая значение на
множестве И,Л.