Логика - доступно для всех

Следующий этап в построении формализованного языка - задание правил построения его выражений из символов алфавита. В ЯЛП имеются два типа правильно построенных выражений - это термы и формулы.

Результатом символической записи как простых, так и сложных выражений естественного языка являются термы, а результатом записи высказывания - формулы.

Определение терма:

Произвольная переменная константа является термом.

Если Ф - 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)

Язык логики предикатов

``Предикатные формулы'' обобщают понятие пропозициональной формулы.

объявляя 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 – квантор.