Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Точный результат удобно формулировать в терминах булевых алгебр.
5.6. Булевы алгебры. Булева алгебра В — это множество с операцией ранга 1 и двумя операциями у, Л ранга 2, а также с двумя отмеченными элементами 0,1, которые удовлетворяют следующим аксиомам:
а) (а')'=а для всех аеЗ;
б) Д> V ассоциативны и коммутативны;
в) Л, V дистрибутивны друг относительно друга;
г) (а\/ Ь)’ — а’ /\Ь’, {а Д Ь)’ = а! \[Ь’;
д) ау а = а/\а~а;
е) 1 /\а=а; 0 \/а=а.
Примеры, а) В — множество всех частей множества Мг ' — дополнение, Д —пересечение, V — объединение, 0 — пустое подмножество, 1 — все М.
60
б) В — множество открыто-замкнутых подмножеств топологического пространства М с теми же операциями.
в) В — множество измеримых подмножеств вероятностного пространства М с теми же операциями.
Во всех этих случаях В можно отождествить с пространством характеристических функций соответствующих подмножеств (принимающих значения 1 на подмножество, 0 на дополнении).
5.7. Булева функция истинности. Пусть В — булева алгебра, 6 — некоторое множество формул языка Ь. Пусть || ||: г-+В—любое отображение. Продолжим его на логические многочлены над е (точнее, их представления) по рекурсивным формулам:
||Р<-*С!|| = (||Р]| ЛIIСII) V (II ^ II' ЛIIС !Г). ||Р-*<2|| = 1!р1ГVIIСI!» ЦРУ0|1Н|Р|М[311. [|РЛ<211Н1рЛЛ1]31!> 1Пр1Ы|Р|Г-
В случае В= {0, 1} эти формулы переходят в определения из п. 2.5. Отметим, что V и Л в левых и правых частях имеют разный смысл.
5.8. Предложение.
Пусть Р — логический многочлен— тавтология над г. Тогда для любого отображения |] || : е-кВ в любую булеву алгебру В имеем
\\Р\\ = 1.
Доказательство. Пример естественного отображения || || получается так: если задана интерпретация языка Ь в множестве М, то функции истинности \Р (I) можно рассматривать как характеристически^ функции выразимых подмножеств интерпретационного класса М (см. § 2). Поэтому наша обычная функция, истинности по существу принимает булевы значения. Они вкладываются в булеву алгебру всех подмножеств М, которая разлагается в прямое произведение двухточечных булевых алгебр {О, 1}. Поэтому здесь заключение тривиально следует из условия.
В общем случае можно было бы воспользоваться теоремой Стоуна о структуре булевых алгебр.
Вместо этого мы укажем, как редуцировать задачу к нескольким несложным вычислениям с помощью предложения 5.1. Для этого достаточно проверить || ||-истинность базисных тавтологий и сохранение || ||-истинности при применении МР. Например, если) ||Р|] = 1 И ||Р-^|| = 1, то ||Р|Г=0, ||Р||' V Л<211 = 1, откуда 1^11 = 1 в силу 5.6е: это решает вопрос об МР. Аналогично вычисляются значения истинности базисных тавтологий с помощью аксиом п. 5.6.
Булевы функции истинности будут основным инструментом в изложении метода форсинга Коэна в гл. III.
Отступление с кеннингами
1. Процесс, описанный в § 5, порождает всевозможные тавтологии с помощью конечного числа правил. В современной лингвистике попытка адекватного описания естественных языков посредством порождающих правил очень популярны (Н.‘ Хомский и др.), см., например, книгу А. В. Гладкого, И. А. Мельчука [24].
Многие психологи, однако, полагают, что эта концепция имеет мало отношения к реальному процессу речи. Последний, согласно одному из мнений, скорее уподобляется вероятностной игре, погоне, течению реки по местности со сложным рельефом. Выбор очередного слова при порождении фразы статистически определяется как общим формирующим принципом (мысль, ситуация, психологическое состояние), так и особенностями семантики, грамматического оформления, фонетики, ассоциативного облака уже сказанных слов.
Можно надеяться, что формальные грамматики более адекватны специальным фрагментам естественных языков, жестче организованным в том или ином смысле: скажем, языкам определенных поэтических или юридических систем. В этих фрагментах существенную роль играют «правила запрета», отсеивающие, например все тексты без выраженного ритмического рисунка. Даже поверхностная интроспекция позволяет удостовериться в психологической реальности таких правил при верифицировании. Это значительно менее очевидно относительно порождающих правил.
2. Все же существовала по крайней мере одна поэтическая система, в которой порождающие правила занимали важное место.
Одним из существенных элементов скальдической (древнеисландской) поэзии были специальные формулы, называемые кён-нингами. Кеннинг есть выражение, которое может заменить одно слово. Например,
„вьюга копий“ есть кеннинг „битвы “
древо битвы“ „война“
куст шлема“ метатель меча“ суть кеннинги „мужчины“
раздаватель золота“ „человека“
море телеги“ есть кеннинг „земли“
огонь войны“ есть кеннинг „золота“
небо песка“ ^ поле тюленя“ ) суть кеннинги „моря“ и т
Простой кеннинг — это кеннинг, никакая часть которого не является кеннингом. Приведенные выше примеры являются простыми кеннингами. Они играют роль аксиом, и создавать новые прос-
62
тьіе кеннинги, очевидно, имеют право только великие поэты. На долю невеликих поэтов остается создание новых кеннингов по правилам вывода. Правило вывода нового кеннинга из уже имеющихся: любое слово в одном из данных кеннингов может быть заменено его кеннингом (не обязательно простым). Пример сложного кеннинга с его расшифровкой (пример реальный):
