Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 14
Текст из файла (страница 14)
2]31. Провести подробно доказательство выводимости в интуиционистском исчислении высказываний всех перечисленных формул.С другой стороны, многие законы классической логики перестают быть выводимыми без закона исключённого третьего. Таковы,например, формулы¬¬p → p,p ∨ ¬p,¬p ∨ ¬¬p,(¬q → ¬p) → (p → q),¬(p ∧ q) → (¬p ∨ ¬q),((p ∨ q) → p) ∨ ((p ∨ q) → q).Мы пишем здесь переменные p и q, а не произвольные формулы,поскольку результат подстановки некоторых формул вместо p и qможет быть выводимой формулой.
Например, если вместо p в первуюиз перечисленных формул подставить формулу ¬A, то получитсявыводимая формула ¬¬¬A → ¬A.Довольно ясно, что эти формулы не согласуются с интуиционистским подходом. Например, в предпоследней формуле говорится, чтоесли мы опровергли предположение (p ∧ q), то мы можем указать наодно из предположений p и q и предъявить его опровержение. Врядли такой переход можно считать обоснованным с интуиционистскойточки зрения. Но, разумеется, формальный вопрос о выводимоститребует формального ответа.Начнём с закона исключённого третьего.Теорема 24.
Формула p ∨ ¬p не выводима в интуиционистскойлогике. В классической логике каждая пропозициональная переменная может принимать два значения — истина (И) и ложь (Л). Взависимости от значений переменных каждой формуле также приписывается значение И или Л. Расширим множество истинностныхзначений, добавив новое значение Н (если угодно, можно считать этосокращением слова «неизвестно»). Мы отождествляли И с единицей,а Л — с нулём, так что логично отождествить Н с числом 1/2.Мы докажем, что интуиционистски выводимые формулы всегдапринимают значение И, а формула p ∨ ¬p не такова, и потому невыводима.Чтобы определить значения формул в трёхзначной логике, нужно задать таблицы истинности для всех пропозициональных связок.[п.
4]Интуиционистская пропозициональная логика63Конъюнкцию определим как минимум из двух значений (так что,например, Л ∧ Н = Л, а И ∧ Н = Н), а дизъюнкцию — как максимум.Отрицание действует так: ¬И = Л, ¬Л = И, ¬Н = Л. (Последнееможет показаться странным: почему бы не считать, что ¬Н = Н?Оказывается, так нельзя — например, потому, что тогда формула¬(p∧¬p), которая выводима в интуиционистской логике, будет иметьзначение Н при p = Н.)Сложнее всего определение истинности для импликации.
Мы полагаем, что(И → x) = x и (Л → x) = Идля любого истинностного значения x, а также что(Н → Л) = Л,(Н → Н) = И и (Н → И) = И.Назовем формулу 3-тавтологией, если она принимает значениеИ при любых значениях переменных из множества {И, Л, Н}. Теперь надо проверить две вещи: (1) все аксиомы интуиционистскогоисчисления являются 3-тавтологиями; (2) если посылка импликациии вся импликация являются 3-тавтологиями, то и заключение тожеявляется 3-тавтологией.
Второе сразу ясно из определения импликации, а первое надо аккуратно проверять, составив таблицы для всехаксиом. Мы не будем этого подробно делать, поскольку это чистомеханическая проверка и поскольку чуть позже мы сможем вывестиэто из более общего утверждения.Следовательно, всякая интуиционистски выводимая формула является 3-тавтологией. Теперь заметим, что формула p∨¬p принимаетзначение Н при p = Н и потому не является 3-тавтологией — значит,невыводима. 32.
Покажите, что всякая 3-тавтология является тавтологией в обычном смысле.Использованный нами приём годится не всегда. Например, интуиционистски невыводимая формула ¬p ∨ ¬¬p является 3-тавтологией, поскольку (согласно нашему определению) формула ¬p можетпринимать только значения И и Л.33. Какие из перечисленных нами интуиционистски невыводимых формул являются 3-тавтологиями?Более общий способ установить недоказуемось (невыводимость)различных формул доставляют шкалы Крипке (или модели Крипке,как ещё говорят).Чтобы задать шкалу Крипке, нужно:64Исчисление высказываний[гл.
2]• указать частично упорядоченное множество hW, 6i, называемое множеством миров;• для каждого мира указать, какие из пропозициональных переменных считаются истинными в этом мире (остальные переменные считаются ложными в этом мире). Если переменная xистинна в мире w, мы пишем w x.При этом требуется, чтобы было выполнено следующее: если u 6 v иu x, то v x (область истинности любой переменной наследственна вверх).Когда шкала задана, можно определить истинность любой формулы (в данном мире) индукцией по построению формулы. Мы пишем w A, если в мире w истинна формула A. Вот индуктивноеопределение:• w A ∧ B, если w A и w B;• w A ∨ B, если w A или w B;• w A → B, если в любом мире u > w, в котором истиннаформула A, истинна также и формула B;• w ¬A, если ни в каком мире u > w формула A не являетсяистинной.Формула, не являющаяся истинной (в данном мире), называетсяложной (в нём).Определение истинности для отрицания, как мы видим, согласовано с пониманием ¬A как A → ⊥, где ⊥ — тождественно ложная(во всех мирах) формула.Именно определение импликации (и отрицания) использует порядок на множестве миров.
Если формула содержит лишь конъюнкциии дизъюнкции, то её истинность по существу определяется отдельнов каждом мире.Индукцией по построению формулы A легко проверить, что еслиона истинна в каком-то мире, то истинна и во всех бо́льших мирах. В самом деле, пересечение и объединение двух наследственныхвверх множеств также обладает этим свойством, так что для случая конъюнкции и дизъюнкции можно сослаться на предположениеиндукции.
А для импликации даже и этого не нужно, достаточнопосмотреть на определение.[п. 4]Интуиционистская пропозициональная логика65Философский смысл шкал Крипке иногда объясняют так. Будемсчитать, что W есть множество возможных состояний цивилизации(миров); неравенство w 6 u означает, что мир u может получитьсяиз мира w в результате развития цивилизации. Утверждение w Aозначает, что в мире w установлено, что высказывание A истинно.(При этом оно останется истинным и при дальнейшем развитии цивилизации.) Истинность ¬A в мире w означает, что ни при какомразвитии цивилизации из состояния w высказывание A не станетистинным.Определение истинности отрицания в шкалах Крипке предвосхитил Пушкин, когда писал «нет правды на земле.
Но правды нет ивыше . . .» (Моцарт и Сальери).34. Во что превращается определение истинности в шкале Крипке, еслив ней только один мир? если в ней никакие два мира не сравнимы?Теорема 25 (корректность интуиционистского исчисления высказываний относительно шкал Крипке). Формула, выводимая в интуиционистском исчислении высказываний, истинна во всех мирах всехшкал Крипке. Надо проверить, что все аксиомы истинны во всех мирах, атакже что правило modus ponens сохраняет это свойство.
Второеочевидно: если A → B истинна во всех мирах и A истинна во всехмирах, то по определению истинности импликации B будет истиннаво всех мирах.Осталось проверить истинность всех аксиом. Чтобы установить,что импликация ϕ → ψ истинна во всех мирах, надо проверить, что втех мирах, где истинна формула ϕ, истинна и формула ψ. Для первойаксиомы A → (B → A): если формула A истинна в некотором мире,то в силу монотонности она истинна и выше, так что B → A такжеистинна.Перейдём ко второй аксиоме (A → (B → C)) → ((A → B) →→ (A → C)). Пусть u A → (B → C). Мы должны доказать,что u (A → B) → (A → C).
Это означает, что если v > u иv A → B, то v A → C. Последнее, в свою очередь, значит, чтоесли w > v и w A, то w C. Но в силу монотонности мы знаем,что w A → (B → C) и w A → B. Поэтому из w A следуетw B, w (B → C), и, наконец, w C, что и требовалось.Остальные аксиомы проверяются ещё проще. Таким образом, чтобы доказать, что некоторая формула не выводима в интуиционистском исчислении высказываний, достаточнопредъявить шкалу Крипке, в одном из миров которой она ложна.66Исчисление высказываний[гл. 2]35. Покажите, что в этом случае есть шкала, в которой среди мировесть наименьший и в нём формула ложна.Для формулы p ∨ ¬p такая шкала строится легко. Возьмём двамира, первый меньше второго. Пусть p истинна только во второммире.
Тогда ¬p не будет истинна нигде, а p∨¬p будет истинна тольково втором мире.На самом деле это доказательство в сущности совпадает с приведённым выше (с трёхзначной логикой). В самом деле, в этой шкаледля формулы есть три возможности: она истинна в обоих мирах, онаистинна только во втором мире, или она не истинна ни в одном измиров. Эти три возможности соответствуют трём значениям И, Ни Л в рассмотренной нами трёхзначной интерпретации. Легко проверить, что таблицы операций как раз соответствуют определениюистинности в модели Крипке.Теперь мы можем установить, что все перечисленные выше формулы невыводимы в интуиционистском исчислении высказываний.Для формулы ¬¬p → p годится та же шкала (p истинно только вбольшем мире).
Она же годится для формулы (¬q → ¬p) → (p → q),если p истинно в обоих мирах, а q — только в большем. Для трёхоставшихся формул можно рассмотреть шкалы с тремя мирами: начальным миром u, из которого можно попасть в v > u и в w > u;миры v и w не сравнимы. Если формула p истинна только в миреv, то формула ¬p истинна только в мире w, a ¬¬p истинна только вмире v, так что в мире u обе формулы ¬p и ¬¬p ложны и дизъюнкция ¬p ∨ ¬¬p ложна. Чтобы построить контрмодель для формулы¬(p ∧ q) → ¬p ∨ ¬q, будем считать, что p истинна только в мире v,а q истинна только в мире w. Та же шкала годится и для формулы((p ∨ q) → p) ∨ ((p ∨ q) → q).Оказывается, что этот приём универсален, как показывает следующая теорема.Теорема 26 (полноты интуиционистского исчисления высказыванийотносительно шкал Крипке).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
