Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Выбор базисных тавтологий ни в какой мере не однозначен. Наш список будет состоять из тавтологий А. О, А.1, А.2, А.З, В.1,
В.2 п. 3.4 и следующих тавтологий:
С.1. П(Р-П0)->(РД0), (РЛ<2)-П(Р-13); с.2. пР-^)-^(Ру<2). (Ру<2)-ПР-<г);
С.З. Р—+("](}-+ ~| (Р-^<2));
С.4. (Р-»<2) — (ПР—
С.5. пР-0<3)-+(сг-Р);
С.6. (Р —>? <2) Д (<2 —>• Р) ? (Р?--*Q);
С.7. ПРД0->П(Р-0).
Мы экономим не на размере базисного списка, а на длине доказательства предложения 5.1, поэтому список А.О—С.7 не является кратчайшим. Для логики 3\ это несущественно; лишь для видоизмененных логик типа интуиционистской требуется более осторожный анализ.
Доказательство. Пусть е — конечное множество формул Ь, Р —? логический многочлен (с фиксированным представлением) над е. Рассмотрим отображение V : е—»-{0, 1} и продолжим его на Р по тем же формулам, которые в п. 2.3 определяли функцию истинности | |. Положим
р°= I р> если
I Д Р, если V (Р) = 0.
5.2. Основная лемма.
Пусть е° = {0° | <2 0?}- Тогда для любого и имеем'. § и е°г-Р° (с помощью МР).
Лемма является оформлением следующей идеи. Естественно доказывать предложение 5.1 индукцией по длине тавтологии, но части тавтологии могут не быть тавтологиями. Операция, переводящая Р в Рг, насильственно делает любую формулу «и-истин-ной» и дает возможность провести индукцию.
5.3. Доказательство 5.1 с помощью основной леммы.
Пусть Р — тавтология и РХ,=Р для всех V (обозначения прежние). Положим 8={РЬ ..., Рг}.
По ОСНОВНОЙ лемме, § и {Р0!, ..., Рф} [— Р с помощью МР для любого и. Покажем, что тогда $ (Д |Р“ ,..., Р” } Н Р с помощью МР. Индукция вниз но г даст требуемое (предположение о том,
58
что Р есть логический многочлен от Рь . .Рт в индуктивном переходе не используется).
Лемма о дедукции 4.5 показывает, что $ и {Р° ,..., Р“ } |— р(Раг->-Р) с помощью МР: нужно обратиться к ее доказательству и удостовериться, что в выводе участвуют лишь тавтологии из Ф и МР, потому что веп не участвовал в выводе Р.
Так как для любого у существует и', совпадающее с о на Р,,... ..., Рг_1, но отличающееся на Рг, имеем: РГ~^Р и “] Рл — Р выводятся из и {Р^ > с помощью МР. С другой стороны, тавтология
С.4: (Рг —Р)1-* ((П1 Рг—*Р)—>Р) лежит в Дважды применяя МР, выводим Р.
5.4. Доказательстве основной леммы. Проведем индукцию по числу связок в представлении Р в виде логического многочлена над е. Если их нет, т. е. Р6Е?> утверждение очевидно. В противном случае Р имеет вид ~] Р или ф, <2г, где — одна
из бинарных связок.
а) Случай Р— ПС- Если у(<2) = <2, то (3°= ~] 0 = Р = Ра. Выводимость (?а=Ра из у га является индуктивным предположением. Если же У«2)=1, ТО <2° = <2, Р°=-]ПС- Здесь С выводится из |Ти80по индуктивному предположению, затем тавтология из ?:
~1~1Ф и МР дают вывод Р°.
б) Случай P = Q1>|<Q2. Сначала сведем в таблицу при разных сочетаниях >|с и 0(0,), о(02) формулы, выводы которых существуют по индуктивному предположению, и формулы, которые нужно вывести.
В столбцах для Д, V указаны такие формулы, из которых (<2, Д <32)п и (<2, V соответственно выводятся применением МР с помощью тавтологий из ЯГ (тавтологии В.1, В.2 п. 3.4).
«Выводимость» в комментариях к таблице означает «выводимость из 2Г и пары формул первого столбца с помощью МР».
2 а 2 а Даны выводы Нужно вывести
Л V « V
0 0 И«?!- П«1 1. (За (За 5. -]-]«л->--1<га) 13. С), а—У (}а
0 1 ~|<?1. <эа 2. 0, С}% 6. Т^а-»“^) 10. Оа-а-Оа 14. -| ^ *--у <1,)
1 0 о.. ~]<г. 3. -] «За -> <3а) 7. ~1 “1(<Э1^—1^) 11. -| (3, ^ (За 15. -| ((За «--*• (За)
1 1 <Эа. ?а 4. (^1 -V 3. ~| ((За -* “]0») 12. -| <3, (За 16. (За -а—* (За
Вывод формул 1 —16 (номера формул указаны в таблице). Вот простейшее соображение: если Р выводима, то для любой (2 формула <3->-Р тоже выводима (тавтология А.1 и МР).
59
Это сразу доставляет выводимость формул 2, 4, 10 и 12. Сняв в столбце Д двойные отрицания с помощью тавтологии В.1 и МР, получим выводимость формул 5 и 7. Вывод формул 4 в последней строке по симметрии дает вывод (Эг-^ь лемма 4.4 и тавтология
С.6 дают вывод формул 16 из и (Зг-^Фь
I выводится из и С.5 посредством МР. По симметрии выводится (22~>-<2, и затем 13 так же, как 16.
3 выводится из С.З: (2,-+ (~| <32^ П (С^ —>-С22)) и данных двукрат-
ным применением МР.
6 выводится из В.2: (2, —? (С! —* “| 0.2) и данных применением
МР, В1 и МР.
8 выводится из С.З: —> (~| ~] @2 -> ~| ($,-+ “] ф,))
9 выводится из С.З: ~10г —1 (П^! —^Фг)) двукрат-ным МР.
II выводится из В.2: ~] Q1 —* (“1 ;? С12) заменой на
по В.1 и МР.
14 выводится из С.7: 0,1 Д Q2 —? “] ((2г Q2) с помощью
леммы 4.4 и МР.
15 выводится аналогично 14.
Предложение 5.1 доказано.
5.5. Тавтологии и вероятность. Тавтологии — высказывания, истинные независимо от истинности или ложности своих «составных частей». Это утверждение сохраняется, даже если компонентам тавтологии придавать вероятностные значения истинности ||Р}[ в алгебре измеримых множеств какого-нибудь вероятностного пространства.
Например: тавтология ^ \/ 5 V I V 1 ^ — „то ли дождик, то
ли снег, то ли будет, то ли нет» — является достоверным прогнозом погоды, несмотря на крайнюю сложность метеорологического вероятностного пространства.
