Дискретка

определяется значениями истинности высказываний A, B, сразу вытекает следующее важное утверждение.

Лемма 2. (1) Всякое высказывание эквивалентно самому себе.

(2)Если высказывание A эквивалентно высказыванию B, то высказывание B эквивалентно высказыванию A.

(3)Если высказывание A эквивалентно высказыванию B, а высказывание B эквивалентно высказыванию C, то высказывание A эквивалентно высказыванию C.

(4)Если высказывание A1 эквивалентно высказыванию A, а высказывание B1 эквивалентно высказыванию B, то высказывания A1&B1, A1 _B1, :A1, A1 ! B1, A1 $ B1 эквивалентны соответственно высказываниям A&B, A _ B, :A, A ! B,

A $ B.

Первые три утверждения леммы показывают, что эквивалентность высказываний действительно является отношением эквивалентности на множестве всех высказываний. Поэтому множество высказываний разбивается в объединение классов эквивалентности. Пусть X

множество классов эквивалентности высказываний. Класс эквивалентности, содержащий высказывание A, будем обозначать через

[A]. Определим на X действия сложения, умножения и дополнения, положив

[A] + [B] = [(A _ B)]; [A] [B] = [(A&B)]; [A] = [(:A)];

последнее утверждение леммы показывает, что эти определения не зависят от выбора высказываний, представляющих классы эквивалентности. Обозначим также через 0 и 1 классы [л] и [и]. Как часто

бывает в алгебре, классы эквивалентности [xi] символов переменных мы будем обозначать теми же буквами xi. Таким образом, xi, ðàñ- сматриваемый как элемент X это класс [xi]

Теорема 4. Множество X с введенными выше операциями является свободной булевой алгеброй со свободными образующими xi, i = 1; 2; : : : . Для любых высказываний A, B выполняются соотношения [A ! B] = [A] + [A] [B], [A $ B] = [A] [B] + [A] [B] . Выска- зывания A, B эквивалентны тогда и только тогда, когда [A] = [B]. Высказывание A является тавтологией тогда и только тогда, когда [A] = [и] = 1.

Доказательство. Последние два утверждения приведены для полноты и фактически содержатся в самом определении множества X.

Далее, непосредственная проверка показывает, что следующие пары высказываний эквивалентны, то есть имеют одинаковые функции истинности:

11

(6)A&(:A) è (ë), A_(:A) è (è), :(A_B) è (:A)&(:B), :(A&B) è (:A) _ (:B), :(:A) è A;

(7)A ! B è (:A) _ (A&B), A $ B è (A&B) _ ((:A)&(:B)).

Все утверждения теоремы, кроме того, что элементы xi являются свободными образующими X, следуют отсюда; в частности, эквива-

лентность пар высказываний, собранных в (1)-(6), показывает, что выполняются все аксиомы булевой алгебры.

Ясно, что элементы xi порождают алгебру X; для того, чтобы показать, что они являются свободными образующими X, достаточно проверить, что для любого n элементы x1,. . . ,xn свободно порождают

алгебру S(x1; : : : ; xn), то есть что для любых различных подмножеств I, J множества f0; 1gn элементы

различны. Но эти элементы являются классами эквивалентности высказываний

которые не эквивалентны, ибо по следствию 1 из x 2.1 они имеют различные функции истинности.

6. Каноническая дизъюнктивно-конъюнктивная форма высказывания.

Теорема 5. Всякое высказывание, в запись которого не входят никакие символы переменных, кроме x1; : : : ; xn, эквивалентно единст- венному высказыванию вида

Эта теорема немедленно следует из теоремы предыдущего пункта и из того, что всякий элемент свободной булевой алгебры, порожден- ной элементами x1; : : : ; xn, однозначно представим в виде

для некоторого подмножества I f1; 1gn. Такой представитель

класса эквивалентных высказываний называется канонической дизъ- юнктивно-конъюнктивной формой высказывания.

12

7. Выводимость. Пусть S некоторое множество высказываний; мы говорим, что высказывание A выводимо из множества высказываний S и записываем это в виде S ` A, если существует конечное

(быть может, пустое) множество высказываний Y1; : : : ; Ym 2 S, такое что высказывание (Y1& : : : &Ym) ! A является тождественно истинным высказыванием (тавтологией). Пусть A тавтология; поскольку высказывание (и) ! A тоже является тавтологией, а тождественно

истинное высказывание и это конъюнкция пустого множества высказываний, то высказывание A выводимо из S.

Теорема 6. Высказывание A выводимо из множества высказываний S тогда и только тогда, когда его класс [A] в булевой алгебре высказываний X принадлежит дуальному идеалу, порожденному классами [Y ] всех высказываний Y 2 S.

Доказательство. Пусть S ` A; тогда существуют такие высказывания Y1; : : : ; Ym 2 S, что высказывание (Y1& : : : &Ym) ! A тождественно истинно. Обозначим через Z высказывание Y1& : : : &Ym. Ïî теореме 4 тождественная истинность высказывания Z ! A означа- ет, что [Z] + [Z][A] = 1. Домножив обе части этого равенства на [Z], получаем: [Z] = [Z]([Z] + [Z][A]) = [Z][A], откуда следует, что элемент

[A] = [A]([Z]+[Z] ) = [A][Z]+[A][Z] = [Z]+[A][Z] = [Y1] : : : [Yn]+[A][Z]

принадлежит дуальному идеалу булевой алгебры X, порожденному элементами [Y1],. . . ,[Ym].

Обратно, пусть класс эквивалентности [A] высказывания A при-

надлежит дуальному идеалу, порожденному классами высказываний, принадлежащих S. По теореме 3 из x 2.4 существуют высказы-

вания Y1; : : : ; Yn 2 S и высказывание X, такие что [A] = [Y1] : : : [Yn] +

[X]. Обозначим, как и выше, через Z высказывание Y1& : : : &Yn; òî- гда [A] = [Z]+[X]. Находим теперь, что [Z] +[Z][A] = [Z] +[Z]([Z]+

[X]) = [Z] +[Z]+[Z][X] = 1, а это означает, что высказывание Z ! A тождественно истинно, то есть что высказывание A выводимо из высказывания Z = Y1& : : : &Yn.

8. Правило силлогизма. Покажем, что если высказывание выводимо из множества высказываний S, то оно может быть получено многократным применением нескольких простых правил.

Теорема 7. Пусть S некоторое множество высказываний.

(1)Если X 2 S, то X выводимо из S.

(2)Если высказывание X тавтология, то X выводимо из S.

(3)Если высказывания X, X ! Y выводимы из S, то и высказывание Y выводимо из S.

(4)Любое высказывание, выводимое из S, может быть получено многократным применением правил (1) (3).

13

Доказательство. Утверждение (2) уже было отмечено выше, а утверждение (1) тривиально: высказывание X ! X является тавтоло-

гией. Докажем теперь (3). Пусть I дуальный идеал алгебры высказываний X, порожденный классами всех высказываний из S. Если высказывания X, X ! Y выводимы из S, то по теореме 6 их классы [X], [X ! Y ] = [X] + [X][Y ] принадлежат I, а потому и [Y ] = [Y ] + [X]([X] + [X][Y ]) 2 I, а это и значит, по той же теореме, что высказывание Y выводимо из S.

Несколько сложнее доказывается обратное утверждение (4). Сна- чала индукцией по m покажем, что если высказывания Y1,. . . ,Ym принадлежат S, то высказывание Y1& : : : &Ym получается применени- ем правил (1)-(3). База индукции доставляется правилом (1). Пусть m > 1 и уже доказано, что высказывание Y1& : : : &Ym 1 получается применением правил (1)-(3). Высказывание

(Y1& : : : &Ym 1) ! (Ym ! (Y1& : : : &Ym))

является тавтологией (см. конец x 2.2), то есть оно получается при

помощи правила (2). Применяя к последним двум высказываниям правило (3), видим, что высказывание Ym ! (Y1& : : : &Ym) получа-

ется применением правил (1)-(3). Опять применяя правило (3), на сей раз к высказываниям Ym 2 S, Ym ! (Y1& : : : &Ym), найдем, что

высказывание Y1& : : : &Ym получается применением правил (1)-(3). Пусть высказывание A выводимо из S; тогда найдутся такие вы-

сказывания Y1; : : : ; Ym 2 S, что высказывание (Y1& : : : &Ym) ! Aтавтология, то есть оно получается при помощи правила (2). Но мы только что доказали, что высказывание Y1& : : : &Ym получается применением правил (1)-(3). Высказывание A получается из преды-

дущих двух высказываний по правилу (3). Теорема полностью доказана.

Правило (3) называется правилом силлогизма, или modus ponens. Обычно его иллюстрируют следующим рассуждением:

Конечно, этот пример не совсем точен. Правильнее здесь было бы вместо первого высказывания поставить его специальный случай: "Если Сократ человек, то Сократ смертен".

Обратимся теперь к правилу (2). Строго говоря, это не одно правило, а бесконечно много правил, потому что имеется бесконечно много тавтологий. Однако, используя modus ponens и правило подстановки

можно вывести все тавтологии из некоторого конечного множества тавтологий. Этот основной конечный набор тавтологий можно выбрать многими способами; приведем из возможных вариантов.

14

Теорема 8. Любая тавтология может быть получена при помощи правил подстановки и силлогизма из тавтологий (1) (18), приве-

денных в x 2.2.

Указанный в теореме набор (1)-(18) не минимален, некоторые входящие в него тавтологии могут быть выведены из других. Но он представляется наиболее естественным: тавтологии (6)-(18) по существу совпадают с аксиомами булевой алгебры, тавтологии (4) и (5) выражают характеристические свойства дизъюнкции и конъюнкции, а остальные тавтологии из этого набора сводят импликацию и эквивалентность к булевым операциям.

Мы опускаем доказательство теоремы 8: она нам не понадобится.

Следствие 3. Пусть S некоторое множество высказываний. Любое высказывание, выводимое из S, может быть получено из тавтологий (1) (18) и из высказываний, принадлежащих S, многократным применением правил подстановки и силлогизма.

9. Непротиворечивость. Будем говорить, что множество S выска-

зываний противоречиво, если тождественно ложное высказывание л выводимо из S, то есть S ` л. Если же тождественно ложное выска-

зывание не выводимо из S, то множество высказываний S называ-

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

идеал, порожденный классами всех высказываний из S, содержит класс 0 = [л]. Но тогда этот дуальный идеал содержит также любой элемент x = 0 y + x булевой алгебры высказываний X, то есть он совпадает с X. Таким образом, из противоречивого множества высказываний выводимо любое высказывание.

x 3. Правильно построенные формулы

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

только высказывания, но и предикаты. Как и при построении алгебры высказываний, мы начнем с задания алфавита; он включает не только те буквы, которые использовались в теории высказываний, но и ряд новых букв. Вот этот алфавит:

; è ë ( ) = & _ : ! $ 8 9 cn xn Pn

(n = 1; 2; 3; : : : ). Этот алфавит бесконечен, но, как и в исчислении

высказываний, можно свести его к конечному алфавиту, введя вместо трех бесконечных серий букв три буквы c, x, P и еще одну букву 0 и обозначив c1 = c, x1 = x, P1 = P , c2 = c0, x3 = x00 и т.д. Буквы ci будем называть символами констант, буквы xi символами перемен- ных, буквы Pi символами предикатов. В дальнейшем мы обычно не будем строго следовать этой системе обозначений и будем использовать буквы c; d; : : : (возможно, с индексами) для записи символов

15

констант, буквы x; y; z; : : : для записи символов переменных, буквы P; Q; R : : : для записи символов предикатов. Каждому символу

предиката соотносится некоторое натуральное число; если символу P соответствует число n, то говорим, что P символ n-местного

предиката.

Не все слова представляют для нас интерес: некоторые из них просто бессмысленные наборы букв. Следующее определение вводит сразу два понятия: правильно построенная формула и свободное или связанное вхождение символа переменной в не¼. В дальнейшем мы будем называть правильно построенную формулу просто формулой, поскольку никаких других формул у нас не будет.

Определение. (1) (и) и (л) формулы;

(2)(x = y), (x = c), (c = d) формулы, и все вхождения символов переменных в них свободные;

(3)если P символ r-местного предиката, и каждая из букв t1; : : : ; tr обозначает символ переменной или символ константы, то P (t1; : : : ; tr) формула, и все вхождения символов переменных в не¼ свободны;

(4)если A, B формулы, то (A&B), (A_B), (A ! B), (A $ B), (:A) тоже формулы; при этом каждое свободное (связанное) вхождение символа переменной в A или B остается свободным (связанным) и в (A&B), (A _ B), (A ! B), (A $ B),

(:A);

(5)если A формула, все вхождения символа переменной x в которую свободны, то (8xA) и (9xA) формулы, все вхождения символа переменной x в которые связанные, а вхож-

дения символов остальных переменных такие же, как в

A.

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

В определении формулы важную роль играют скобки; они дают возможность однозначно восстановить построение формулы из простейших элементов и, л, xn, cn, Pn(t1; : : : ; tr). Однако, без ущерба для

понимания некоторые скобки можно для краткости опускать, если договориться, что операция : предшествует операциям &, _, а эти

две операции предшествуют операциям !, $ (так же, как в алгеб-

ре возведение в степень предшествует умножению и делению, а они предшествуют сложению и вычитанию). Любая формула заключена в скобки; эти наружные скобки мы, как правило, тоже будем опускать. Наконец, мы будем опускать скобки в конъюнкциях и дизъюнкциях более чем двух выражений, считая, что сначала действие производится над первыми двумя выражениями, затем над полученным выражением и третьим выражением и т.д. Например, полной записью формулы x1&x2&x3&x4 будет (((x1&x2)&x3)&x4). Учитывая все

16

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

Прежде, чем сформулировать следующее определение, рассмотрим ситуацию, несколько напоминающую нашу. Пусть f(x) неко-

n

торая функция натурального аргумента. Тогда выражения P f(s),

s=1

n

P

f(t) являются функциями только от верхнего предела суммирова-

t=1

ния n и не зависят от "связанных переменных" s, t. Поэтому обычно

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

Определение. Пусть A, A1 формулы; будем считать, что A A1, если A можно преобразовать в A1, применив несколько раз сле- дующие правила (1) (3).

(1)Если A формула, то A A.

(2)åñëè A, B, A1, B1 формулы, и A A1, B B1, òî (A&B) (A1&B1), (A _ B) (A1 _ B1), (A ! B) (A1 ! B1), (A $ B) (A1 $ B1), (:A) (:A1).

(3)если A(x) формула, y символ переменной, не входящей свободно в A(x) и A(y) формула, получающаяся из слова A(x) заменой всех свободных вхождений символа переменной x на символ переменной y, то

(8xA(x)) (8yA(y)); (9xA(x)) (9yA(y)):

Иначе говоря, A A1, если слово A1 получается из слова A заме-

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

Åñëè A, A1 формулы, и A A1, то мы отождествляем A и A1,

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

Формула, в которую ни один символ переменной не входит свободно, называется суждением. Легко понять, что суждение это формализация понятия математического утверждения (теоремы, леммы, предложения и т.п.). Итак, в этом параграфе мы ввели язык, на котором можно формулировать математические утверждения, и теперь надо понять, что такое логически корректное доказательство таких утверждений. Но сначала укажем, как можно связать построенную формальную схему с содержательным описанием высказываний и предикатов, данным в x 1.

17

x 4. Интерпретации символов констант и предикатов. Модели

1. Интерпретации символов констант и предикатов. Содержательное описание высказываний и предикатов из x 1 получается из формальной схемы x 3 при интерпретировании символов констант и предикатов в некотором множестве. Пусть C множество символов констант, а P множество символов предикатов. Для самого исчисления предикатов C = fc1; c2; : : : g, P = fP1; P2; : : : g; однако в дальнейшем мы будем допускать в качестве C и P любые множества,

поскольку основные содержательные результаты не зависят от конкретного вида множеств символов констант и предикатов. Пусть M

множество, и пусть каждому символу константы c 2 C сопоставлен

элемент cM 2 M, а каждому символу n-местного предиката P 2 P сопоставлено подмножество PM n-й декартовой степени Mn множе- ства M. Набор, состоящий из множества M, элементов cM (c 2 C) и подмножеств PM (P 2 P) называется интерпретацией множеств символов констант C и символов предикатов P.

2. Истинность в интерпретации. Пусть fM; cM ; PM g интерпретация множества символов констант C и множества символов предикатов P. Далее, пусть A = A(x1; : : : ; xN ) формула со свободными символами переменных x1; : : : ; xN , в записи которой использованы

только символы констант и предикатов из этих множеств. Для любых элементов m1; : : : ; mN 2 M присвоим выражению A(m1; : : : ; mN )

значение истинности в нашей интерпретации. Сделаем это индукцией по построению формулы A. Выражения c = d, c = m, m = m0,

ãäå c; d 2 C, m; m0 2 M, истинны в интерпретации M тогда и только тогда, когда, соответственно, cM = dM èëè cM = m èëè m = m0. Выражение P (t1; : : : ; tn), в котором каждый символ ti означает или элемент из M, или символ константы из C, истинно в интерпрета-

ции M тогда и только тогда, когда (m1; : : : ; mn) 2 PM , ãäå mi = ti, åñëè ti элемент из M, и mi = (ti)M , åñëè ti 2 C символ константы. Значения истинности для формул A&B, A _ B, A ! B,

A $ B, :A определяются по правилам исчисления высказываний. Если формула A(x1; : : : ; xN ) имеет вид 8xB(x; x1; : : : ; xN ), то выражение A(m1; : : : ; mN ) считается истинным тогда и только тогда, когда выражение B(m; m1; : : : ; mN ) истинно для любого m 2 M. Наконец, если формула A(x1; : : : ; xN ) имеет вид 9xB(x; x1; : : : ; xN ), то выражение A(m1; : : : ; mN ) считается истинным тогда и только тогда, когда найдется такой элемент m 2 M, что выражение B(m; m1; : : : ; mN ) истинно.

3. Модели. Начиная отсюда, для множества символов констант Cи множества символов предикатов P будем обозначать через A(C; P)

18

множество всех суждений, в записи которых участвуют лишь символы констант, принадлежащие C, и символы предикатов, принадлежа-

щие P. Иногда мы будем опускать упоминание о множестве символов предикатов и писать A(C) вместо A(C; P). Пусть S 2 A(C; P) некоторое множество суждений. Интерпретация fM; cM ; PM g множеств символов констант C и символов предикатов P называется моделью S, если все суждения из S истинны в этой интерпретации.

В качестве примера рассмотрим модели следующего множества суждений с одним символом констант e и одним символом трехмест-

ного предиката P :

(1)8x8y9zP (x; y; z);

(2)8x8y8z8t((P (x; y; z)&P (x; y; t)) ! (z = t));

(3)8x8y8z8t8u8v8w((P (x; y; t)&P (t; z; u)&P (y; z; v)&P (x; v; w)) !

(u=w));

(4)8x(P (x; e; x)&P (e; x; x));

(5)8x9y(P (x; y; e)&P (y; x; e)).

Пусть G любая модель этой системы суждений. Запишем соотношение P (x; y; z) в виде xy = z; суждение (1) означает, что для любых двух элементов x; y 2 G существует их произведение z = xy, а суж-

дение (2) показывает, что это произведение определено однозначно. Таким образом, G является множеством с одной бинарной операци-

ей умножения. Остальные суждения утверждают, что это умножение ассоциативно, что e является единицей для него и что всякий элемент

из G обратим. Таким образом, моделями множества суждений (1)-(5) являются группы.

x 5. Правила вывода

1. Выводимые суждения. В исчислении высказываний мы выде-

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

(1)Правило подстановки. Пусть F (x1; : : : ; xm) тавтология ис- числения высказываний, и пусть Y1, . . . ,Ym произвольные суждения; тогда суждение, полученное из F (x1; : : : ; xm) подстановкой вместо каждого вхождения букв x1, . . . , xm ñîîò- ветствующих суждений Y1, . . . ,Ym, выводимо.

(2)Modus ponens. Если суждения X, X ! Y выводимы, то и

суждение Y выводимо.

19

Нам часто будет полезно следующее утверждение.

Предложение 1. Если суждения X и Y выводимы, то и суждение (X&Y ) выводимо.

Доказательство. Высказывание (x ! (y ! (x&y))) является тавтологией, поэтому суждение (X ! (Y ! (X&Y ))), полученное из этой тавтологии подстановкой, выводимо. Поскольку X выводимо, по правилу силлогизма выводимо суждение (Y ! (X&Y )), а поскольку Y

выводимо, снова по правилу силлогизма получается, что выводимо суждение X&Y .

Перед тем, как сформулировать другие правила построения универсально верных суждений, введем одно полезное обозначение. Пусть A(t) формула, а t символ константы или переменной, и пусть c

символ константы; через A(c) мы будем обозначать слово, получа- ющееся из слова A(t) заменой всех свободных вхождений t, если t символ переменной, или всех вхождений t, если t символ константы, на символ c.

(3) Свойства равенства. Выводимы следующие суждения:

(c = c); (c = d) ! (d = c); ((c = d)&(d = e)) ! (c = e):

(4)Если A(c) любое суждение, то (c = d) ! (A(c) ! A(d)) выводимое суждение.

(5)Пусть A(x) формула, в которую свободно входит только символ переменной x, B любое суждение; тогда

(8xA(x)) ! A(c);

(:(8xA(x))) $ (9x(:A(x)));

((8xA(x))&B) $ (8x(A(x)&B));

((9xA(x))&B) $ (9x(A(x)&B))

выводимые суждения.

Наконец, отметим еще один, принципиально отличный от предыдущих, способ построения выводимых суждений. Для того, чтобы обосновать его, дадим сначала его интуитивный смысл. Ясно, что если суждение 8xA(x) верно, то для любого символа константы должно

быть верно и суждение A(c); нам хотелось бы, чтобы и обратно, если суждение A(c) верно для всех символов констант, то было бы верно и суждение 8xA(x). Но верно для всех символов констант это

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

(6)Пусть A(x) формула с единственным символом переменной x, входящим в не¼ свободно. Если c символ константы, не входящий в A(x), и суждение A(c) выводимо, то и суждение

8xA(x) выводимо.

20