Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 10
Текст из файла (страница 10)
Докажите, что формула (A → (B → C)) → ((A ∧ B) → C), так жекак и обратная к ней формула (в которой посылка и заключение переставлены), являются теоремами исчисления высказываний. Докажите аналогичное утверждение про формулы (A ∧ B) → (B ∧ A) и ((A ∧ B) ∧ C) →→ (A ∧ (B ∧ C)).Аксиомы 6 – 7 позволяют утверждать, что A ` A ∨ B и B ` A ∨ B.Аксиома 8 обеспечивает такое правило:Γ, A ` CΓ, B ` CΓ, A ∨ B ` CОно соответствует такой схеме рассуждения: «Предположим, что A∨B.
Разберём два случая. Если выполнено A, то h . . . i и потому C.Если выполнено B, то h . . . i и потому C. В обоих случаях верно C.Значит, A ∨ B влечёт C.»Обоснование: дважды воспользуемся леммой о дедукции, получив Γ ` (A → C) и Γ ` (B → C), а затем дважды применимправило MP к этим формулам и аксиоме (A → C) → ((B → C) →→ ((A ∨ B) → C)). Получив формулу (A ∨ B) → C, опять применимправило MP к ней и формуле (A ∨ B).24. Докажите, что следующие формулы, а также обратные к ним (меняем местами посылку и заключение) являются теоремами исчисления[п.
1]Исчисление высказываний (ИВ)45высказываний:((A ∨ B) → C) → ((A → C) ∧ (B → C)),((A ∧ C) ∨ (B ∧ C)) → ((A ∨ B) ∧ C),((A ∨ C) ∧ (B ∨ C)) → ((A ∧ B) ∨ C).У нас остались ещё три аксиомы, касающиеся отрицания. Аксиома 9 гарантирует, что из противоречивого набора посылок можновывести что угодно: если Γ ` A и Γ ` ¬A, то Γ ` B для любогоB. Аксиома 10, напротив, объясняет, как можно вывести отрицаниенекоторой формулы A: надо допустить A и вывести два противоположных заключения B и ¬B.
Точнее говоря, имеет место такоеправило:Γ, A ` BΓ, A ` ¬BΓ ` ¬A(в самом деле, дважды применяем лемму о дедукции, а затем правило MP с аксиомой 10).Аксиомы 9 и 10 позволяют вывести некоторые логические законы, связанные с отрицанием.
Докажем, например, что (для любыхформул A и B) формула(A → B) → (¬B → ¬A)(«закон контрапозиции») является теоремой исчисления высказываний. В самом деле, по лемме о дедукции достаточно установить, что(A → B), ¬B ` ¬A.Для этого, в свою очередь, достаточно вывести из трёх посылок(A → B), ¬B, A какую-либо формулу и её отрицание (в данном случае формулы B и ¬B).25. Выведите формулы A → ¬¬A и ¬¬¬A → ¬A с помощью аналогичных рассуждений.Последняя аксиома, называемая «законом исключённого третьего», и иногда читаемая как «третьего не дано» (tertium non daturв латинском оригинале), вызвала в первой половине века большоеколичество споров.
(См. раздел 2.4 об интуиционистской логике, вкоторой этой аксиомы нет.)Из неё можно вывести закон «снятия двойного отрицания», формулу ¬¬A → A. Достаточно показать, что A ∨ ¬A, ¬¬A ` A. Поправилу разбора случаев, достаточно установить, что A, ¬¬A ` A46Исчисление высказываний[гл. 2](это очевидно) и что ¬A, ¬¬A ` A (а это верно, так как из двух противоречащих друг другу формул выводится что угодно с помощьюаксиомы 9).26.
Докажите, что формула (¬B → ¬A) → (A → B) является теоремойисчисления высказываний. (Указание: используйте закон исключённоготретьего.)27. Исключим из числа аксиом исчисления высказываний закон исключённого третьего, заменив его на закон снятия двойного отрицания.Покажите, что от этого класс выводимых формул не изменится.28.
Докажите, что при наличии аксиомы исключённого третьего (11)аксиома (10) является лишней — её (точнее следовало бы сказать: любойчастный случай этой схемы аксиом) можно вывести из остальных аксиом.Теперь уже можно доказать теорему о полноте: всякая тавтология выводима в исчислении высказываний. Идея доказательствасостоит в разборе случаев. Поясним её на примере.
Пусть A — произвольная формула, содержащая переменные p, q, r. Предположим,что A истинна, когда все три переменные истинны. Тогда, как мыдокажем, p, q, r ` A. Вообще каждой строке таблицы истинности дляформулы A соответствует утверждение о выводимости. Например,если A ложна, когда p и q ложны, а r истинно, то ¬p, ¬q, r ` ¬A.Если формула A является тавтологией, то окажется, что она выводима из всех восьми возможных вариантов посылок. Пользуясьзаконом исключённого третьего, можно постепенно избавляться отпосылок. Например, из p, q, r ` A и p, q, ¬r ` A можно получитьp, q, (r ∨ ¬r) ` A, то есть p, q ` A (поскольку (r ∨ ¬r) является аксиомой).Проведём это рассуждение подробно.
Начнём с такой леммы:Лемма 3. Для произвольных формул P и QP, Q ` (P ∧ Q);P, ¬Q ` ¬(P ∧ Q);¬P, Q ` ¬(P ∧ Q);¬P, ¬Q; ` ¬(P ∧ Q)P, Q ` (P → Q);P, ¬Q ` ¬(P → Q);¬P, Q ` (P → Q);¬P, ¬Q ` (P → Q);P, Q ` (P ∨ Q);P, ¬Q ` (P ∨ Q);¬P, Q ` (P ∨ Q);¬P, ¬Q ` ¬(P ∨ Q);P ` ¬(¬P );¬P ` ¬P.Эта лемма говорит, что если принять в качестве гипотез истин-[п. 1]Исчисление высказываний (ИВ)47ность или ложность формул P и Q, являющихся частями конъюнкции, дизъюнкции или импликации, то можно будет доказать илиопровергнуть всю формулу (в зависимости от того, истинна она илиложна). Последняя часть содержит аналогичное утверждение проотрицание.После предпринятой нами тренировки доказать эти утверждениянесложно. Например, убедимся, что ¬P ` ¬(P ∧Q). Для этого достаточно вывести два противоположных утверждения из ¬P, (P ∧ Q);ими будут утверждения P и ¬P .Проверим ещё одно утверждение: ¬P, ¬Q ` ¬(P ∨ Q).
Нам надо вывести два противоположных утверждения из ¬P, ¬Q, (P ∨ Q).Покажем, что из ¬P, ¬Q, (P ∨ Q) следует всё, что угодно. По правилу разбора случаев достаточно убедиться, что из ¬P, ¬Q, P и из¬P, ¬Q, Q следует всё, что угодно — но это мы знаем.Утверждения, касающиеся импликации, просты: в самом деле,мы знаем, что Q ` (P → Q) благодаря аксиоме 1, а ¬P ` (P → Q)благодаря аксиоме 9.Остальные утверждения леммы столь же просты.Теперь мы можем сформулировать утверждение о разборе случаев для произвольной формулы.Лемма 4.
Пусть A — произвольная формула, составленная из переменных p1 , . . . , pn . Тогда для каждой строки таблицы истинностиформулы A имеет место соответствующее утверждение о выводимости: если ε1 , . . . , εn , ε ∈ {0, 1}, и значение формулы A есть ε приp1 = ε1 , . . . , pn = εn , то¬ε1 p1 , .
. . , ¬εn pn ` ¬εA ,где ¬u ϕ обозначает ϕ при u = 1 и ¬ϕ при u = 0 (напомним, что 1обозначает истину, а 0 — ложь).Лемма очевидно доказывается индукцией по построению формулы A. Мы имеем посылки, утверждающие истинность или ложностьпеременных, и для всех подформул (начиная с переменных и идя ковсей формуле) выводим их или их отрицания с помощью леммы 3.Если формула A является тавтологией, то из всех 2n вариантовпосылок выводится именно она, а не её отрицание. Тогда правилоразбора случаев и закон исключённого третьего позволяют избавиться от посылок: сгруппируем их в пары, отличающиеся в позиции p1(в одном наборе посылок стоит p1 , в другом ¬p1 ), по правилу разбораслучаев заменим их на посылку (p1 ∨ ¬p1 ), которую можно выбросить (она является аксиомой).
Сделав так для всех пар, получим48Исчисление высказываний[гл. 2]2n−1 выводов, в посылках которых нет p1 ; повторим этот процесс спосылками p2 , ¬p2 и т. д. В конце концов мы убедимся, что формулаA выводима без посылок, как и утверждает теорема о полноте. 2.2. Второе доказательство теоремы о полнотеЭто доказательство, в отличие от предыдущего, обобщается наболее сложные случаи (исчисление предикатов, интуиционистскоеисчисление высказываний).Начнём с такого определения: множество формул Γ называется совместным, если существует набор значений переменных, прикоторых все формулы из Γ истинны.
Заметим, что формула ϕ является тавтологией тогда и только тогда, когда множество, состоящееиз единственной формулы ¬ϕ, не является совместным. Для случаяодной формулы есть специальный термин: формула τ выполнима,если существуют значения переменных, при которых она истинна,то есть если множество {τ } совместно. Тавтологии — это формулы,отрицания которых не выполнимы.Множество формул Γ называется противоречивым, если из негоодновременно выводятся формулы A и ¬A. Мы знаем, что в этомслучае из него выводятся вообще все формулы. (В противном случаеΓ называется непротиворечивым.)Теорема 19 (корректность исчисления высказываний, вторая форма). Всякое совместное множество формул непротиворечиво.
В самом деле, пусть совместное множество Γ противоречиво.Так как оно совместно, существуют значения переменных, при которых все формулы из Γ истинны. С другой стороны, из Γ выводитсянекоторая формула B и её отрицание. Может ли так быть?Оказывается, что нет. Мы уже видели, что всякая выводимаяформула истинна при всех значениях переменных (является тавтологией).
Справедливо и несколько более общее утверждение: еслиΓ ` A и при некоторых значениях переменных все формулы из Γистинны, то и формула A истинна при этих значениях переменных.(Как и раньше, это легко доказывается индукцией по построениювывода A из Γ.)В нашей ситуации это приводит к тому, что на выполняющемнаборе значений переменных для Γ должны быть истинны обе формулы B и ¬B, что, разумеется, невозможно. Мы называем это утверждение другой формой теоремы о корректности исчисления высказываний, поскольку из него формально[п.
2]Второе доказательство теоремы о полноте49можно вывести, что всякая теорема является тавтологией: если A —теорема, то множество {¬A} противоречиво (из него выводятся A и¬A), потому несовместно, значит, ¬A всегда ложна, поэтому A всегдаистинна.Теорема 20 (полнота исчисления высказываний, вторая форма).Всякое непротиворечивое множество совместно. Нам дано непротиворечивое множество Γ, а надо найти такие значения переменных, при которых все формулы из Γ истинны.(Вообще говоря, множество Γ может быть бесконечно и содержатьбесконечное число разных переменных.)Пусть есть какая-то переменная p, встречающаяся в формулахиз семейства Γ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
