<< Пред. стр.

стр. 2
(общее количество: 9)

ОГЛАВЛЕНИЕ

След. стр. >>


Теорема 2.2 (об индукции по структуре формул) Пусть ? такое подмножес-
тво L? , что

(i) ? содержит все атомные формулы;

(ii) Если P, Q ? ?, то (¬P), (P ? Q), (P ? Q), (P > Q) ? ?;

(iii) Если P ? ?, то ((?x)P), ((?x)P) ? ? для произвольного символа предметной
переменной x.

Тогда ? содержит все формулы.
12 Языки логики предикатов первого порядка


3. Докажите, что любая формула языка логики предикатов первого порядка содер-
жит одинаковое количество открывающих и закрывающих скобок.
Указание. Воспользуйтесь доказанными теоремами об индукции по структуре тер-
мов и формул.
Приоритеты операций. Запись формул можно сократить путем некоторого
уменьшения количества ненужных скобок. Для этого введем следующие приори-
теты логических символов:

P r (?) = P r (?) = P r (¬) > P r (?) > P r (?) > P r (>) ,
где символ P r (A) обозначает приоритет операции A.
Таким образом, самый высокий приоритет имеют кванторы, далее в порядке
убывания приоритета следуют символы отрицания, конъюнкции, дизъюнкции,
и, наконец, импликации. С учетом этого правила, например, цепочки символов
?x(A1 (x) > B 1 (x)) и ?x¬A2 (x, y) являются сокращенным обозначением формул
((?x)(A1 (x) > B 1 (x))) и ((?x)(¬A2 (x, y))), соответственно. Впредь мы будем за-
писывать все формулы в сокращенном виде с использованием введенных прио-
ритетов.


2.3 Свободные и связанные переменные
Определим множество свободных переменных Free(P) и множество связанных
переменных Bound(P) формулы P ? L? . Здесь и далее var (t), var (P) обозначает
множество символов предметных переменных, входящих, соответственно, в терм
t и формулу P.

Определение 2.2 Множество свободных переменных Free(P) и множество
связанных переменных Bound(P) формулы P ? L? определяются по следующим
правилам:

• если P – атомная формула, то Free(P) := var (t), где объединение бе-
t
рется по всем термам, входящим в формулу P, и Bound(P) := ?;

• если P = (¬Q), то Free(P) := Free(Q) и Bound(P) := Bound(Q);

• если P = (Q ? S) или P = (Q ? S), или P = (Q > S), то Free(P) :=
Free(Q) ? Free(S) и Bound(P) := Bound(Q) ? Bound(S);

• если P = ((?x)Q) или P = ((?x)Q), то Free(P) = Free(Q) \ {x} и
Bound(P) = Bound(Q) ? {x}.
2.4 Семантика языков логики первого порядка 13


Иначе говоря, переменные “связываются” кванторами ?, ?. Заметим, что вовсе
не обязательно Free(P) ? Bound(P) = ?. Например, если

P := ?x(Q(x, y) > R(x)) ? ?y(¬Q(x, y) > ?zR(z)),

то для данной формулы Free(P) = {x, y}, Bound(P) = {x, y, z}, а значит,
Free(P) ? Bound(P) = {x, y} = ?. Тем не менее, каждое конкретное вхожде-
ние переменной в формулу может быть либо свободным, либо связанным.

Определение 2.3 Формула P называется замкнутой (или предложением), ес-
ли у нее нет свободных переменных.

2.4 Семантика языков логики первого порядка
До сих пор мы занимались исключительно вопросами синтаксиса языков логики
предикатов первого порядка, рассматривая эти языки совершенно формально
как наборы цепочек символов, построенных по определенным правилам. Теперь
нашей задачей будет придать смысл введенным синтаксическим конструкциям.
Формулы языков первого порядка будем интерпретировать как утверждения
о некоторой предметной области, заранее не фиксированной при рассмотрении
каждого конкретного языка. Так, например, любая формула может восприни-
маться как утверждение о натуральных числах, о геометрических фигурах, о
крокодилах в Южной Америке и т. п. При этом одна и та же формула может
представлять истинное утверждение в одной предметной области и ложное в
другой. Например, формула ?xA(x) может представлять истинное утверждение
о крокодилах (например, “все крокодилы являются рептилиями”, если A(x) ин-
терпретируется как “x – рептилия”) и ложное утверждение о натуральных числах
(“все натуральные числа являются четными”, если A(x) интерпретируется как “x
– четное число”). И даже в одной и той же предметной области формула может
оказаться как истинной, так и ложной, в зависимости от того, какой смысл при-
писывается символам констант, функциональным и предикатным символам, а
также символам свободных переменных. Например, приведенная выше формула
может представлять и истинное утверждение о натуральных числах, если A(x)
интерпретируется как “x – натуральное число”.
Прежде чем вводить формальные определения, сделаем еще одно важное за-
мечание. Мы будем рассматривать только классическую двузначную семантику
(как правило, принято говорить о двузначной логике), в которой каждая фор-
мула языка первого порядка интерпретируется как истинное либо ложное утвер-
ждение. При этом говорят, что формула имеет истинностное значение: 1 (отож-
дествляемом с истиной) или 0 (отождествляемом с ложью). Существует и много-
значная семантика, в которой истинностное значение формулы может принимать
14 Языки логики предикатов первого порядка


более двух значений. Наиболее широко известной является трехзначная логика
Лукасевича, в которой допускается наряду с 0 и 1 истинностное значение 1/2
(интерпретируемое, например, как “вероятно”). Можно рассматривать и конти-
нуальную многозначную семантику, в которой истинностное значение формулы
может быть любым числом от 0 до 1 и интерпретироваться, например, как сте-
пень правдоподобности. Особенно интересны приложения таких многозначных
логик. Например, в языке логики предикатов, предназначенном для описания
действий с абстрактными множествами, можно записать формулу, выражающую
утверждение “данный элемент принадлежит заданному множеству”. В класси-
ческой однозначной семантике такая формула может считаться либо истинной
(истинностное значение 1), либо ложной (истинностное значение 0). Однако в
только что упомянутой континуальной семантике эта формула может иметь лю-
бое истинностное значение в промежутке [0, 1], которое логично интерпретиро-
вать как степень принадлежности элемента множеству. Таким образом, в теории
множеств, базирующейся на такой семантике, элемент может принадлежать мно-
жеству в большей или меньшей степени. Эта теория получила название теории
нечетких множеств (fuzzy set theory) и нашла широкое применение в методе
экспертных оценок.
Теперь мы можем строго определить истинностное значение формулы языка
логики предикатов первого порядка L? для двузначной семантики. Для этого
нам понадобятся понятия универсума, алгебраической системы и интерпрета-
ции для языка L? .

Определение 2.4 Алгебраической системой для сигнатуры ? называется на-
бор M следующих объектов:

• непустого множества M , называемого универсумом,

• для каждого символа предметной константы c ? Const выделенного эле-
мента универсума cM ? M ,

• для каждого n-арного функционального символа f ? Funcn выделенной
функции f M : M n > M , где M n := M ? M ? ... ? M ,
n раз


• для каждого n-арного предикатного символа A ? Predn характеристиче-
ской функции выделенного n-местного отношения AM : M n > {0, 1}.

Определение 2.5 Интерпретацией в алгебраической системе M называется
пара (M, ?), где ? функция ?: Var > M .
2.4 Семантика языков логики первого порядка 15


Таким образом, алгебраическая система для языка L? определяет тот “мир”,
о котором “говорят” формулы L? . Символы предметных констант представле-
ны в ней элементами универсума, функциональные символы – функциями на
универсуме, а предикатным символам соответствуют отношения на универсуме.
Интерпретация нужна, чтобы поставить в соответствие символам предметных
переменных элементы универсума.
Пользуясь введенными определениями, мы можем связать элементы универ-
сума и термы языка L? . Для этого, фиксировав интерпретацию (M, ?), введем
в рассмотрение функцию [ ]: TER(L? ) > M “значения” терма в соответствии со
следующими правилами:

• если t = c ? Const, то [t] := cM ,

• если t = x ? Var, то [t] := ?(x),

• если t = f (t1 , t2 , ..., tn ), где t1 , . . . , tn ? TER(L? ), то где f ? Funcn , то
[t] := f M ([t1 ], ..., [tk ]).

Заметим, что приведенные правила корректно определяют функцию [ ] на всем
множестве TER(L? ).
Теперь мы можем наконец определить понятие истинностного значения фор-
мулы P ? L? в интерпретации (M, ?).

Определение 2.6 Истинностным значением формулы P ? L? в интерпрета-
ции
(M, ?) называется число v(P) ? {0, 1}, определяемое по следующим правилам:

1. если P – атомная формула, т. е. P = A(t1 , ..., tn ), A ? Predn , t1 , . . . tn ?
TER(L? ), то v(P) := AM ([t1 ], ..., [tk ]),

2. если P = ¬Q, то v(P) := 1 ? v(Q),

3. если P = Q ? S, то v(P) := min{v(Q), v(S)},

4. если P = Q ? S, то v(P) := max{v(Q), v(S)},

5. если P = Q > S, то v(P) := max{1 ? v(Q), v(S)},

6. если P = ?xQ, то v(P) := min{v[a/x] (Q) : a ? M }, где va (Q) – ис-
тинностное значение формулы Q в интерпретации (M, ?[a/x] ), а функция
?[a/x] : Var > M определена соотношениями ?[a/x] (y) := ?(y) при y = x, и
?[a/x] (x) := a,
16 Языки логики предикатов первого порядка


7. если P = ?xQ(x), то v(P) := max{v[a/x] (Q) : a ? M }, где v[a/x] (Q) – истин-
ностное значение формулы Q в интерпретации (M, ?[a/x] ), определенной
выше.

Определение 2.7 Будем говорить, что формула P истинна в интерпретации
(M, ?), если v(P) = 1, и ложна, если v(P) = 0.

Будем писать (M, ?) |= P, если v(P) = 1 в интерпретации (M, ?).

Определение 2.8 Будем говорить, что формула P:
• выполнима в алгебраической системе M, если (M, ?) |= P для какой-либо
интерпретации (M, ?);

• выполнима, если она выполнима в какой-либо алгебраической системе;

• тавтология, если она выполнима в любой алгебраической системе;

• противоречива, если она невыполнима.

Определение 2.9 Алгебраическая система M называется моделью формулы
P, если (M, ?) |= P для любой интерпретации (M, ?). При этом пишут M |=
P. Формула P называется истинной, если у нее есть модель.

Определение 2.10 Формула P называется семантическим следствием мно-
жества формул ?, если из того, что (M, ?) |= Q для всех одновременно Q ? ?,
следует (M, ?) |= P. В этом случае принято писать ? |= P.

Определение 2.11 Формулы P, Q называются семантически эквивалентны-
ми, если v(P) = v(Q) в любой интерпретации. В этом случае пишут P ? Q.

Пример 2.2 Пусть ? = {c, f 1 , g 2 , A2 , B 1 }, где c – символ предметной константы,
f , g – одноместный и двуместный функциональные символы, соответственно, A
– двуместный предикатный символ, B – одноместный предикатный символ. В
качестве универсума выберем множество Z+ = N ? {0} неотрицательных целых
0
чисел. Зададим алгебраическую систему для L? , положив:
cM := 0,
f M (n) := n + 1,
g M (m, n) := m + n,
1, m > n
AM (m, n) :=
0, m ? n,
1, n простое число
B M (n) :=
0, n составное число
2.4 Семантика языков логики первого порядка 17


Пусть ?(y) := 2. Тогда формула P := ?xA(x, f (x)) ? B(g(c, y)) истинна, т. е.
v(P) = 1. В данной алгебраической системе формула P выражает следующее
утверждение о натуральных числах: “Либо n + 1 < n для любого числа n, либо
y + 0 – простое число”. Если в той же алгебраической системе положить ?(y) := 4,
то в такой интерпретации формула P окажется ложной, т. е. v(P) = 0.
Заметим, что истинностное значение формулы P не зависит от интерпретации
связанной переменной.

Рассмотрим еще один любопытный пример.

Пример 2.3 (Парадокс брадобрея) В одном городе жил брадобрей, который
брил всех тех, и только тех, кто не брил самого себя. Кто брил брадобрея? Па-
радокс заключается в том, что попытка дать ответ на этот вопрос приводит к
замкнутому кругу рассуждений. А именно, если брадобрей брил себя сам, то он
не мог брить себя сам, так как он брил только тех, кто не брил самого себя, и
наоборот. Объяснение состоит в противоречивости основного утверждения.
Запишем на формальном языке логики первого порядка формулу, выража-
ющую “парадокс брадобрея”. Для этого в сигнатуре нам понадобится бинарный
предикатный символ, выражающий отношение “бреет”: R(x, y) значит x бреет
y. Рассмотрим сигнатуру ? = {b, R}, где символ константы b – это брадобрей.
Утверждение “брадобрей бреет тех и только тех, кто не бреет самого себя” запи-
сывается тогда в виде формулы:

P := ?x(¬R(x, x) > R(b, x)) ? ?x(R(b, x) > ¬R(x, x))

Достаточно простого подсчета в соответствии с определением истинностного зна-
чения, чтобы убедиться в том, что эта формула не выполняется ни в какой ал-
гебраической сестеме.

Упражнение 2.1 Покажите справедливость следующих утверждений:

¬?xP (x) ? ?x¬P (x),
¬?xP (x) ? ?x¬P (x)

Определение 2.12 Будем называть замыканием формулы P со свободными пе-
ременными Free(P) = {x1 , x2 , . . . , xk } формулу

Cl(P) := ?x1 , ?x2 , . . . , ?xk P

Теорема 2.3 Алгебраическая система M являeтся моделью формулы P, если
и только если M является моделью замыкания P, т. е. M |= P если и только
если M |= Cl(P).
18 Языки логики второго порядка


Упражнение 2.2 Доказать теорему о замыкании.

Определение 2.13 Язык логики первого порядка, сигнатура которого содер-
жит счетный набор символов констант, счетный набор функциональных сим-
волов и счетный набор предикатных символов любой арности будем обозначать
L?? . Очевидно, что при этом любой другой язык логики первого порядка с не
более чем счетным алфавитом можно, не ограничивая общности, считать со-
держащимся в L?? .


3 Языки логики второго порядка
Языки логики второго порядка отличаются от языков логики первого порядка
наличием в алфавите дополнительно символов предикатных переменных (для
которых мы резервируем большие латинские буквы X, Y , Z, возможно, с цифро-
выми индексами), а также наличием дополнительных формул вида ?X Q, ?X Q
с использованием символов предикатных переменных.
Множество предикатных переменных алфавита A языка логики второго по-
рядка будем обозначать VarPred. Если надо подчеркнуть, что речь идет о мно-
жестве k-арных предикатных переменных, то будем писать VarPredk . Таким
образом,

A = Const ? Func ? Pred ? VarPred ? Var ? Log ? Aux.

Термы языкa логики второго порядка определяются так же, как и термы язы-
ка логики первого порядка, а формулы отличаются возможностью использовать
предикатные переменные после кванторов:

< атомная формула > ::= < n ? арный пред. символ > (< терм >, ...)
| < n ? арная пред. переменная > (< терм >, . . .),
< формула > ::= < атомная формула > | (¬ < формула >)
|(< формула > ? < формула >)
|(< формула > ? < формула >)
|(< формула >>< формула >)
|(? < переменная >< формула >)
|(? < переменная >< формула >)
|((? < пред. переменная >< X >) < формула >)
|((? < пред. переменная >< X >) < формула >),
< терм > ::= < константа >
| < переменная >
| < n ? арный функ. символ > (< терм >, ...).
19


Чтобы не писать лишних скобок, мы применяем ранее введенное правило при-
оритетов операций:

P r (?) = P r (?) = P r (¬) > P r (?) > P r (?) > P r (>) .

Очевидно, чтобы интерпретировать формулы языка логики второго порядка,
достаточно лишь слегка скорректировать сформулированные правила для семан-
тики языков первого порядка, добавив возможность интерпретировать “новые”
формулы с предикатными переменными. Приведем поэтому только те определе-
ния, которые существенно меняются по сравнению с семантикой языков первого
порядка.

Определение 3.1 Интерпретацией для языка логики второго порядка назы-
вается тройка (M, ?, ?), где M – алгебраическая система, ?: Var > M , ? :
VarPredk > Bk , Bk := ? : L > {0, 1} L ? M k .

Таким образом, если символ предметной переменной интерпретируется эле-
ментом выбранного универсума, то символ k-арной предикатной переменной ин-
терпретируется характеристической функцией k-арного отношения на универсу-
ме.
Для вычисления истинностного значения формул языка логики второго по-
рядка необходимо в дополнение к соответствующим правилам, сформулирован-
ным для логики первого порядка, использовать следующие правила:

(i) v(X k (t1 , . . . , tk )) := ?(X k )([t1 ], ..., [tk ]), где X k ? VarPredk , а все ti ? TER;

(ii) v(?Y (P)) := min v?Y (P) : ? ? Bk ,

(iii) v(?Y (P)) := max v?Y (P) : ? ? Bk ,

где символом v?Y (P) обозначено истинностное значение формулы P в интерпре-
тации (M, ?, ?Y ),
? ? Bk , X = Y
?Y (X) :=
?(X), X = Y.

4 Логические языки с равенством
Очень часто в алфавит языков логики первого или второго порядка, предназна-
ченных для формализации математических или естественнонаучных утвержде-
ний, включается двуместный предикатный символ равенства, обозначаемый, как
правило, символом =. Такие языки будем называть языками с равенством. За-
метим, что вместо = (x, y) принято писать x = y.
20 Логические языки с равенством


Пусть задана алгебраическая система M для интерпретации формул языка с
равенством. Вообще говоря, если ничего дополнительно не требовать, то преди-
катному символу равенства может соответствовать в ней двуместное отношение,
никак не соотносящееся с привычным для нас понятием равенства. Чтобы избе-
жать такой ситуации, принято требовать, чтобы в M был выполним набор пред-
ложений, называемых аксиомами равенства, характеризующих особые свойства
отношения равенства.
Для языка первого порядка аксиомы равенства следующие:

(R) ?x (x = x),

(S) ?x?y(x = y > y = x),

(T ) ?x?y?z(x = y ? y = z > x = z),

(F ) ?x1 . . . ?xn ?y1 . . . ?yn ((x1 = y1 ? x2 = y2 ? . . . ? xn = yn ) > (?n (x1 , . . . , xn ) =
?n (y1 , . . . , yn )),

(P ) ?x1 . . . ?xn ?y1 . . . ?yn ((x1 = y1 ? x2 = y2 ? . . . ? xn = yn ) > (P n (x1 , . . . , xn ) =
P n (y1 , . . . , yn )).

Здесь (R), (S), (T ) – аксиомы, выражающие, соответственно, рефлексивность,
симметричность и транзитивность отношения равенства. (F ) и (P ) – это схе-
мы аксиом, т.е. “шаблоны” бесконечного, вообще говоря, множества аксиом. От-
дельные аксиомы получаются из схем (F ) и (P ) подстановкой вместо ?n любой
выразимой в рассматриваемом языке n-местной функции (т.е. терма с n различ-
ными символами переменных), а вместо P n – любого выразимого в этом язы-
ке n-местного предиката (т.е. атомной формулы с n свободными переменными).
Получаемые таким образом аксиомы называются вариантами соответствующих
схем аксиом. Схемы аксиом (F ) и (P ) выражают, соответственно, неразличимость
“равных” объектов (элементов универсума) при помощи выразимых в данном
языке функций и предикатов.
Для языка логики второго порядка набор аксиом равенства состоит из ак-
сиом (R), (S), (T ) и аксиом (F ) и (P ), заменяющих схемы аксиом (F ) и (P )
соответственно:

(F ) ?f n ?x1 . . . ?xn ?y1 . . . ?yn ((x1 = y1 ? x2 = y2 ? . . . ? xn = yn ) >
(f n (x1 , . . . , xn ) = f n (y1 , . . . , yn )),

<< Пред. стр.

стр. 2
(общее количество: 9)

ОГЛАВЛЕНИЕ

След. стр. >>