Следующий этап в построении формализованного языка — задание правил построения его выражений из символов алфавита. В ЯЛП имеются два типа правильно построенных выражений — это термы и формулы.
Результатом символической записи как простых, так и сложных выражений естественного языка являются термы, а результатом записи высказывания — формулы.
Определение терма:
Произвольная переменная константа является термом.
Если Ф — n-местная предметно-функциональная константа,
а t1, t2, t3,… tn — термы, то выражение Ф(t1, t2, t3,… tn) — является термом.
Ничто иное термом не является.
Например, символы а, в1, с3 — термы (согласно пункту 1) и символы x2, z10, y — термы (согласно п.2), а символы f1, P2 и — не термы, т.к. не относятся ни к числу предметных констант или предметных переменных, ни к числу выражений вида Ф(t1, t2, t3,… tn).
Попробуем перевести на язык логики предикатов имена естественного языка:
Пусть простому имени «4» соответствует предметная константа α,
а простому имени «5» — b,
одноместному предметному функтору «» сопоставим одноместную предметную функциональную константу f1 (или просто f),
а двухместному функтору «+» — двухместную предметно- функциональную константу g2 (или просто g)
Тогда при переводе на ЯЛП сложным именам будут соответствовать следующие термы:
имени «4» — терм f(a);
имени «4+5» — терм g(a, b);
имени «5+4» — терм g(b, a);
имени «4+5» — терм g (f(a),b);
имени «4+5» — терм f (g (a,b));
имени «(4+4) + (5+5)» — терм g(g (a,a), g(b,b).
Давайте разберем еще один пример:
Пусть имени Москва соответствует константа a, имени Киев — константа b, имени Россия — c, имени Украина — d, столица обозначим f, а «расстояние от … до …» — обозначим g. Тогда, при переводе на язык логики высказываний сложным именам будут соответствовать следующие термы:
Столица России — f (c)
Расстояние от Москвы до Киева — g (a,b)
Расстояние от Москвы до столицы Украины — g (a, f(d))
Расстояние от столицы России до Киева — g (f(c), b).
Дадим определение формулы:
1. Если П — n-местная предикаторная константа, а t1, t2, t3 …, tn — термы,
то выражение П (t1, t2, t3 …, tn) — является формулой.
2. Если А — формула, то А — тоже формула.
3. Если А и В — формулы, то — формулы.
4. Если А — формула, а а — предметная переменная, то аА и аА — формулы.
5. Ничто иное формулой не является.
Каким образом осуществляется перевод высказываний естественного языка на язык логики предикатов? Начнем с высказываний, которые не содержат утверждений об отдельных предметах и в состав которых не входят кванторные слова.
Простые высказывания, в которых утверждается наличие свойства отдельного предмета, записываются в ЯЛП посредством формулы вида П1(t), где t — терм, соответствующий имени предмета, а П1 — одноместная предикаторная константа, соответствующая знаку свойства.
Например, переводом высказывания на ЯЛП выражений:
1.»Ромео — юноша» может быть формула Р(а), где предметная константа а — соответствует имени «Ромео», а одноместная предикаторная константа Р – знаку свойства — «юноша»;
2. «Отец Ромео — храбр» — Q (f (a)), где а — Ромео, f — отец, а знаку свойства «храбрый» соответствует одноместная предикаторная константа — Q
3. Отрицание наличия свойства у отдельных предметов переводится на ЯЛП посредством формул вида П1 (t).
Например, «Отец Ромео не является юношей» — Р (f (a)).
4. Наличие отношения между двумя предметами записывается в виде
формул вида П2 (t1,t2). Например, выражение «Ромео любит Джульетту» — R (a, b),
«Джульетта любит своего отца» — R (b, f (b))
5. Высказывание о наличии отношения между n предметами записывается в виде формулы Пn (t1, t2, … tn), где Пn — n-местная предикаторная константа, которая соответствует предикатору n-местного отношения.
«Джульетта любит Ромео больше, чем своего отца» — R1 (b, a, f(b)), где R1 — трехместная предметная константа, которая соответствует трехместному отношению «любит больше, чем».
6. Запись высказывания, содержащего кванторы, в ЯЛП происходит с помощью формул вида а А (а), где а — предметная переменная.
«Кто-то является храбрым» — x Q (x),
«Кто-то любит Джульетту» — x R (x, b),
«Джульетта любит кого-то» — x R (b, x),
«Кто-то не любит самого себя» — x R (x, x)
7. Простые высказывания могут содержать несколько кванторов:
«Каждый любит кого-нибудь» — x y R (x, y),
«Кто-то кого-то не любит » — x y R (x, y)
Язык логики предикатов
«Предикатные формулы» обобщают понятие пропозициональной формулы.
|
Предикатная сигнатура – это множество символов двух типов – объектные константы и предикатные константы – с неотрицательным целым числом, называемым арностью, назначенным каждой предикатной константе. Предикатную константу мы будем называть пропозициональной, если её арность равна 0. Пропозициональные константы являются аналогом атомов в логике высказываний. Предикатная константа унарна, если её арность равна 1, и бинарна, если её арность равна 2. Например, мы можем определить предикатную сигнатуру { a, P, Q } |
(4) |
объявляя a объектной константой, P – унарной предикатной константой, и Q – бинарной предикатной константой.
Возьмём предикатную сигнатуру s, которая включает по крайней мере одну предикатную константу и не включает ни одного из следующих символов:
объектные переменные x, y, z, x1, y1, z1, x2, y2, z2, …,
пропозициональные связки,
квантор всеобщности » и квантор существования $,
скобки и запятая.
Алфавит логики предикатов состоит из элементов из s и четырёх групп дополнительных символов, указанных выше. Строка – это конечная последовательность символов из этого алфавита.
Терм – это объектная константа или объектная переменная. Строка называется атомарной формулой, если она является пропозициональной константой или имеет вид R(t1, …, tn), где R – предикатная константа арности n (n > 0) и t1, … , tn – термы. Например, если мы рассматриваем сигнатуру (4), то P(a) и Q(a, x) – атомарные формулы.
Множество X строк замкнуто относительно правил построения (для логики предикатов), если
каждая атомарная формула принадлежит X,
для любой строки F если F принадлежит X, то ¬F тоже принадлежит,
для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G),
для любого квантора K, любой переменной v и любой строки F если F принадлежит X, то также принадлежит Kv F.
Строка F является (предикатной) формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.
Например, если рассматриваемая сигнатура есть (4), тогда
(¬P (a) Ъ $ x(P (x) & Q(x, y))) – формула.
3.1 Является ли » x формулой?
Как и в логике высказываний можно доказать, что множество формул замкнуто относительно правил построения. Теоремы возможности и единственности разбора подобны соответствующим теоремам для пропозициональных формул.
В случае предикатных формул доказательство по структурной индукции имеет следующий вид. Для данного свойства формул мы проверяем, что каждая атомарная формула обладает этим свойством, для любой формулы F, обладающей этим свойством, ¬F также обладает этим свойством, для любых формул F, G, обладающих этим свойством, и любой бинарной связки Д, (F Д G) также обладает этим свойством, для любого квантора K, любой переменной v и любой формулы F, обладающей этим свойством, K v F также обладает этим свойством.
Тогда это свойство выполняется для всех формул.
При записи предикатных формул мы будем опускать некоторые скобки и применять другие сокращения. Строку вида » v1 ··· » vn (n і 0)
будем писать как » v1 ··· vn, и подобным образом для квантора существования.
Свободные и связанные переменные
Множество свободных переменных * формулы F определяется рекурсивно, следующим образом:
(Свободные переменные).
Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы, свободные переменные формулы F являются свободными переменными формулы ¬F, переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G), все свободные переменные формулы F кроме v являются свободными переменными формулы K v F.
(Замкнутая формула). Формула без свободных переменных называется замкнутой формулой, или предложением.
(Связаная переменная). Переменная v связана в формуле F, если F содержит вхождение Kv, где K – квантор.