И.А. Пушкарев логика

Замечание. Множество F известно, поэтому верхняя граница размера шкалы Крипке известна. Поэтому все шкалы можно перебрать, поэтому интуиционистская пропозициональная теория разрешима.

4. Общая картина

Интуиционистское исчисление высказываний изначально появилось как синтаксическая теория. Подобрав ей подходящую семантику, удалось (ну… практически J…) показать, что она разрешима. Тоже полезное знаниеJ.

Синтаксис и семантика – равноправные партнёры.

52

Глава 2. Предикаты и выразимость §6. Формулы языка логики предикатов. Интерпретации

1. Обсуждение

рассмотренные теории оказались разрешимы и синтаксическая теория всюду

создать какую-нибудь безумную пропозициональную семантику… Впрочем,

семантика усложнится вместе с языком J.

Вспомним также, что имеется в виду обсуждать настоящую математику,

описывающую реальный мир, то есть некоторые множества и их элементы.

Поэтому следует ввести в рассмотрение функции, отношения и кванторыJ.

Иначе на программе Лейбница можно ставить крест.

Практически это означает, что класс высказываний суживается(все они теперь касаются только математики, притом – достаточно простой), но они перестают быть неделимыми единицами и начинают взаимодействовать.

Точнее – начинают взаимодействовать между собой использованные при их формулировании функции, отношения и кванторы.

2. Алфавит языка логики предикатов

В языке, о котором пойдёт речь, имеются четыре типа букв:

а) уже использованные символы логических связок: С, D, J, N, O, I и новые буквы А и Е, обозначающие кванторы (теперь буква А есть перевёрнутый квантор всеобщности " J);

б) множество V всевозможных предметных переменных(принимающих значения из некоторых множеств); элементы множества V записываются строчными латинскими буквами, возможно – с индексами;

в) множество F всевозможных функциональных символов;

+¥

– множество всевозможных символов m-арных отношений, получаем F = UFk ,

k=0

+¥

R = URk .

k=0

3.Термы

Необходимо рассмотреть два уровня обсуждения: на нижнем уровне при

изготавливаются простые высказывания, из которых, в свою очередь, на верхнем уровне (при помощи логических связок) создаются высказывания сложные (или лучше сказать – составные?).

Следует сознаться, что без функций (и, следовательно, без первого уровня)

можно обойтись. Например, функцию сложения (от двух переменных) можно

довольно замысловатой и превращает даже довольно простые вещи в очень сложные формулы, поэтому мы так делать не будем(в качестве упражнения

54

Определение 6.1. Множество Т называется множеством термов, если

удовлетворяет условиям:

fÎT , так что F0 Í T ;

(3)для любого множества W, удовлетворяющего условиям (1) и (2), T ÍW

.

Замечания. (1) Приведённое определение очень похоже на определение

множества пропозициональных формул. Напомним, что определения такого

вида называются индуктивными.

(2)Выражение f t1t2 ...tn заменяет собой более привычное f (t1,t2 ...,tn ) .

(3)Как и в случае формул, можно говорить не только о множестве, но и об

алгебре термов (только зачем?).

(4) Совершенно так же, как и для формул, доказывается, что множество Т существует и единственно (упражнение).

(5) Конечно плохо, что на функциональном символе нигде не написано количество аргументов функций, которые он может обозначать. Поэтому не может быть полной уверенности в том, что f xyz есть терм, это так только в том случае, если f Î F3 . Будем считать, что это подразумевается. Однако ясно,

что термом не является выражение f g xyz gzx , поскольку функция g не может быть одновременно от двух и от трёх аргументов.

4. Формулы логики предикатов

При определении формул возникает ещё одно осложнение. Из чистой

аккуратности хочется избежать появления странных формул типаAyRxz , в

которой квантор навешивается на переменную, отсутствующую в этой

формуле. Для этого одновременно с определением формулыр будет строиться некоторое множество, ей соответствующее – множество параметров этой формулы p (р). Параметры формулы иногда также называют её свободными

свободными, обычно называют связанными. Свободная переменная становится связанной, если навесить на неё квантор.

Определение 6.2. Множество Ф называется множеством формул логики

входящих в термы t1, t2 , ..., tn ;

(3)если p ÎФ , то и Np ÎФ , p (Np)= p (p);

(4)если p, q ÎФ , то и Cpq, Dpq, Jpq ÎФ ,

p(Cpq)= p (Dpq)= p (Jpq)= p (p)È p (q);

(5)если p ÎФ , x Îp (p), то Axp, Exp ÎФ , p (Axp)= p (Exp)= p (p)\ {x};

(6)если множество W удовлетворяет свойствам (1) – (5), то Ф ÍW .

Замечания. (1) Определение множества формул снова индуктивное.

символам. Символ Qt1t2 ...tn заменяет собой привычное Q(t1 , t2 , ..., tn ); на нём не написана арность отношения, так что в отсутствие коллизий всегда считается,

желании) их восстановить, заменив в пункте (5) определения формулу x Îp (p)

на более общую x ÎV .

56

(5) В формуле DAxSxyExQzx иксы, стоящие до и после буквыЕ –

различные! При этом оба вида иксов – связанные. Вообще, появление квантора слева «закрывает» (связывает!) переменную так же, как появление символа dx

заканчивает использование x в качестве переменной интегрирования.

(6) Впрочем, вполне возможно, что одна и та же буква использована для обозначения одной свободной и одной или нескольких связанных переменных:

DSxyExQzx .

(7) В действительности почти никогда не требуется разреша

использовать в формулах все возможные символы функций и отношений. Как

правило, рассматривается множество тех функций и отношений, которые предполагается использовать, у всех функциональных символов(явно или неявно) указывается количество аргументов, а у всех символов отношений– арность. Такой набор называется сигнатурой, и можно говорить о множествах формул данной сигнатуры.

$x1$x2 ...$xn S( f (x1, f (x2 , ..., f (xn-1, xn )...))), и даже более определённое

$n$x1$x2 ...$xn S( f (x1, f (x2 , ..., f (xn-1, xn )...))) формулой не является, потому что

неизвестно, сколько в ней переменных (как это – неизвестно? Их n штук J).

(10) Дав определения в терминах языка, полезно вернуться к скобочной

записи функций и отношений, равно как и к обычным обозначениям

логических связок: так понятнее J.

Лемма 6.1. Для любой формулы множество её параметров определено однозначно.

Доказательство проводится индукцией по множеству формул. Пусть U –

множество тех формул, для которых утверждение верно. Тогда U Í Ф и

удовлетворяет условиям (1) – (5) из определения множестваФ: если для

57

предыдущей формулы множество параметров было определено однозначно, то оно однозначно определено и для следующей, чуть более сложной(в

определении прямо написано, чему оно равно J). Тогда, в силу условия (6),

U = Ф .

QED

Пример. Формула p = "x$z"tG(x, f (y, t ))Ù S(f (y, f (t, z)), x, z ) является таковой только при условии, что f – символ функции двух переменных, G –

символ двухместного отношения, S – символ трёхместного отношения. При этом p (p)= {y}. Она является формулой потому, что формулами являются выражения $z"tG(x, f (y, t ))Ù S (f (y, f (t, z)), x, z),

"tG(x, f (y, t ))Ù S( f (y, f (t, z )), x, z), q = G(x, f (y, t ))Ù S( f (y, f (t, z )), x, z),

G(x, f (y, t )) и S (f (y, f (t, z)), x, z). Последние две формулы являются атомарными. Они, в свою очередь, являются формулами потому что выражения f (y, f (t, z)), f (y, t ), x, y, z являются термами. Далее,

p (p)= p (q)\ {x, z, t}= {x, y, z, t}\ {x, z, t}= {y}.

58

Пример. Рассмотрим аксиомы теории групп. При этом сигнатуры можно выбирать по-разному.

Вариант 1. Рассмотрим сигнатуру S1 = (*, =, ×-1, е), где * – символ функции двух переменных, ×-1 – символ функции одного переменного, е – символ функции от нуля переменных, то есть константы, = – символ двухместного отношения. Тогда аксиомы теории групп можно записать формулами так:

(Г1) "x"y"z((x * y)* z)= (x * (y * z ));

(Г2) "x(x * e = x)Ù (e * x = x);

(Г3) "x(x * x-1 = e)Ù (x-1 * x = e).

Вариант 2. Предположим, что решено не включать функцию обращения в сигнатуру, то есть рассмотреть сигнатуру поменьше: S2 = (*, =, е). Тогда вместо формулы (Г3) можно добавить формулу, которая её заменит:

(Г4) "x$y(x * y = e)Ù (y * x = e).

Вариант 3. Попробуем обойтись без термов. Заменим функциональный символ * символом трёхместного отношенияS, которое будем понимать так:

S (x, y, z )Û x * y = z . В этом случае вместо формулы(Г1) следует написать ужасное:

(Г5) $t$s$u$vS(x, y, t )Ù S(t, z, s)Ù S(y, z, u)Ù S(x, u, v)Ù (s = v).

6. Определение истинности

Пусть фиксирована сигнатура (и, соответственно, множество всех формул

этой сигнатуры) и некоторая её интерпретация. Значения термов и формул удобнее всего определять «коллективно», для всех термов и формул сразу.

предметного множества – её значение x(x).

(2) Пусть x – оценка. Определим значение [t](x ) терма t на оценке

индуктивно посредством правил:

Вернёмся к определению истинности.

(3) Значение [q](x ) формулы q на данной оценке в данной интерпретации может быть равно0 или 1 (истина или ложь) и определяется индуктивно посредством правил:

а) [O](x )= 0 , [I ](x )=1 для любой оценки ξ;

б) если q = At1...tn – атомарная формула, то [q](x )= [A][( t1 ](x ), ..., [tn ](x )), где

[A] – интерпретация символа n-арного отношения А;

в) [Nq](x )= Ø[q](x );

г) [Cpq](x )= [p](x )Ù [q](x ), [Dpq](x )= [p](x )Ú [q](x ),

[Jpq](x )= ([p](x )Þ [q](x )).

д) Для определения истинности формул вида Axp(x) и Exp(x) на оценке ξ следует рассмотреть множество I (x, x) всевозможных оценок, совпадающих с оценкой ξ всюду, кроме, возможно, её значения на переменной x. Положим:

i) [Axp(x)](x )=1 Û "z Î I (x, x) [p](z )=1;

суждением. Истинность суждения, очевидно, зависит только от интерпретации и не зависит от конкретной оценки.