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

21

5. Вывод. Выводимость

Вдействительности мышление устроено ещё чуть-чуть . сложнее

Повседневная практика показывает, что только самые простые теоремы

выводятся из одних лишь аксиом. Дальнейшая мыслительная деятельность

(2)В описанной ситуации говорят, что формула dn выводима из набора Р

ипишут: P f dn .

теоремой.

Доказательство. Вывод тривиально превращается в доказательство:

достаточно вместо посылки dk вставить доказательство теоремы dk .

QED

Замечание. Однако вполне возможно, что среди посылок встречаются формулы, не являющиеся ни теоремами, ни даже тавтологиями. Понятие вывода от этого не теряет своей осмысленности. У множества формул, которые можно получить как результат таких«незаконных доказательств», даже есть свой наглядный смысл: в него могут входить только те высказывания, которые получаются, если подставлять вместо пропозициональных переменных не

«какие попало» наборы простых высказываний, а только такие, которые не делают ложной ни одну использованную посылку. Можно сказать, что вывод –

22

это «условное» доказательство (в противовес доказательству обычному,

«безусловному»), а его результат– «условная тавтология». Сделанное соображение крайне важно, и в дальнейшем будет сильно обобщено, поэтому полезно оформить его в виде определения.

Определение 2.4. Пусть Р – множество формул, q – формула. Если любой набор значений переменных, обращающий все формулы множества Р в

истины, обращает в истину и q, то говорят, что q семантически следует из Р и

пишут P > q .

Использование этого определения позволяет уточнить замечание.

Теорема 2.2. (оправданность аксиоматизации)

P f q Þ P > q .

Доказательство. Индукция по длине вывода, т.е. по количеству формул в выводе. Если длина вывода равна1, то его единственная формула– либо

аксиома (которая является тавтологией), либо посылка (которая тривиально

данном наборе аргументов все посылки истинны, то на нём истинны и формулы r и r ® q . Следовательно, на этом наборе аргументов истинна и формула q (так

как при истинном значенииr единственный способ сделать импликацию истинной – это сделать истинной формулу q).

QED

23

6. Транзитивность выводимости

Следует отметить ещё одно свойство выводимости, которое тривиально обобщает лемму 2.1. и доказывается совершенно так же.

Лемма 2.3. (Транзитивность выводимости)

Пусть Р и Q – два множества формул, "q ÎQ P f q , Q f r . Тогда P f r .

Теорема 2.4. (Лемма о дедукции для исчисления высказываний)

Для любого множества формул Р и для любых формул q и r равносильны условия:

(1)P È {q}f r ;

(2)P f (q ® r ).

Замечание. Вместо P È {q} удобно писатьP, q. В дальнейшем будет

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

24

Шаг 1. Напишем последовательность формул

q ® d1, q ® d2 , ..., q ® dn (**). Разумеется, эта последовательность формул не

является выводом. Для того чтобы сделать её таковым, вставим в неё ещё некоторые формулы.

исчисления высказываний или посылками изР. Вставим перед каждой такой формулой ещё две:

a – посылка или аксиома; a ® (q ® a) – аксиома (А1).

Тогда формула q ® a становится результатом применения к ним правила

МР.

Шаг 4. Возможно, некоторые формулы di являются результатом

применения правила МР. Тогда существуют номера j, k < i , такие, что d j = a , dk = (a ® b), di = b . Соответственно, в последовательности (**) есть формулы q ® a , q ® (a ® b), которые можно использовать для вывода формулыq ® b .

Вставим перед последней формулой ещё две формулы:

(q ® (a ® b))® ((q ® a)® (q ® b)) – аксиома (А2);

(q ® a)® (q ® b) – результат применения правила МР.

Теперь и формула q ® b становится результатом применения правила

МР.

Заметим, что проведение этих шагов делает формулы последовательности

(**) «всё более и более доказанными», а последний шаг просто превращает эту последовательность в вывод.

QED

совершенно аналогично доказательству импликации (2) Þ(1).

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

Вывод является достаточно адекватным аналогом процесса мышления(и

даже может быть основан на неверных посылкахJ). Теории, построенные на основе различных вариантов выводов, и, соответственно, состоящие из теорем,

называются синтаксическими. Основной предмет изучения в математической логике – соотношение между синтаксисом и семантикой.

26

§3. Полнота исчисления высказываний 1. Мотивировка

С самого момента изобретения дедуктивного метода(то есть – со времён Евклида, а не Шерлока Холмса! J) математики мечтали установить важнейший факт: любое истинное утверждение может быть доказано. Нельзя сказать, что в противном случае математика стала бы намного менее осмысленным занятием,

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

Жизнь показала, что во многих случаях всё сложнее, но иногда этот факт всё-таки имеет место. В этом случае говорят, что в рассматриваемой ситуации имеет место теорема о полноте соответствующего исчисления. В этом параграфе будет показано, что для исчисления высказываний теорема о полноте верна. Итак, имеет место теорема.

Теорема 3.1. (Теорема о полноте исчисления высказываний)

Формула выводима в исчислении высказываний тогда и только тогда,

когда она является тавтологией. Символически: > q Û f q .

2. Первое доказательство

Естественно предположить, что имеет место более сильное утверждение:

P > q Û P f q . В одну сторону это утверждение даже доказано(теорема 2.2),

поэтому достаточно проверить импликации > q Þ f q и P > q Þ P f q (*).

Позднее мы покажем, что импликация (*) действительно верна. Однако

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

Для примера приведём некоторые выводы.

а) Первая выводимость:

p – посылка;

p ® (q ® (p Ù q)) – аксиома (А5);

q ® (p Ù q) – правило МР;

q – посылка;

p Ù q – правило МР.

28

б) Во многих случаях построение выводов основано на одной из

«дробей», приведённых в замечании к лемме о дедукции, именно – на правиле

P, q f r; P, q f Ør . Докажем это правило.

P f Øq

Согласно лемме о дедукции, если P, q f r , то P f (q ® r ). Пусть

d1, d2 , ..., dn = (q ® r ) – соответствующий вывод. Аналогично, если P, q f Ør ,

то P f (q ® Ør ), соответствующий вывод обозначимs1, s2 , ..., sm = (q ® Ør ).

Напишем второй вывод после первого и добавим к получившемуся выводу ещё три строки:

(q ® r )® ((q ® Ør )® Øq) – Аксиома (А10);

(q ® Ør )® Øq – правило МР;

Øq – правило МР.

в) Докажем выводимость Ø p f Ø(p Ù q), которая заменяет две указанные

выводимости (какие?). Согласно предыдущему пункту, для этого достаточно вывести из посылок Ø p и p Ù q две формулы вида r и Ør . В качестве таковых

подойдут, например, формулы p и Ø p . Вторая формула – просто одна из посылок, первая выводится так:

p Ù q – посылка;

(p Ù q)® p – аксиома (А3);

p – правило МР.

г) Докажем ещё одно правило из замечания к лемме о дедукции, именно –

P, r f s , то P f (r ® s), соответствующий вывод обозначим t1 , t2 , ..., tm = (r ® s).

Напишем второй вывод после первого и добавим к получившемуся выводу ещё пять строк:

(q ® s)® ((r ® s)® ((q Ú r )® s)) – Аксиома (А8);

обыкновенное доказательство.

QED

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

способ построения ужасен L).

(2) В том случае, когда доказываемое утверждение (например, по ошибке)

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

то не позволяющее построить» требуемое доказательство J.

(3) Рассмотренное доказательство полезно сравнить с примером,

рассмотренным в §1 и с материалом следующего параграфа.