Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 9
Текст из файла (страница 9)
А. Субботовская. Идея доказательства такова: если заменить случайно выбранную переменную в формуле с конъюнкциями и дизъюнкциями на случайно выбранное значение 0 или 1, то формулаупростится (не только эта переменная пропадёт, но с некоторой вероятностью пропадут и другие). Если делать так многократно, то отформулы останется небольшая часть — с другой стороны, эта частьвсё равно должна реализовывать сложение оставшихся аргументовпо модулю 2.18. Докажите, что функция большинства может быть вычислена нетолько схемой, но и формулой полиномиального размера, содержащейтолько связки И и ИЛИ.19. Докажите, что fsize1 (h) и fsize2 (h) для одной булевой функции hи двух полных базисов полиномиально связаны: существует полином P(зависящий от выбора базисов), для которого fsize2 (h) 6 P (fsize1 (h)) привсех h.
(Указание: использовать теорему 16.)2. Исчисление высказыванийНапомним, что тавтологии — это пропозициональные формулы, истинные при всех значениях переменных. Оказывается, что всетавтологии можно получить из некоторого набора «аксиом» с помощью «правил вывода», которые имеют чисто синтаксический характер и никак не апеллируют к смыслу формулы, её истинностии т. д. Эту задачу решает так называемое исчисление высказываний.В этой главе мы перечислим аксиомы и правила вывода этого исчисления, и приведём несколько доказательств теоремы о полноте(которая утверждает, что всякая тавтология выводима в исчислениивысказываний).2.1. Исчисление высказываний (ИВ)Каковы бы ни были формулы A, B, C, следующие формулы называют аксиомами исчисления высказываний:(1) A → (B → A);(2) (A → (B → C)) → ((A → B) → (A → C));(3) (A ∧ B) → A;(4) (A ∧ B) → B;(5) A → (B → (A ∧ B));(6) A → (A ∨ B);(7) B → (A ∨ B);(8) (A → C) → ((B → C) → (A ∨ B → C));(9) ¬A → (A → B);(10) (A → B) → ((A → ¬B) → ¬A);(11) A ∨ ¬A.Как говорят, мы имеем здесь одиннадцать «схем аксиом»; из каждой схемы можно получить различные конкретные аксиомы, заменяя входящие в неё буквы на пропозициональные формулы.Единственным правилом вывода исчисления высказываний является правило со средневековым названием «modus ponens» (MP).Это правило разрешает получить (вывести) из формул A и (A → B)формулу B.Выводом в исчислении высказываний называется конечная последовательность формул, каждая из которых есть аксиома или получается из предыдущих по правилу modus ponens.Вот пример вывода (в нём первая формула является частнымслучаем схемы (1), вторая — схемы (2), а последняя получается из[п.
1]Исчисление высказываний (ИВ)41двух предыдущих по правилу modus ponens):(p → (q → p)),(p → (q → p)) → ((p → q) → (p → p)),((p → q) → (p → p)).Пропозициональная формула A называется выводимой в исчислении высказываний, или теоремой исчисления высказываний, еслисуществует вывод, в котором последняя формула равна A. Такой вывод называют выводом формулы A.
(В принципе можно было бы ине требовать, чтобы формула A была последней — все дальнейшиеформулы можно просто вычеркнуть.)Как мы уже говорили, в исчислении высказываний выводятся всетавтологии и только они. Обычно это утверждение разбивают на двечасти: простую и сложную. Начнём с простой:Теорема 17 (о корректности ИВ). Всякая теорема исчисления высказываний есть тавтология. Несложно проверить, что все аксиомы — тавтологии. Для примера проделаем это для самой длинной аксиомы (точнее, схемы аксиом) — для второй. В каком случае формула(A → (B → C)) → ((A → B) → (A → C))(где A, B, C — некоторые формулы) могла бы быть ложной? Дляэтого посылка A → (B → C) должна быть истинной, а заключение(A → B) → (A → C) — ложным.
Чтобы заключение было ложным,формула A → B должна быть истинной, а формула A → C — ложной. Последнее означает, что A истинна, а C ложна. Таким образом,мы знаем, что A, (A → B) и (A → (B → C)) истинны. Отсюда следует, что B и (B → C) истинны, и потому C истинна — противоречие.Значит, наша формула не бывает ложной.Корректность правила MP также ясна: если формулы (A → B) иA всегда истинны, то по определению импликации формула B такжевсегда истинна. Таким образом, все формулы, входящие в выводы(все теоремы) являются тавтологиями. Гораздо сложнее доказать обратное утверждение.Теорема 18 (о полноте ИВ).
Всякая тавтология есть теорема исчисления высказываний. Мы предложим несколько альтернативных доказательств этойтеоремы. Но прежде всего мы должны приобрести некоторый опытпостроения выводов и использования аксиом.42Исчисление высказываний[гл. 2]Лемма 1. Какова бы ни была формула D, формула (D → D) является теоремой.Докажем лемму, предъявив вывод формулы (D → D) в исчислении высказываний.1. (D → ((D → D) → D)) → ((D → (D → D)) → (D → D))[аксиома 2 при A = D, B = (D → D), C = D];2.
D → ((D → D) → D) [аксиома 1];3. (D → (D → D)) → (D → D) [из 1 и 2 по правилу MP];4. D → (D → D) [аксиома 1];5. (D → D) [из 3 и 4 по правилу MP].Как видно, вывод даже такой простой тавтологии, как (D → D),требует некоторой изобретательности. Мы облегчим себе жизнь, доказав некоторое общее утверждение о выводимости.Часто мы рассуждаем так: предполагаем, что выполнено какое-тоутверждение A, и выводим различные следствия. После того какдругое утверждение B доказано, мы вспоминаем, что использовали предположение A, и заключаем, что мы доказали утверждениеA → B.
Следующая лемма, называемая иногда «леммой о дедукции», показывает, что этот подход правомерен и для исчисления высказываний.Пусть Γ — некоторое множество формул. Выводом из Γ называется конечная последовательность формул, каждая из которых является аксиомой, принадлежит Γ или получается из предыдущих поправилу MP.
(Другими словами, мы как бы добавляем формулы изΓ к аксиомам исчисления высказываний — именно как формулы, ане как схемы аксиом.) Формула A выводима из Γ, если существуетвывод из Γ, в котором она является последней формулой. В этомслучае мы пишем Γ ` A. Если Γ пусто, то речь идёт о выводимостив исчислении высказываний, и вместо ∅ ` A пишут просто ` A.Лемма 2 (о дедукции). Γ ` A → B тогда и только тогда, когдаΓ ∪ {A} ` B.В одну сторону утверждение почти очевидно: пусть Γ ` (A → B).Тогда и Γ, A ` (A → B).
(Для краткости мы опускаем фигурныескобки и заменяем знак объединения запятой.) Согласно определению, Γ, A ` A, откуда по MP получаем Γ, A ` B.Пусть теперь Γ, A ` B. Нам надо построить вывод формулы A →B из Γ. Возьмём вывод C1 , C2 , . . . , Cn формулы B = Cn из Γ, A.Припишем ко всем формулам этого вывода слева посылку A:(A → C1 ), (A → C2 ), . .
. , (A → Cn ).[п. 1]Исчисление высказываний (ИВ)43Эта последовательность оканчивается на (A → B). Сама по себеона не будет выводом из Γ, но из неё можно получить такой вывод, добавив недостающие формулы, и тем самым доказать лемму одедукции.Будем добавлять эти формулы, двигаясь слева направо. Пустьмы подошли к формуле (A → Ci ). По предположению формула Ciлибо совпадает с A, либо принадлежит Γ, либо является аксиомой,либо получается из двух предыдущих по правилу MP.
Рассмотримвсе эти случаи по очереди.(1) Если Ci есть A, то очередная формула имеет вид (A → A). Полемме 1 она выводима, так что перед ней мы добавляем её вывод.(2) Пусть Ci принадлежит Γ. Тогда мы вставляем формулы Ci иCi → (A → Ci ) (аксиома 1). Применение правила MP к этим формулам даёт (A → Ci ), что и требовалось.(3) Те же формулы можно добавить, если Ci является аксиомойисчисления высказываний.(4) Пусть, наконец, формула Ci получается из двух предыдущихформул по правилу MP. Это значит, что в исходном выводе ей предшествовали формулы Cj и (Cj → Ci ). Тогда в новой последовательности (с добавленной посылкой A) уже были формулы (A → Cj )и (A → (Cj → Ci )).
Поэтому мы можем продолжить наш Γ-вывод,написав формулы((A → (Cj → Ci )) → ((A → Cj ) → (A → Ci )) (аксиома 2);((A → Cj ) → (A → Ci )) (modus ponens);(A → Ci ) (modus ponens).Итак, во всех четырёх случаях мы научились дополнять последовательность до вывода из Γ, так что лемма о дедукции доказана.20. Докажите, что для любых формул A, B, C формула(A → B) → ((B → C) → (A → C))выводима в исчислении высказываний. (Указание: используйте лемму одедукции и тот факт, что A → B, B → C, A ` C.)21. Докажите, что если `1 ` A и `2 , A ` B, то `1 ∪ `2 ` B.
(Это свойство иногда называют «правилом сечения» (cut); говорят, что формулаA «отсекается» или «высекается». Сходные правила играют центральнуюроль в теории доказательств, где формулируется и доказывается «теоремаоб устранении сечения» для различных логических систем.)22. Добавим к исчислению высказываний, помимо правила MP, ещёодно правило, называемое правилом подстановки. Оно разрешает заменить в выведенной формуле все переменные на произвольные формулы44Исчисление высказываний[гл. 2](естественно, вхождения одной переменной должны заменяться на одну иту же формулу).
Покажите, что после добавления такого правила классвыводимых формул не изменится, но лемма о дедукции перестанет бытьверной.Заметим, что мы пока что использовали только две первые аксиомы исчисления высказываний. Видно, кстати, что они специальноподобраны так, чтобы прошло доказательство леммы о дедукции.Другие аксиомы описывают свойства логических связок. Аксиомы 3 и 4 говорят, какие следствия можно вывести из конъюнкции(A ∧ B ` A и A ∧ B ` B). Напротив, аксиома 5 говорит, как можно вывести конъюнкцию. Из неё легко следует такое правило: еслиΓ ` A и Γ ` B, то Γ ` (A ∧ B) (применяем эту аксиому и дваждыправило MP). Часто подобные правила записывают так:Γ`AΓ`BΓ`A∧B(над чертой пишут «посылки» правила, а снизу — его «заключение»,вытекающее из посылок).23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
