«КУРС МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ ВЫЧИСЛИМОСТИ УЧЕБНОЕ ПОСОБИЕ Издание третье, исправленное и дополненное Электронный вариант этой книги (в виде PDF-файла) распространяется с сайта Московского центра непрерывного ...»

А. С. ГЕРАСИМОВ

КУРС

МАТЕМАТИЧЕСКОЙ ЛОГИКИ

И ТЕОРИИ ВЫЧИСЛИМОСТИ

УЧЕБНОЕ ПОСОБИЕ

Издание третье, исправленное и дополненное

Электронный вариант этой книги (в виде PDF-файла)

распространяется с сайта Московского центра непрерывного

математического образования http://www.mccme.ru/free-books и

с сайта её автора http://gas-teach.narod.ru.

Издательство ЛЕМА Санкт-Петербург 2011 УДК 510.6+510.2+510.5+512.54.05+004.05 ББК 22.12 Г37 Герасимов А. С. Курс математической логики и теории вычислимости: Учебное пособие. 3-е изд., испр. и доп. СПб.: Издательство ЛЕМА, 2011. 284 с.

ISBN 978-5-98709-292- Настоящее учебное пособие предназначено для изучения математической логики и теории алгоритмов. В нём описаны языки логики высказываний и логики предикатов первого порядка, семантика этих языков. На основе общего понятия исчисления изложены исчисления гильбертовского типа, секвенциальные исчисления и метод резолюций как способы формального математического доказательства. Рассмотрены основные формальные аксиоматические теории элементарная арифметика и теория множеств Цермело-Френкеля. Теория алгоритмов представлена теорией вычислимости, в рамках которой дано несколько точных определений понятия алгоритма и доказана неразрешимость некоторых проблем.

Дополнительная глава посвящена исчислению для формального доказательства правильности программ некоторого императивного языка программирования. В данной книге имеется более 190 упражнений.

Это учебное пособие адресовано в первую очередь студентам, специализирующимся по информатике, но будет полезно студентам разных математических специальностей (направлений подготовки), а также всем желающим начать систематическое изучение математической логики.

Александр Сергеевич Герасимов Курс математической логики и теории вычислимости Подписано в печать 12.01.2011.

Формат 60 84/16. Бумага офсетная.

Тираж 25 экз. Усл. п. л. 16,7.

Заказ N 1865.

Отпечатано в ООО Издательство ”ЛЕМА” 199004, Россия, Санкт-Петербург, В. О., Средний пр., д. 24, тел./факс: 323-67- email: [email protected] c А. С. Герасимов, 2009, 2010, ISBN 978-5-98709-292- Оглавление Предисловие Начальные соглашения об обозначениях Глава 1. Исчисления высказываний 1.1. Пропозициональные формулы и булевы функции....... 1.1.1. Формальные языки..................... 1.1.2. Язык логики высказываний................ 1.1.3. Семантика языка логики высказываний. Логические законы............................ 1.1.4. Выражение булевой функции формулой. Дизъюнктивная и конъюнктивная нормальные формы. Полиномы Жегалкина.......................... 1.2. Общее понятие исчисления..................... 1.2.1. Исчисление и вывод в исчислении............ 1.2.2. Вывод из гипотез...................... 1.3. Исчисление высказываний гильбертовского типа........ 1.3.1. Формулировка исчисления................. 1.3.2. Корректность исчисления................. 1.3.3. Теорема о дедукции. Допустимые правила....... 1.3.4. Полнота исчисления.................... 1.3.5. Поиск вывода и алгоритм Британского музея...... 1.4. Секвенциальное исчисление высказываний........... 1.4.1. Поиск контрпримера для пропозициональной формулы 1.4.2. Формулировка исчисления................. 1.4.3. Корректность и полнота исчисления........... 1.4.4. Допустимые правила.................... 1.5. Метод резолюций для логики высказываний.......... Глава 2. Исчисления предикатов 2.1.1. Формулы языка первого порядка............. 2.1.2. Вхождения предметных переменных в формулы.... 2.2. Семантика языка первого порядка................ 2.2.1. Интерпретация языка первого порядка......... 2.2.2. Примеры языков первого порядка и их интерпретаций 2.2.3. Формула, выражающая предикат............. 2.3. Свободные и правильные подстановки.............. 4 Герасимов А. С. Курс математической логики и теории вычислимости 2.6.2. Вывод из гипотез. Корректность исчисления. Теорема 2.7.4. Соотношение с исчислением предикатов гильбертовского типа.......................... 4.2.4. Алгоритм проверки невыполнимости множества дизъюнктов............................ 4.4.1. Определение резолютивного вывода и корректность Оглавление 4.5. Основы логического программирования............. 4.5.1. Логическая программа и её декларативная семантика. 4.5.3. Операционная семантика логической программы.... 5.1.3. Лямбда-исчисление и лямбда-определимые функции. 5.2.1. Разрешимые и перечислимые множества натуральных 5.2.4. Разрешимые и перечислимые языки и словарные отношения........................... 5.3.2. Универсальные машины Тьюринга и универсальные 5.4.2. Проблемы самоприменимости, остановки и всюду 5.4.3. Доказательство неразрешимости проблем методом сведения............................. 5.5.2. Проблема общезначимости и проблема выводимости Глава 6. Исчисление Хоара для доказательства корректности 6.3. Аксиоматическая семантика программы............. 6 Герасимов А. С. Курс математической логики и теории вычислимости Приложение А. Свойства секвенциального исчисления предикатов и формальные аксиоматические теории на его основе А.1. Некоторые свойства секвенциального исчисления предикатов А.1.1. Допустимость правил добавления............. А.1.3. Допустимость правил, формализующих некоторые обычные способы математических рассуждений.... А.2. Формальные аксиоматические теории на основе секвенциального исчисления предикатов.................... А.2.3. Примеры содержательного и формального доказательств в теории....................... Предисловие Настоящее учебное пособие предназначено для изучения математической логики и смежной с ней области теории вычислимости. Эта книга адресована в первую очередь студентам, специализирующимся по информатике, но будет полезна студентам разных математических специальностей (направлений подготовки), а также всем желающим начать систематическое изучение указанных областей математики. Традиционные названия дисциплин, для изучения которых можно использовать это учебное пособие, Математическая логика, Математическая логика и теория алгоритмов. Теория вычислимости, также называемая общей теорией алгоритмов, является одним из основных разделов теории алгоритмов (наряду с более молодым разделом теорией сложности вычислений).

Математическая логика наука о принятых в математике способах рассуждений. Эта наука определяет, что считается доказательством в математике, тем самым формируя основания математики. Даваемые математической логикой определения доказательства настолько точны, что могут быть использованы для проверки и поиска доказательств с помощью компьютера. Это позволяет широко применять математическую логику в информатике, например, разрабатывать экспертные системы программы, моделирующие рассуждения эксперта в какой-либо области знаний.

Информатика является наукой, близкой к математике, и занимается, в частности, точным описанием (формализацией) знаний, причём такое описание должно быть настолько точно, чтобы его понимал компьютер. Данная книга учит формальным языкам и представлению знаний с их помощью, формальным доказательствам и их алгоритмизации; таким образом, эта книга учит осуществлять формализацию знаний. Также читатель познакомится с теоретическими основами одной из парадигм декларативного программирования логическим программированием; знание этих основ поможет эффективно использовать языки логического программирования, например, язык Prolog.

Теория вычислимости произошла из математической логики в результате попыток осуществить желание математиков иметь алгоритм доказательства математических утверждений, записанных на формальном логическом языке. В посвящённой теории вычислимости главе этой книги читатель познакомится с точными определениями алгоритма; каждое из них по сути задаёт язык программирования. Это знакомство крайне полезно для развития программистского опыта, поскольку некоторые из точных определений алгоритма легли в основу современных парадигм программирования, например, императивной и функциональной парадигм. Также в теории вычислимости раскрыты неустранимые ограничения алгоритмичеГерасимов А. С. Курс математической логики и теории вычислимости ского решения задач: доказано, что для решения некоторых важных задач не существует никакого алгоритма.

В последней главе книги рассматривается основополагающий метод формального доказательства правильности программ. Изучение этого метода не только развивает умение убеждаться в правильности программ (или находить в них ошибки) путём рассуждений, но и подготавливает читателя к использованию и разработке технологий программирования, предполагающих проверку правильности программ посредством доказательства.

Итак, данная книга создана с целью существенно способствовать качественной подготовке математиков, исследователей в области информатики, программистов, умеющих осуществлять формализацию знаний.

С более детальным содержанием этого учебного пособия можно ознакомиться в оглавлении и в аннотациях, с которых начинается каждая глава и приложение. Характерной особенностью изложения является определение общего понятия исчисления как, грубо говоря, некоторого механического способа получения заключений из ранее установленных или принятых в качестве аксиом утверждений. Это обеспечивает единый подход к различным способам формализации математических доказательств. В данной книге изучаются исчисления пяти принципиально различных видов: исчисления гильбертовского типа, секвенциальные и резолютивные исчисления, лямбда-исчисление и исчисление Хара.

Излагаемый материал представляет собой лишь введение в соответствующие разделы математической логики и теории вычислимости. Однако автор уверен, что освоивший эту книгу читатель при желании будет готов к изучению более специальной литературы по математической логике, теории алгоритмов и их применениям в информатике.

Для изучения данной книги требуется знание начальных понятий наивной теории множеств (таких, как отношение, функция, отношение эквивалентности, классы эквивалентности по отношению эквивалентности, счётность множества), знание метода математической индукции, знание понятий полинома, полугруппы, группы, дерева, а также желательно знакомство с каким-нибудь языком программирования (например, с языком Pascal). Все эти знания студенты обычно получают из курсов алгебры, математического анализа и информатики в течение первого семестра обучения на математических факультетах университетов.

Автор благодарен С. П. Герасимову за поддержку и А. И. Герасимовой за поддержку и нахождение множества опечаток в первом издании этого учебного пособия.

Также автор выражает благодарность студентам математико-механического факультета СПбГУ, которым он преподавал и которые указали опечатки в первом издании данной книги.

Начальные соглашения об обозначениях Знаком отмечается конец доказательства (а также определения, примера, замечания и упражнения), начинающегося соответствующим заголовком.

Принадлежность элемента x множеству X записывается как x X. Если неверно, что x X, то пишем x X. Пустое множество обозначаем.

{x1,..., xn } есть множество, элементами которого являются в точности x1,..., xn. Сходным образом можно записывать множество {x1,..., xn,...}, когда указан или общепринят способ получения элементов, подразумеваемых под последним многоточием. {x X | (x)} есть множество всех элементов x множества X, для которых верно утверждение (x).

Объединение, пересечение и разность множеств X и Y обозначаются X Y, X Y и X \ Y соответственно. iI Xi есть объединение всех множеств Xi, где i I. X Y означает, что множество X является подмножеством множества Y.

Под f : X Y понимается, что f является функцией (отображением) из множества X в множество Y. Область определения и область значений функции f обозначаются через dom(f ) и rng(f ) соответственно.

Множество X1... Xn (где n 1) является декартовым произведением множеств X1,..., Xn, т. е. множеством всех упорядоченных n-ок x1,..., xn элементов x1 X1,..., xn Xn. Множество X n есть n-ая декартова степень множества X, иначе говоря, X n есть X1... Xn при X = X1 =... = Xn, т. е. множество всех упорядоченных n-ок элементов множества X.

N обозначает множество всех натуральных чисел {0, 1, 2,...}. Множество всех отличных от нуля натуральных чисел {1, 2,...} мы обозначаем через N+. Знак заменяет слово влечёт, а слова тогда и только тогда, когда.

Остальные обозначения общеупотребительны (как, впрочем, и некоторые из вышеприведённых обозначений) или вводятся в тексте по мере необходимости. Подробный список обозначений является частью предметного указателя.

10 Герасимов А. С. Курс математической логики и теории вычислимости Греческий алфафит Приведём греческий алфавит с названиями букв. (Далее в этом учебном пособии мы будем использовать только те буквы греческого алфавита, которые по начертанию отличны от букв латинского алфавита.) Нестандартные варианты написания букв латинского алфавита Укажем (более или менее) нестандартные варианты написания некоторых букв латинского алфавита, используемые в этой книге.

Глава 1.

Исчисления высказываний Под высказыванием мы понимаем повествовательное предложение, которое является либо истинным, либо ложным, но не тем и другим сразу. Логика высказываний, или пропозициональная логика, изучает способы математических рассуждений о высказываниях. Высказывания могут быть простыми (неделимыми) или составными. Примеры простых высказываний: 4 чётное число, 5 нечётное число, идёт дождь, я прогуливаюсь. Примеры составных высказываний: 4 чётное число и нечётное число, если идёт дождь, то я не прогуливаюсь. В этих примерах курсивом выделены слова, связывающие высказывания для образования составных высказываний. Из последнего составного высказывания и высказывания идёт дождь можно заключить, что я не прогуливаюсь ;

причём это рассуждение считается правильным. Из того же составного высказывания и высказывания я прогуливаюсь, можно вывести не идёт дождь ; и это рассуждение мы считаем правильным. А какие ещё рассуждения (о высказываниях) считать правильными, можно ли их как-нибудь точно описать? Основной целью данной главы является ответ на этот вопрос.

1.1. Пропозициональные формулы и булевы Для изучения способов рассуждений о произвольных высказываниях мы введём обозначения для высказываний и для слов, связывающих высказывания, задав тем самым некоторый формальный язык. Кроме таких обозначений, существенной особенностью этого формального языка, отличающей его от естественного (например, русского) языка, будет однозначность его понимания. Мы укажем, как можно определить, является ли записанное на этом формальном языке высказывание истинным или ложным, и рассмотрим некоторые свойства таких высказываний.

1.1.1. Формальные языки Мы запланировали ввести некоторый формальный язык для записи высказываний. Однако сначала будет полезно определить общее понятие 12 Герасимов А. С. Курс математической логики и теории вычислимости формального языка и сопутствующие понятия.

Под символом, или буквой, понимается знак, который рассматривается как единое целое. Понятие символа является исходным и не определяется, а лишь поясняется. Предполагается, что про любые два символа можно с уверенностью сказать ровно одно из двух: одинаковы они или различны.

Тот факт, что два символа, обозначаемые через a1 и a2, одинаковы, мы будем записывать как a1 = a2.

Алфавитом называется произвольное непустое конечное множество символов.

Словом в алфавите называется конечная цепочка (в том числе цепочка, не содержащая ни одного символа) записанных подряд символов этого алфавита, а число символов (не обязательно различных) в этой цепочке называется длиной этого слова. Цепочка, не содержащая ни одного символа, называется пустым словом.

Пусть a1,..., am, b1,..., bn (не обязательно различные) символы некоторого алфавита, перечисленные через запятую. Будем говорить, что два слова a1... am и b1... bn равны (совпадают или одинаковы) и писать a1... am = b1... bn, если m = n и ai = bi для каждого i = 1,..., m. В противном случае будем говорить, что эти слова неравны (не совпадают или различны).

Конкатенацией слов и называется слово, получающееся приписыванием слова к слову. Говорят, что слово начинается со слова, и слово называют началом слова.

Говорят, что слово входит в слово ( является подсловом слова ), если найдутся такие слова и, что =. При этом, если длина слова равна k, то будем говорить, что имеется k-вхождение слова в слово. Для любого n N n-вхождение слова в слово будем называть вхождением слова в слово. Вхождения (если они есть) слова в слово естественным образом упорядочены (k-вхождение предшествует m-вхождению, если k < m), поэтому можно говорить о первом, втором и т. д. вхождении в.

Пусть имеется k-вхождение слова в слово, т. е. существуют такие слова и, что = и длина слова равна k. Тогда результатом замены этого вхождения слова в слово на слово (результатом подстановки слова вместо этого вхождения слова в слово ) назовём слово.

Пример 1.1.1. Пусть рассматривается алфавит {A, a, B, b, C, c,..., Z, z}. Слово mathematics имеет длину 11. Имеется ровно 2 вхождения слова ma в слово mathematics: 0-вхождение и 5-вхождение. Результатом замены 5-вхождения слова ma в слово mathematics на F GH является слово matheF GHtics.

Пустое слово имеет длину 0 и входит ровно 1 раз в пустое слово, причём это единственное вхождение является 0-вхождением.

Имеется ровно 2 вхождения слова aba в слово ababa: 0-вхождение и 2-вхождение.

Множество всех слов в алфавите обозначается через. (Отметим, что пустое слово принадлежит.) 1 Для экономии места мы не перечисляем все элементы этого множества, полагая, что это множество состоит в точности из всех заглавных и всех строчных английских букв.

Глава 1. Исчисления высказываний Формальным языком (или просто языком) в алфавите называется какое угодно подмножество множества.

Пример 1.1.2. Пусть алфавитом LettersAndDigits является множество символов {A, a, B, b, C, c,..., Z, z, 0, 1, 2,..., 9}. Определим язык Identiers в этом алфавите как множество всех слов в алфавите LettersAndDigits, которые начинаются с любого символа, принадлежащего множеству {A, a, B, b, C, c,..., Z, z}. Слова Clause33, dvgjf 683Xitr принадлежат языку Identiers, а пустое слово и слово 73abc нет.

Предпочтительнее задать язык Identiers с помощью следующего индуктивного определения:

1) любой символ из {A, a, B, b, C, c,..., Z, z} является словом языка Identiers;

LettersAndDigits, то (т. е. конкатенация и ) является словом языка Identiers.

Мы отдаём предпочтение этому индуктивному определению, поскольку оно описывает процесс построения (или конструирования) слов из символов по заданным правилам.

Итак, мы ввели общее понятие (формального) языка. Теперь определим язык для записи высказываний.

1.1.2. Язык логики высказываний Определение 1.1.3. Обозначим через V ars язык {V |V, V ||V, V |||V,...} в алфавите {V, |}. Каждое слово языка V ars будем называть пропозициональной переменной (или, короче, переменной). Пропозициональная формула (формула логики высказываний или просто формула) задаётся следующим индуктивным определением:

1) любая пропозициональная переменная является пропозициональной формулой;

2) символы F и T являются пропозициональными формулами и называются истинностными константами (ложь и истина соответственно);

3) если A и B пропозициональные формулы, то ¬A, (A B), (A B) и (A B) пропозициональные формулы.

Множество всех пропозициональных формул обозначим через P L и назовём языком логики высказываний (или пропозициональным языком). Таким образом, алфавит языка P L есть множество символов {V, |, F, T, (, ), ¬,,, }.

Пример 1.1.4. Разделённые запятыми слова 2P L является сокращением словосочетания Propositional Language.

14 Герасимов А. С. Курс математической логики и теории вычислимости являются пропозициональными формулами. Ни одно из слов не является пропозициональной формулой.

Замечание 1.1.5. Поясним, почему мы выбрали в качестве пропозициональных переменных несколько неестественные слова, например, V |V и V ||V, вместо немного более естественных слов V | и V ||. Но тогда, если бы мы заменили все вхождения V | в (V | V ||) на A, то получили бы (A A|). Нам же, как правило, будет удобно без дополнительных оговорок заменять все вхождения V |V в (V |V V ||V ) на A и получать в результате (A V ||V ).

Поэтому пропозициональные переменные мы выбрали так, что ни одна из них не входит ни в какую отличную от неё переменную.

В дальнейшем изложении для удобства записи мы будем обозначать произвольную пропозициональную переменную словом из букв латинского алфавита, которое начинается с одной из букв p, q, r, причём такое слово может иметь индекс, являющийся натуральным числом. Например, обозначениями пропозициональных переменных являются следующие слова:

p, p1, pf, pf2, q0, r, r2007. С такими обозначениями переменных мы будем считать формулами, например, следующие слова: p3, ¬p, ((p q) p). Условимся, что в данной главе в каждой записи формулы различны переменные, имеющие различные обозначения, если явно не оговорено другое. Также условимся, что в данной главе буквы A, B, C, D, E и G (возможно, с индексами) будут обозначать произвольные пропозициональные формулы, если иное не оговорено явно.

Символы ¬ (отрицание), (конъюнкция), (дизъюнкция) и (импликация) называются логическими связками (иногда просто связками).

Будем говорить, что отрицание является унарной связкой, а остальные из этих связок являются бинарными связками. (Связка названа унарной или бинарной по числу формул, которые она связывает в одну формулу.) Укажем, как обычно логические связки представляются словами русского языка в речи математиков:

3) (A B) дизъюнкция A и B (здесь союз и означает перечисление, а не конъюнкцию), A или B ;

4) (A B) импликация с посылкой A и заключением B, если A, A следует B, B является следствием A, B имеет место при A, B имеет место в случае A, A только (лишь) при B, A только (лишь) в случае B, A достаточно для B, B необходимо для A, Индуктивный характер определения пропозициональной формулы позволяет использовать следующий метод доказательства того, что любая формула C обладает свойством P. Для этого достаточно доказать 1) базу индукции: любая переменная и любая истинностная константа обладает свойством P; и Глава 1. Исчисления высказываний 2) индукционный переход: из предположения (называемого индукционным предположением) того, что формулы A и B обладают свойством P, следует, что ¬A, (A B), (A B) и (A B) обладают свойством P.

Этот метод доказательства называют индукцией по построению формулы C, а также индукцией по построению множества формул P L.

Докажем, например, что в любой формуле C число вхождений левых скобок ( равно числу вхождений правых скобок ).

Д о к а з а т е л ь с т в о. Обозначим утверждение в формуле C число вхождений левых скобок равно числу вхождений правых скобок через P[C]. Доказательство того, что для любой формулы C верно P[C], проведём индукцией по построению формулы C.

База индукции. Для любой формулы C, являющегося пропозициональной переменной или истинностной константой, выполняется P[C], поскольку в C имеется 0 вхождений левых и 0 вхождений правых скобок.

Индукционный переход. Предположим, что для формулы A верно P[A], и для формулы B верно P[B]. Тогда P[¬A] выполняется, поскольку при построении ¬A из A ни одно вхождение скобки не добавляется, и P[A] верно по индукционному предположению. P[(A B)] выполняется потому, что при построении (A B) из A и B добавляется ровно одно вхождение левой скобки и ровно одно вхождение правой скобки, а P[A] и P[B] верны по индукционному предположению. Аналогично верны P[(AB)] и P[(A B)].

Упражнение 1.1.6. Докажите, что в любой пропозициональной формуле число вхождений бинарных логических связок не превосходит числа вхождений переменных.

Индуктивный характер определения пропозициональной формулы также позволяет задавать функции, определённые на множестве формул P L, индукцией (или рекурсией) по построению множества формул P L, а именно, следующим образом:

1) пусть каждой переменной p сопоставлен объект F[p], и каждой истинностной константе Q сопоставлен объект F[Q];

2) пусть задано правило такое, что если формулам A и B сопоставлены объекты F[A] и F[B], то однозначно находится каждый из объектов F[¬A], F[(A B)], F[(A B)] и F[(A B)].

Тогда для любой формулы A определён объект F[A].

Упражнение 1.1.7. Для каждой формулы A определим её логическую сложность l[A] следующим образом (а именно, индукцией по построению множества формул P L): 1) l[A] = 0, если A переменная или истинностная константа; 2) l[¬A] = l[A] + 1, l[(A B)] = l[A] + l[B] + 1, где A, B формулы, одна из связок,,. Докажите, что l[A] равно числу вхождений логических связок в формулу A.

Определим бинарную логическую связку (эквивалентность), являющуюся вспомогательной. Пусть A и B формулы. Тогда (A B) служит сокращённой записью формулы ((A B) (B A)). Формуле (A B) обычно соответствуют следующие выражения русского языка: A, если и 16 Герасимов А. С. Курс математической логики и теории вычислимости только если B, A тогда и только тогда, когда B, A равносильно B, A эквивалентно B, для A необходимо и достаточно B.

Введём нередко используемое сокращение: заменяет слова по определению есть (или слова, обозначаемое через, ), где ранее определённое понятие, а определяется данным сокращением. Ниже мы будем нередко пользоваться таким сокращением, а также понимать под записью, что сначала вводится обозначение, а затем С использованием только что введённого сокращения определение логической связки можно переписать так: (A B) ((A B) (B A)).

Наконец, дадим ещё одно определение, используемое в дальнейшем, и договоримся о сокращении числа скобок в записи формул.

Формула, входящая в формулу A, называется подформулой формулы A.

Для более экономной и иногда более наглядной записи формул примем соглашения об опускании некоторых скобок.

Во-первых, можно опускать пару внешних скобок в записи отдельно стоящей формулы. Например, формулу (p ¬q) можно записать в виде p ¬q.

Во-вторых, будем считать, что каждая бинарная логическая связка левоассоциативна. Это означает, что в произвольной формуле любую подформулу вида ((A B) C) можно записать в виде (A B C), где все выделенные вхождения являются вхождениями какой угодно фиксированной бинарной связки. Например, формулу p ((q (r ¬p)) r) можно записать как p (q (r ¬p) r).

В-третьих, будем считать, что приоритет связок в последовательности,,, строго убывает. Подробнее, пусть и обозначают такие связки, что приоритет выше, чем приоритет (т. е. стоит в указанной последовательности левее ). Тогда любую подформулу вида ((A B) C) можно записать как (A B C), а также любую подформулу вида (A (B C)) можно записать как (A B C). Например, формулу ((p q) r) p можно записать как (p q r) p, а формулу Пример 1.1.8. Формула ((((p ¬q) r) ¬(p q))) может быть записана в виде p ¬q r ¬(p q), причём в этой записи уже нельзя опустить пару скобок.

Отметим, что ¬p p является, а p q не является подформулой формулы ¬p p q, поскольку последняя формула подробнее записывается как (¬p p) q.

¬p является, а ¬(p q) не является подформулой формулы ¬p q r, поскольку последняя может быть подробнее записана как (¬p q) r.

Вхождение логической связки ¬ относится к минимальной по длине подформуле, стоящей сразу за рассматриваемым вхождением ¬.

Упражнение 1.1.9. Разработайте алгоритм восстановления опущенных скобок в любой заданной сокращённой записи формулы.

Глава 1. Исчисления высказываний 1.1.3. Семантика языка логики высказываний. Логические законы До сих пор пропозициональные формулы были для нас лишь специальным образом построенными цепочками символов, лишёнными какого-либо содержательного значения (смысла). В данном разделе мы придадим пропозициональным формулам некоторое содержательное значение, иначе говоря, зададим семантику языка P L логики высказываний, а также изучим некоторые семантические свойства этого языка.

Рассмотрим следующее высказывание математика: У меня с собой зонт, если я не знаю прогноз погоды, или я знаю прогноз погоды, и прогнозируются дожди. Нам понятен его смысл: если мы знаем, истинно или нет каждое простое высказывание в составе этого составного высказывания, то мы сможем определить, говорит ли этот математик правду (истину). Для удобства введём обозначения: pu у меня (этого математика) с собой зонт, pf я знаю прогноз погоды, pr прогнозируются дожди, всё исходное высказывание обозначим через A.

Если мы знаем, что pf, pr и pu все истинны, то мы считаем, что математик говорит правду, т. е. высказывание A истинно. Если же мы знаем, что pf и pr истинны, а pu ложно, то мы считаем, что математик говорит ложь, т. е. высказывание A ложно.

Из предыдущего раздела мы знаем, какие логические связки соответствуют словам если, не, или, и, поэтому мы можем записать A в виде формулы (¬pf (pf pr)) pu, где pf, pr и pu играют роль пропозициональных переменных. Расстановка скобок в этой формуле соответствует интуитивному смыслу высказывания A, в частности, pf и pr связаны союзом и сильнее, чем ¬pf и pf союзом или. Рассуждения, приведённые выше, интуитивно показывают, что можно определить, истинна ли формула A, если известно, истинна ли каждая входящая в A переменная. Такой подход мы и примним по отношению к любой пропозициональной формуе ле.

Если высказывание истинно, то также говорят, что это высказывание имеет истинностное значение 1 (истина). Если высказывание ложно, то также говорят, что это высказывание имеет истинностное значение (ложь). Множество {0, 1} всех истинностных (или булевских) значений обозначим через B.

Для того, чтобы любая пропозициональная формула получила истинностное значение, прежде всего каждой пропозициональной переменной сопоставим истинностное значение с помощью так называемой интерпретации.

Определение 1.1.10. Интерпретацией (или моделью) языка P L называется какое угодно отображение M : V ars B, которое каждой переменной p сопоставляет истинностное значение M (p).

Далее, предположим, что формулы A и B получили истинностные значения и соответственно. Зададим, как по истинностным значениям и вычисляются истинностные значения формул ¬A, (A B), (A B) и (A B). Для этого определим одноместную функцию F¬ из множества B в B и двухместные функции F, F, F из множества B2 в B с помощью таблиц, изображённых на рис. 1.1. Эти функции (таблицы) назовём функцией 18 Герасимов А. С. Курс математической логики и теории вычислимости (таблицей) истинности отрицания, конъюнкции, дизъюнкции и импликации соответственно. Теперь положим, что истинностные значения формул Рис. 1.1. Таблицы, определяющие функции F¬, F, F и F.

соответственно.

Замечание 1.1.11. В соответствии с определением функции F, импликация A B ложна, если и только если одновременно формула A истинна и формула B ложна; в остальных случаях эта импликация истинна: если A истинна и B истинна, а также, если A ложна (B может быть как истинна, так и ложна). Возможно, вызывает сомнение то, что при ложной посылке A мы посчитали импликацию истинной вне зависимости от истинностного значения заключения B.

Чтобы развеять это сомнение, для любого натурального числа k рассмотрим такое высказывание: Если k больше 5, то k больше 2. Для каждого k эту импликацию мы, конечно, хотим считать истинной. При k = посылка этой импликации ложна и заключение ложно; при k = 3 посылка ложна и заключение истинно; поэтому мы признаём, что при ложной посылке импликацию целесообразно считать истинной. Таким образом, определение функции F согласуется с нашим интуитивным пониманием импликации.

Теперь мы готовы дать определение истинностного значения любой формулы в произвольной интерпретации.

Определение 1.1.12. Пусть задана какая угодно интерпретация M языка P L. Для любой формулы A определим истинностное значение формулы A в интерпретации M. Это значение мы будем обозначать через |A|M (или иногда через |A|, если из контекста понятно, какая интерпретация рассматривается). Зададим |A|M с помощью следующего индуктивного определения3 :

1) если A является переменной, то |A|M = M (A);

2) если A является истинностной константой F, то |A|M = 0;

3) если A является истинностной константой T, то |A|M = 1;

4) если A имеет вид ¬B, то |A|M = F¬ (|B|M );

5) если A имеет вид (B C), то |A|M = F (|B|M, |C|M );

6) если A имеет вид (B C), то |A|M = F (|B|M, |C|M );

3 Это определение является определением индукцией по построению множества формул P L (см. раздел 1.1.2). В дальнейшем мы не будем явно отмечать такие факты.

Глава 1. Исчисления высказываний 7) если A имеет вид (B C), то |A|M = F (|B|M, |C|M ).

Если |A|M = 1, то будем говорить, что формула A истинна в (при) интерпретации M, и сокращённо записывать этот факт как M A.

Если |A|M = 0, то будем говорить, что формула A ложна в (при) интерпретации M, и сокращённо записывать этот факт как M A.

Очевидно, что истинностное значение формулы определяется лишь значениями переменных, входящих в неё, и не зависит от значений переменных, не входящих в эту формулу.

Пример 1.1.13. Пусть A ((p q) p).

Зададим интерпретацию M1. Положим M1 (p) = 0, M1 (q) = 1. Отличным от p и q переменным можно сопоставить любые истинностные значения, положим для определённости M1 (r) = 1 для любой переменной r V ars \ {p, q}. Тогда имеем |A| = F (|p q|, |p|) = F (F (|p|, |q|), |p|) = таким образом, M1 A.

Если же задать интерпретацию M2 так, что M2 (r) = 1 для любой переменной r, то M2 (p q) и M2 p, поэтому M2 A.

Среди пропозициональных формул выделяют формулы, которые являются истинными при любых значениях входящих в них переменных. Такие формулы представляют в формальном виде принятые в математике способы рассуждений, иначе говоря, логические законы. Например, формула p (p q) является логическим законом, поскольку, имея какие угодно высказывания, обозначенные через p и q, мы наверняка считаем, что если истинно p, то истинно хотя бы одно из двух: p или q. Эти соображения приводят нас к следующему определению.

Определение 1.1.14. Формула, истинная в любой интерпретации, называется общезначимой формулой (тождественно истинной формулой, тавтологией или логическим законом). То, что формула A общезначима, обозначается через A.

Формула, не являющаяся общезначимой, называется необщезначимой.

То, что формула A необщезначима, обозначается через A.

Формула, ложная в любой интерпретации, называется невыполнимой (противоречивой или тождественно ложной).

Формула, не являющаяся противоречивой, называется выполнимой (или непротиворечивой).

Пример 1.1.15. Формула p (p q) является общезначимой, выполнимой.

Формула ¬(p (p q)) является невыполнимой, необщезначимой. Формула p q является выполнимой, необщезначимой.

Выясним, как проверять, является ли произвольная формула A общезначимой. Если в A не входит никакая переменная, то A имеет одно и то же истинностное значение в любой интерпретации, которое легко вычислить согласно определению 1.1.12. Иначе в A входит лишь конечное число n попарно различных переменных, каждая из которых получает одно из двух 20 Герасимов А. С. Курс математической логики и теории вычислимости истинностных значений при задании интерпретации. Следовательно, имеется лишь конечное число (именно, 2n ) различных наборов значений этих переменных. Поэтому проверить, является ли данная формула общезначимой или нет, можно путём нахождения истинностного значения этой формулы для каждого такого набора значений переменных. Такую проверку удобно представлять в виде таблицы, общий вид которой мы сейчас зададим.

Пусть p1,..., pn попарно различные переменные, n > 0, A какая угодно пропозициональная формула, в которую могут входить переменные только из списка p1,..., pn (в частности, в A может не входить никакая переменная). Таблица истинности формулы A имеет вид, соответствующий таблице 1.1. Кроме верхней (заголовочной) строки, эта таблица имеет 2n строк, в которых записаны все различные последовательности 1,..., n истинностных значений и истинностные значения формулы A в какой угодно интерпретации M такой, что M (p1 ) = 1,..., M (pn ) = n. (Очевидно, = |A|M не зависит от выбора такой интерпретации M, поскольку истинностное значение формулы не зависит от значений переменных, не входящих в эту формулу.) Таблица 1.1. Общий вид таблицы истинности формулы.

Пример 1.1.16. Таблица истинности формулы p q есть таблица 1.2.

Пример 1.1.17. Составим таблицу истинности (см. таблицу 1.3) формулы ¬(p q) (¬p ¬q) и увидим, что в последнем столбце стоят только 1, таким образом, эта формула общезначима. Обязательными столбцами в этой таблице являются те, в которых указаны значения переменных (первый и второй столбцы) и значение исходной формулы (последний столбец), а остальные столбцы вспомогательные и могут быть опущены.

Приведём список некоторых логических законов с их традиционными названиями.

Законы коммутативности и ассоциативности конъюнкции:

Глава 1. Исчисления высказываний Таблица 1.3. Таблица истинности формулы ¬(p q) (¬p ¬q).

Законы коммутативности и ассоциативности дизъюнкции:

Законы дистрибутивности:

Законы поглощения:

Законы Де Моргана:

10) ¬(p q) (¬p ¬q).

Закон исключённого третьего:

11) p ¬p.

Закон двойного отрицания:

12) p ¬¬p.

Закон контрапозиции:

13) (p q) (¬q ¬p).

Отрицание посылки:

14) ¬p (p q).

Выражение импликации через отрицание и дизъюнкцию:

Упражнение 1.1.18. Проверьте общезначимость формул 1–15, приведённых выше.

22 Герасимов А. С. Курс математической логики и теории вычислимости Продолжаем изучение семантических свойств языка логики высказываний. Рассмотрим, например, формулы G1 qиA (p q). Легp, G ко видеть, что в любой интерпретации, если истинны G1 и G2, то истинна и A. Про такие формулы говорят, что A является логическим следствием множества формул {G1, G2 }. Перейдём к определению, которое уточняет и обобщает это наблюдение.

Определение 1.1.19. Формула A называется логическим следствием (или семантическим следствием) множества формул (это обозначается как A), если для всякой интерпретации M выполняется: если для любой формулы G верно M G, то M A.

Если неверно, что A, то пишем A.

Если множество формул пусто, то A в точности означает, что Если состоит из конечного числа формул G1,..., Gn и A, то этот факт будем также записывать как G1,..., Gn A и говорить, что формула A является логическим (семантическим) следствием формул G1,..., Gn.

Для такого факт A будем также записывать как G1,..., Gn A p, p q q. Но p p q (рассмотрите интерпретацию, в которой переменная p истинна, а q ложна).

Теорема 1.1.21 (о логическом следствии). Пусть G1,..., Gn (n N+ ), A пропозициональные формулы. Тогда G1,..., Gn A, если и только если G1... Gn A.

Д о к а з а т е л ь с т в о. G1... Gn A по определению общезначимой формулы означает, что (a) для любой интерпретации M выполняется M (G1... Gn ) A. В соответствии с таблицей истинности импликации утверждение (a) равносильно следующему утверждению (b):

для всякой интерпретации M, если M G1... Gn, то M A. Согласно таблице истинности конъюнкции, утверждение (b) равносильно следующему: для любой интерпретации M, если для любой формулы G {G1,..., Gn } M G, то M A, т. е. (по определению логического следствия) G1,..., Gn A.

Рассмотрим теперь формулы A ¬(p q) и B (¬p ¬q). Таблицы истинности этих формул (являющиеся подтаблицами таблицы 1.3 на с. 21) показывают, что A и B истинны или ложны при одних и тех же значениях переменных. Про такие формулы говорят, что они равносильны. Уточним это наблюдение, дав следующее определение.

Определение 1.1.22. Формулы A и B называются равносильными (логически эквивалентными или семантически эквивалентными), если для всякой интерпретации M выполняется: M A тогда и только тогда, когда M B (утверждение, стоящее после двоеточия, можно записать иначе как |A|M = |B|M ). То, что формулы A и B равносильны, будем обозначать через A B.

Очевидно, что формулы A и B равносильны, если и только если формула (A B) является общезначимой. Ещё один критерий равносильности Глава 1. Исчисления высказываний формул A и B равносильны, если и только если A B и B A по сути является переформулировкой только что данного определения. Также очевидно, что A A (т. е. отношение рефлексивно); из A B следует B A (т. е. симметрично); и из A B и B C следует A C (т. е. транзитивно); таким образом, отношение является отношением эквивалентности на множестве всех пропозициональных формул.

Примеры равносильных формул мы получим, если заменим на в каждом из вышеприведённых логических законов 1–15, в который входит.

Имея некоторые общезначимые формулы, мы можем получать новые общезначимые формулы следующим образом. Рассмотрим, например, общезначимую формулу p (p q). Подставим вместо всех вхождений p какую угодно формулу, скажем, (¬q r). В результате получим формулу (¬q r) ((¬q r) q). Легко проверить, что она общезначима. Можно предположить, что общезначимость будет сохраняться для любой исходной формулы, лишь бы все вхождения некоторой переменной заменялись на одну и ту же (хотя и выбранную произвольно) формулу. Сформулируем это предположение в обобщённом виде и докажем его. Но прежде уточним понятие подстановки формул вместо вхождений пропозициональных переменных.

Пусть p1,..., pn попарно различные пропозициональные переменные;

A, B1,..., Bn пропозициональные формулы; обозначает множество слов {B1 /p1,..., Bn /pn } (таким образом, каждый элемент этого множества есть слово, состоящее из формулы, символа-разделителя / и переменной). Положим по определению, что через A обозначается результат одновременной замены всех вхождений переменных p1,..., pn в A на B1,..., Bn соответственно.

Дадим также индуктивное определение A:

2) если A есть истинностная константа или переменная, отличная от Замечание 1.1.23. С помощью индукции по построению формулы A можно доказать, что два данных определения A равносильны. (Отметим и другой возможный подход: можно было оставить лишь индуктивное определение, а слова A результат одновременной замены всех вхождений переменных p1,..., pn в A на B1,..., Bn соответственно считать пояснением.) Следующее объяснение адресовано прежде всего читателям, изучающим информатику и сомневающимся в целесообразности индуктивных определений, нередко громоздких. Данное индуктивное определение A не следует считать бесполезным из-за того, что неиндуктивное определение того же понятия было дано раньше. Как мы увидим, индуктивное определение позволит легко доказывать некоторые свойства с помощью индукции.

Кроме того, предположим, что требуется разработать компьютерную программу, реализующую подстановку A, причём изначально такая подстановка определена неиндуктивно. Также предположим, что формула предГерасимов А. С. Курс математической логики и теории вычислимости ставляется в программе не просто в виде строки, а в виде так называемого синтаксического дерева формулы.

Пусть A формула. Синтаксическим деревом формулы A называют дерево, корень которого помечен (или является) 1) самой формулой A, если A есть переменная или истинностная константа;

2) логической связкой ¬, если A имеет вид ¬C, причём в этом случае поддеревом этого узла является синтаксическое дерево формулы C;

3) логической связкой, если A имеет вид C D ( одна из связок,, ), причём в этом случае левым и правым поддеревьями этого узла являются синтаксические деревья формул C и D соответственно.

Например, синтаксическое дерево формулы ¬p (p q) выглядит так:

При представлении формулы в программе в виде синтаксического дерева одним из естественных подходов для разработчика программы будет уточнение того, как вычисляется A, в духе данного нами индуктивного определения. Это индуктивное определение по сути является рекурсивным алгоритмом вычисления A.

В дальнейшем мы обычно будем опускать очевидные индуктивные определения и давать более короткие неиндуктивные, будучи уверенными, что читатель при необходимости сможет записать соответствующие индуктивные определения.

Пример 1.1.24. Пусть A (p (pqr)). Тогда A{(¬qr)/p, ¬r1 /q, ¬q/r2 } есть (¬q r) ((¬q r) ¬r1 r).

Теорема 1.1.25 (о подстановке пропозициональных формул в пропозициональную тавтологию). Пусть p1,..., pn попарно различные пропозициональные переменные, A, B1,..., Bn пропозициональные формулы, {B1 /p1,..., Bn /pn }. Тогда если A, то A.

Д о к а з а т е л ь с т в о. Пусть M произвольная интерпретация языка P L. Определим интерпретацию M так, что M (pi ) = |Bi |M для каждого i = 1,..., n и M (q) = M (q) для любой переменной q V ars \ {p1,..., pn }.

Если мы докажем, что для любой формулы E верно |E|M = |E|M, то, взяв в качестве E общезначимую формулу A, получим |A|M = |A|M = 1.

Поскольку M произвольная интерпретация, то A, что и утверждает данная теорема.

Таким образом, для завершения доказательства данной теоремы осталось установить, что для любой формулы E верно |E|M = |E|M. Применим индукцию по построению формулы E.

База индукции. E является пропозициональной переменной или истинностной константой. Если E есть pi для некоторого i = 1,..., n, то Глава 1. Исчисления высказываний Если же E есть переменная из V ars \ {p1,..., pn } или истинностная константа, то |E|M = |E|M = |E|M.

Индукционный переход. Предположим, что для формул C и D устанавливаемое утверждение верно.

Пусть E имеет вид ¬C. Тогда |E|M = |¬C |M, где C C. По индукционному предположению |C|M = |C|M. Следовательно, Наконец, пусть E имеет вид (C D), где одна из связок,,. Тогда |E|M = |C D|M. По индукционному предположению |C|M = |C|M и |D|M = |D|M. Следовательно, Следствие 1.1.26. Пусть p1,..., pn попарно различные пропозициональные переменные, A, B1,..., Bn, C пропозициональные формулы, Д о к а з а т е л ь с т в о. Пусть верно A C. Тогда имеет место (A C), отсюда по предыдущей теореме 1.1.25 получаем (A C). (A C) есть (A C), значит, (A C) влечёт A C, что и требовалось доказать.

Мы бы хотели производить равносильные преобразования формул примерно так же, как и известные преобразования алгебраических выражений.

Например, поскольку ¬(p q) (¬p ¬q), то кажется естественным, что должно быть верно Здесь подчёркнутое вхождение подформулы слева от знака заменено на подчёркнутую формулу справа от этого знака. Следующая теорема обосновывает семантическую эквивалентность исходной формулы и формулы, полученной в результате такой замены.

Теорема 1.1.27 (о семантически эквивалентной замене). Пусть A, B и B пропозициональные формулы, A есть результат замены некоторого вхождения B в A на B. Тогда если B B, то A A.

Пример 1.1.28. Проиллюстрируем эту теорему:

Упражнение 1.1.29. Докажите предыдущую теорему, воспользовавшись индукцией по построению формулы A.

26 Герасимов А. С. Курс математической логики и теории вычислимости 1.1.4. Выражение булевой функции формулой. Дизъюнктивная и конъюнктивная нормальные формы.

Полиномы Жегалкина Для какого угодно n N+ любая функция из множества Bn в множество B называется n-местной булевой функцией.

Любая пропозициональная формула A, в которую входят переменные только из списка попарно различных переменных p1,..., pn, естественным образом определяет булеву функцию f (p1,..., pn ), значения которой вычисляются по формуле A. Подробнее, для любых 1,..., n B f (1,..., n ) = |A|M, где M любая интерпретация такая, что M (p1 ) = 1,..., M (pn ) = n (очевидно, что f (1,..., n ) не зависит от выбора такой интерпретации M ). С другой стороны, если даны формула A и булева функция f (p1,..., pn ), удовлетворяющие указанным условиям, то мы будем говорить, что формула A выражает функцию f (p1,..., pn ).

Пример 1.1.30. Формула ¬p1 выражает как функцию F¬ (p1 ), так и функцию f (p1, p2 ) = F¬ (p1 ). Формула p1 ¬p2 выражает функцию g(p1, p2 ) = F (p1, F¬ (p2 )).

Теорема 1.1.31. Для любой булевой функции f (p1,..., pn ) найдётся пропозициональная формула A, которая выражает f.

Д о к а з а т е л ь с т в о. Для простоты изложения возьмём функцию f, заданную таблицей 1.4. Аналогичное доказательство будет справедливо для любой булевой функции.

Таблица 1.4. Таблица, задающая булеву функцию f.

Запишем пропозициональную формулу A, истинную при тех и только тех значениях переменных, при которых истинна функция f. Для этого сначала для каждой строки таблицы со значением 1 функции f запишем формулу, истинную при тех и только тех значениях переменных, которые стоят в рассматриваемой строке. Для первой строки4 таблицы 1.4 записываем формулу (¬p1 ¬p2 ), а для последней строки формулу (p1 p2 ).

Искомая формула A получается соединением полученных формул с помощью дизъюнкции: (¬p1 ¬p2 ) (p1 p2 ).

Этот способ выражения f формулой годится, если f не является тождественно ложной; иначе f можно выразить, например, формулой (p1 ¬p1 ).

Излагаемый ниже второй способ выражения f формулой применм, и если f не является тождественно истинной; иначе f можно выразить, например, формулой (p1 ¬p1 ).

Запишем пропозициональную формулу A, ложную при тех и только тех значениях переменных, при которых ложна функция f. Для этого сначала 4 Заголовочную строку мы считаем нулевой.

Глава 1. Исчисления высказываний для каждой строки таблицы со значением 0 функции f запишем формулу, ложную при тех и только тех значениях переменных, которые стоят в рассматриваемой строке. Для второй строки таблицы 1.4 записываем формулу (p1 ¬p2 ), а для третьей строки формулу (¬p1 p2 ). Искомая формула A получается соединением полученных формул с помощью конъюнкции:

(p1 ¬p2 ) (¬p1 p2 ).

Формулы, построенные в только что проведённом доказательстве, имеют некий специальный вид, к определению которого мы сейчас перейдём.

Определение 1.1.32. Пусть A1,..., An (n 1) формулы. Формула A1... An называется дизъюнкцией формул A1,..., An. Формула A1... An называется конъюнкцией формул A1,..., An. Каждая формула Ai (i = 1,..., n) называется членом этой дизъюнкции (соответственно, конъюнкции).

Литерой называется любая пропозициональная переменная и отрицание любой пропозициональной переменной.

Определение 1.1.33. Конъюнктом называется конъюнкция литер. Говорят, что формула находится в дизъюнктивной нормальной форме, если она является дизъюнкцией конъюнктов. Также такая формула называется дизъюнктивной нормальной формой (сокращённо ДНФ).

Пример 1.1.34. Следующие формулы находятся в ДНФ: p, ¬p, ¬p q, p ¬q, (p ¬q) (¬p r p) ¬q, причём все скобки в последней формуле можно опустить.

Определение 1.1.35. Дизъюнктом называется дизъюнкция литер. Говорят, что формула находится в конъюнктивной нормальной форме, если она является конъюнкцией дизъюнктов. Также такая формула называется конъюнктивной нормальной формой (сокращённо КНФ).

Пример 1.1.36. Следующие формулы находятся в КНФ: p, ¬p, ¬p q, Будем говорить, что формула B выражает формулу A, если A B.

Определение 1.1.37. Дизъюнктивной (соответственно, конъюнктивной) нормальной формой формулы A называется любая формула, находящаяся в ДНФ (соответственно, КНФ) и выражающая формулу A.

Пример 1.1.38. Легко проверить, что таблица 1.4 из доказательства теоремы 1.1.31 является таблицей истинности формулы A (p1 p2 ). Построенные в доказательстве этой теоремы формулы (¬p1 ¬p2 ) (p1 p2 ) и (p1 ¬p2 ) (¬p1 p2 ) являются, соответственно, ДНФ и КНФ формулы A.

Вышеприведённые определения и доказательство теоремы 1.1.31 дают нам следующую теорему.

Теорема 1.1.39. Любую булеву функцию (и любую пропозициональную формулу) можно выразить как формулой, находящейся в ДНФ, так и формулой, находящейся в КНФ.

28 Герасимов А. С. Курс математической логики и теории вычислимости Упражнение 1.1.40. Докажите, что КНФ общезначима, если и только если в каждом её дизъюнкте имеется переменная и отрицание этой переменной. Сформулируйте и докажите похожее утверждение о невыполнимости ДНФ.

Упражнение 1.1.41. Уточните следующий способ выражения булевой функции формулой, находящейся в КНФ, и обоснуйте его: сначала построить ДНФ отрицания этой функции, а затем построить отрицание полученной ДНФ.

Упражнение 1.1.42. Опишите два алгоритма, один из которых любую формулу выражает формулой, находящейся в КНФ, а другой в ДНФ. Эти алгоритмы должны опираться на равносильные преобразования формул.

Введём бинарные логические связки штрих Шеффера | и стрелку Пирса : положим (A | B) ¬(A B) и (A B) ¬(A B).

Теорема 1.1.43. Любую булеву функцию можно выразить пропозициональной формулой, в которую из логических связок входят только:

(a) ¬ и, (b) ¬ и, (c) |, (d).

Д о к а з а т е л ь с т в о. По теореме 1.1.39 любую булеву функцию можно выразить формулой C, в которую из связок входят только ¬, и.

(a) Докажем, что C можно выразить можно выразить формулой, в которую из связок входят только ¬ и. Воспользуемся индукцией (точнее, методом математической индукции5 ) по числу вхождений связки в C.

База индукции. Имеется ровно 0 вхождений связки в C. Доказываемое утверждение верно.

Индукционный переход. Предположим, что для любой формулы C с числом вхождений связки, равным n, доказываемое утверждение верно.

Рассмотрим формулу C с ровно n + 1 вхождением связки. Легко проверить, что (p q) ¬(¬p ¬q); отсюда по следствию 1.1.26 теоремы о подстановке имеем (A B) ¬(¬A ¬B) для любых формул A и B. Заменим в формуле C одно из вхождений формулы вида (A B) на ¬(¬A ¬B).

Обозначим получившуюся в результате этой замены формулу через C. По теореме 1.1.27 о семантически эквивалентной замене справедливо C C. В формуле C имеется ровно n вхождений связки. Применив к C индукционное предположение, получим формулу C, которая из связок имеет лишь ¬ и, причём C C. Воспользовавшись транзитивностью отношения, получим C C. Таким образом, C искомая формула, и пункт (a) доказан.

Очевидно, для любых формул A и B имеем следующее:

(b) (A B) ¬(¬A ¬B);

5 Пусть k N. Напомним, что для доказательства методом математической индукции того, что утверждение P(n) верно при любом натуральном n k, устанавливают 1) базу индукции: P(k); и 2) индукционный переход: для любого натурального n k из предположения (называемого индукционным предположением) верности P(n) следует верность P(n+1).

Глава 1. Исчисления высказываний Отсюда доказательства пунктов (b), (c) и (d) получаются таким же образом, как и доказательство пункта (a).

Замечание 1.1.44. Доказательство пункта (a) предыдущей теоремы было весьма подробным. В дальнейшем мы иногда будем приводить менее подробные доказательства, будучи уверенными, что читатель при необходимости сможет восстановить детали. Менее подробное доказательство пункта (a) могло бы быть таким: очевидно, (A B) ¬(¬A ¬B), поэтому, заменив в формуле C каждую подформулу вида (A B) на ¬(¬A ¬B), в результате получим формулу, равносильную формуле C и из связок имеющую только ¬ и.

Упражнение 1.1.45. Докажите, что любую булеву функцию можно выразить пропозициональной формулой, в которую из связок входят только ¬ Замечание 1.1.46. Теорема 1.1.39 установила, что любую булеву функцию можно выразить формулой, в которую из связок входят лишь ¬, и. Этот факт можно переформулировать так: любая булева функция есть некоторая композиция функций F¬, F и F. Например, если некоторая функция f (p1, p2 ) выражена формулой (¬p1 ¬p2 ) (p1 p2 ), то f (p1, p2 ) равна F (F (F¬ (p1 ), F¬ (p2 )), F (p1, p2 )).

Упражнение 1.1.47. Докажите, что, кроме функций F| (p1, p2 ) и F (p1, p2 ), которые выражаются формулами (p1 | p2 ) и (p1 p2 ) соответственно, не существует двухместной булевой функции F такой, что любая булева функция есть некоторая композиция функций, среди которых имеется только функция F. Указание. Сколько всего имеется двухместных булевых функций? Какие из этих функций F сохраняют 0 или 1 (т. е. F (, ) = при = 0 или при = 1 соответственно)? Можно ли выразить любую булеву функцию только с помощью функции, сохраняющей 0 или 1?

Полиномы Жегалкина Рассмотрим (известное из алгебры) поле вычетов по модулю 2, обозначаемое здесь через Z2. Напомним, что в Z2 лишь два элемента 0 и 1;

операции + и · над ними определены таким образом: 0 + 0 = 0, 0 + 1 = 1, Полиномом Жегалкина от переменных x1,..., xn называется любой полином над Z2 вида где суммирование идёт по всем подмножествам {i1,..., im } множества {1, 2,..., n}, каждое a{i1,...,im } Z2, причём член, соответствующий пустому подмножеству, является константой.

Для любого x Z2 и любого n N+ имеем xn = x (грубо говоря, степени выше первой не нужны). Поэтому любой полином P (x1,..., xn ) над Z функционально равен некоторому полиному Жегалкина P (x1,..., xn ), т. е.

Отождествим элементы 0 и 1 множества Z2 с истинностными значениями 0 и 1 соответственно. Докажем, что тогда любая булева функция 30 Герасимов А. С. Курс математической логики и теории вычислимости выражается некоторым полиномом Жегалкина, т. е. значения этой функции вычисляются как значения этого полинома.

Согласно замечанию 1.1.46 любая булева функция есть некоторая композиция функций F¬, F и F. Поэтому достаточно выразить полиномами Жегалкина эти три функции. Легко проверить, что Учитывая, что q1 q2 ¬(¬q1 ¬q2 ), имеем F (q1, q2 ) = F¬ (F (F¬ (q1 ), F¬ (q2 ))) = Итак, всякая булева функция может быть выражена некоторым полиномом Жегалкина.

Пример 1.1.48. Выразим полиномом Жегалкина булеву функцию, заданную таблицей 1.4 на с. 26. Следующая ДНФ выражает эту функцию:

Конъюнкт (p1 p2 ) выражается полиномом p1 · p2 (от переменных p1 и p2 );

конъюнкт (¬p1 ¬p2 ) полиномом (p1 + 1) · (p2 + 1) = p1 · p2 + p1 + p2 + 1.

Наконец, D выражается полиномом Упражнение 1.1.49. Докажите, что для любой булевой функции существует ровно один полином Жегалкина, выражащий эту функцию. Указание.

Одним из возможных подходов к доказательству является сравнение числа n-местных булевых функций и числа полиномов Жегалкина от n переменных.

В заключение данного раздела скажем несколько слов о применении теории булевых функций к построению цифровых схем, в том числе интегральных микросхем. Такие схемы состоят из функциональных элементов.

Функциональный элемент f имеет несколько входов и один выход. На каждый из входов элемента f подаётся цифровой сигнал (т. е., по сути, 0 или 1). То, какой сигнал получается на выходе элемента f, определяется тем, какую булеву функцию реализует элемент f. Например, если f реализует функцию F, то на выходе будет 0, когда на оба входа f подаётся 0, в остальных случаях на выходе будет 1. Схему образуют из функциональных элементов путём соединения входов одних элементов и выходов других. Так как любая булева функция есть некоторая композиция функций F¬, F и F (см. замечание 1.1.46), то любую булеву функцию можно реализовать схемой из функциональных элементов трёх типов: реализующих функции F¬, F и F соответственно. Естественно возникает задача: как минимизировать количество элементов в схеме. Однако эта задача выходит за рамки данной книги, а наша цель лишь показать, что теория булевых функций, основ которой мы лишь коснулись, находит важные применения.

Глава 1. Исчисления высказываний 1.2. Общее понятие исчисления Не всегда осознавая это, мы имеем дело с исчислением, когда заданы некоторые исходные объекты (аксиомы) и правила, по которым можно получать новые объекты из исходных и ранее полученных (правила вывода).

Пример 1.2.1. Примером исчисления, хорошо известного из базового курса математического анализа, является исчисление для нахождения производных функций (в символьном виде). Аксиомы этого исчисления суть равенства, задающие производные некоторых элементарных функций, например, константы, степенной, показательной и логарифмической функций. Правила вывода этого исчисления суть правила нахождения производной функции f, которая является суммой, произведением, частным, композицией функций f1 и f2, по уже найденным производным функций f1 и f2. Более конкретно, одна из аксиом может быть записана в общем виде как (x ) = x1. Одно из правил вывода можно записать в виде из (f1 ) = g1 и (f2 ) = g2 получается (f1 + f2 ) = g1 + g2 или в виде Тогда из аксиом (x5 ) = 5x4 и (x6 ) = 6x5 по этому правилу вывода получаем (x5 + x6 ) = 5x4 + 6x5. Далее, из последнего равенства и аксиомы (x7 ) = 7x по данному правилу вывода получаем (x5 + x6 + x7 ) = 5x4 + 6x5 + 7x6.

Это равенство, конечно, не оказывается неожиданным, но замечательно то, что при получении этого равенства мы пользовались лишь аксиомами и правилами вывода исчисления, причём делали это чисто механически и не вникали в содержательное значение (семантику) объектов, которыми оперировали.

Конкретизируем понятие исчисления применительно к формальным языкам (в этом случае получаемые объекты будут словами) и уточним, как получаются (иначе говоря, выводятся) новые объекты с помощью исчисления.

1.2.1. Исчисление и вывод в исчислении Пусть произвольный алфавит, L произвольный язык в алфавите. Говорят, что задано исчисление (или дедуктивная система) C, если задано множество Ax слов языка L и конечное множество R, каждый элемент которого является не менее чем двухместным отношением на L.

Каждый элемент множества Ax называют аксиомой исчисления C. Каждый элемент множества R называют правилом вывода исчисления C. Будем называть алфавитом исчисления C, L языком исчисления C, а также будем говорить, что C является исчислением в алфавите (исчислением в языке L). Если потребуется подчеркнуть, что рассматривается исчисление C в языке L, то вместо C будем использовать C(L).

Пусть R правило вывода, являющееся (n + 1)-местным отношением, где n N+. Если 1,..., n, R, то говорят, что получается (или получено) из 1,..., n по правилу вывода R, или что является результатом применения правила вывода R к 1,..., n. Каждое слово i (i = 1,..., n) 32 Герасимов А. С. Курс математической логики и теории вычислимости называют посылкой, а слово заключением данного (применения) правила. Правило вывода, являющееся (n + 1)-местным отношением, называют n-посылочным правилом вывода.

Часто n-посылочное правило вывода записывают в следующем виде:

где A1,..., An задают общий вид посылок, а A общий вид заключения.

При этом предполагается, что символ ; не входит в алфавит, а служит разделителем. Такая запись и сопутствующие комментарии определяют отношение, являющееся правилом вывода. (Обычно правило вывода таково, что можно построить алгоритм, проверяющий по произвольным словам 1,..., n,, получается ли из 1,..., n по этому правилу вывода или нет.) Выводом (или доказательством) в исчислении C называется конечная последовательность слов 1, 2,..., k, в которой каждое слово i (i = 1, 2,..., k) является аксиомой исчисления C или получается по некоторому правилу вывода исчисления C из некоторых слов i1,..., in этой последовательности таких, что каждое i1,..., in меньше i. (Конец предыдущего предложения, начинающийся со слова из, можно менее точно переформулировать так: из предшествующих слов этой последовательности ).

Число k называется длиной этого вывода. Предполагается, что символ,, служащий разделителем слов языка L в выводе, не входит в алфавит (иначе в качестве такого разделителя возьмём символ, не входящий в ).

Таким образом, вывод является словом в алфавите {, }.

Выводом слова в исчислении C называется вывод 1,..., k в этом исчислении, где k совпадает с.

Если существует вывод слова в исчислении C, то слово называют выводимым в исчислении C (или теоремой исчисления C) и обозначают это как C.

Если слово не является выводимым в исчислении C, то называют невыводимым в C и обозначают это как C.

Обозначения вида C и C часто сокращают до и соответственно, если из контекста понятно, какое исчисление рассматривается.

Зачастую полезно дополнять вывод его анализом: каждое слово в выводе снабжать номером и указанием на то, что оно является аксиомой, или на то, из каких слов и по какому правилу вывода получено данное слово. (Можно условиться дополнять вывод анализом другого вида, если это потребуется.) Пример 1.2.2. Пусть дан алфавит {a, b} и язык L палиндромом называется слово, которое одинаково читается слева направо и справа налево, и дадим определение, уточняющее понятие палиндрома применительно к алфавиту. Слово x1... xn (где xi для каждого i = 1,..., n) назовём палиндромом, если n > 0 и для каждого j = 1,..., n выполняется xj = xn+1j.

Зададим исчисление P al, в котором, как мы докажем, будут выводимы все палиндромы языка L и только они.

Аксиомами этого исчисления являются слова: 1) a, 2) b, 3) aa и 4) bb.

Глава 1. Исчисления высказываний Правила вывода исчисления P al таковы:

где произвольное слово языка L. Справа от каждого из этих правил приведено его обозначение. По правилу (a) (соответственно, по правилу (b)) из слова получается слово aa (соответственно, bb). Определение исчисления P al закончено.

Выводом слова abababa в исчислении P al является приведённая ниже последовательность слов, разделённых запятыми (точка служит для завершения текущего предложения и не входит в этот вывод):

Этот же вывод с анализом выглядит так:

2) aba получается из слова 1 по правилу (a);

3) babab получается из слова 2 по правилу (b);

4) abababa получается из слова 3 по правилу (a).

Докажем, что для любого слова языка L имеет место: тогда и только тогда, когда является палиндромом.

Д о к а з а т е л ь с т в о. Необходимость. Пусть, т. е. существует вывод слова в исчислении P al. Индукцией (точнее, методом возвратной индукции6 ) по длине вывода слова докажем, что является палиндромом.

База индукции. Длина вывода слова равна 1. Тогда является аксиомой. Любая аксиома, очевидно, является палиндромом.

Индукционный переход. Предположим, что любое слово, являющееся последним в выводе длины, меньшей n (n > 1), есть палиндром. Рассмотрим вывод длины n слова. Если является аксиомой, то, как мы уже установили, оно является палиндромом. Иначе получено из некоторого предшествующего слова этого вывода по правилу (a) или по правилу (b).

Тогда = aa или = bb. По индукционному предположению является палиндромом. Следовательно, является палиндромом.

Достаточность. Пусть палиндром. Индукцией по длине слова докажем, что.

База индукции. Длина равна 1 или 2. Тогда, поскольку палиндром, является одним из слов a, b, aa или bb. Каждое из этих слов является аксиомой, поэтому.

6 Пусть k N. Напомним, что для доказательства методом возвратной индукции того, что утверждение P(n) верно при любом натуральном n k, устанавливают, что для любого натурального n k из предположения (называемого индукционным предположением) верности всех P(k), P(k + 1),..., P(n 1) следует верность P(n) (в частности, при n = k непосредственно устанавливают верность P(k)). Базы индукции как таковой в этом методе не требуется, однако нам будет удобно выделять доказательство P(n) при начальных значениях n в виде базы индукции. В дальнейшем и о методе математической индукции, и о методе возвратной индукции мы для краткости будем говорить как об индукции (по натуральному параметру).

34 Герасимов А. С. Курс математической логики и теории вычислимости Индукционный переход. Предположим, что любой палиндром, длина которого меньше n (n > 2), выводим. Рассмотрим палиндром длины n.

Палиндром, очевидно, должен иметь вид xx, где x, слово, являющееся палиндромом. По индукционному предположению. Поскольку x = a или x = b, то по правилу (a) или (b) из получаем xx. Итак,.

Доказательство завершено.

Заметим, что каждое из двух правил вывода исчисления P al является и отношением, и функцией. Однако, чтобы получить тот же результат о выводимости палиндромов, мы могли вместо этих двух правил сформулировать одно правило вывода, являющееся отношением, но не являющееся функцией:

где произвольное слово языка L, c произвольный символ алфавита.

Этому отношению принадлежит, например, как пара слов a, aaa, так и a, bab. (Конец примера 1.2.2.) Упражнение 1.2.3. Задайте исчисление, в котором будут выводимы все слова, являющиеся пропозициональными формулами, и только такие слова.

Постройте выводы нескольких пропозициональных формул в этом исчислении. (Не предлагайте исчисление с бесконечным числом аксиом, например, исчисление, в котором аксиомами объявлены все пропозициональные формулы. Хотя такое решение данной задачи в принципе возможно, оно неинтересно, поскольку не приближает нас к уточнению того, как конструируются формулы из конечного числа символов некоторого алфавита.) Язык-объект и метаязык Следует отметить, что, строя выводы в каком угодно исчислении, мы пользуемся (формальным) языком этого исчисления. Например, последовательность слов () формального языка L из примера 1.2.2 является выводом в исчислении P al. Понятие вывода (или доказательства) в исчислении строго определено. Чтобы это подчеркнуть, говорят также о формальном выводе (или формальном доказательстве).

Утверждения о свойствах исчисления мы формулируем и доказываем на русском (естественном, неформальном) языке, используя убедительные математические способы доказательства; в таких случаях говорят, что проводится содержательное (или неформальное) доказательство.7 Упомянутый в предыдущем предложении естественный язык называется метаязыком (или языком исследователя). А язык, который мы изучаем (в данном случае язык исчисления P al), называется языком-объектом (или предметным языком). Конечно, при необходимости метаязык можно было бы формализовать и сделать объектом исследования, которое могло бы проводиться на некотором метаязыке.

7 О понятии содержательного доказательства и о способах доказательства, считающихся в математике убедительными (попросту говоря, принятых в математике), мы скажем подробнее в разделах 3.3.3, 3.5.5, а также в замечаниях 2.5.7, 2.6.23 и в конце раздела 5.1.5.

Индукцию по натуральному параметру и по построению формулы мы, несомненно, считаем убедительным способом доказательства. При этом, конечно, база такой индукции и индукционный переход должны быть доказаны математически убедительно.

Глава 1. Исчисления высказываний Другим примером языка-объекта и метаязыка служит английский язык и русский язык соответственно, когда преподаватель объясняет смысл фраз английского языка на русском языке.

1.2.2. Вывод из гипотез Для дальнейшего изложения нам понадобится понятие вывода из гипотез. Сейчас мы проиллюстрируем это понятие на доступном примере.

Пусть мы желаем с помощью вывода в исчислении P al получать не только палиндромы, но и слова, в каждом из которых в середине стоит слово ab, а в остальном такие слова строятся как палиндромы. Примерами таких слов являются слова ab, babb, aaba, baabab. Тогда, чтобы воспользоваться исчислением P al, можно предположить, что слово ab является дополнительной аксиомой этого исчисления, иначе говоря, считать ab гипотезой. Уточним этот пример, дав следующие определения.

Пусть C исчисление в языке L, произвольное множество слов языка L. Выводом из в исчислении C называется конечная последовательность слов, каждое из которых является аксиомой, принадлежит или получается из предшествующих слов этой последовательности по некоторому правилу вывода исчисления C. Число членов этой последовательности называется длиной этого вывода из. Элементы множества называются гипотезами вывода из.

Выводом слова из в исчислении C называется вывод 1,..., k из такой, что k совпадает с.

Говорят, что слово выводимо из в исчислении C и обозначают это как C, если существует вывод слова из в исчислении C.

Если слово не является выводимым из в исчислении C, то его называют невыводимым из в исчислении C и обозначают это через C.

Обозначения C и C могут сокращаться до и соответственно, если понятно, о каком исчислении идёт речь.

Заметим, что в выводе из может использоваться только конечное число формул из. Если множество пусто, то выводимость из него означает выводимость в исчислении C.

{} будем также записывать как,. Если состоит из конечного числа слов 1,..., n, то будем также записывать как Пример 1.2.4. Продолжим пример 1.2.2 и построим вывод слова baabab из {ab, bbba} в исчислении P al:

2) aaba получается из слова 1 по правилу (a);

3) baabab получается из слова 2 по правилу (b).

1.3. Исчисление высказываний гильбертовского типа Исчисления оказываются весьма продуктивными для формализации, поиска и исследования доказательств. В данном разделе мы изучим истоГерасимов А. С. Курс математической логики и теории вычислимости рически первое исчисление, в котором выводимы все общезначимые пропозициональные формулы и только они.

1.3.1. Формулировка исчисления Зададим так называемое исчисление высказываний гильбертовского типа, являющееся исчислением в языке P L логики высказываний. Мы будем обозначать это исчисление через H.

Аксиомами исчисления H являются все формулы, имеющие один из следующих видов:

10) ¬¬A A, где A, B, C произвольные формулы. Таким образом, каждый из пунктов 1–12 представляет схему аксиом; аксиома получается при подстановке конкретных формул в схему аксиом вместо букв A, B и C.

Единственным правилом вывода исчисления H является правило, которое называется модусом поненс (modus ponens, сокращённо M P ), а также правилом отделения, и которое позволяет получить из двух посылок A и A B заключение B, где A и B произвольные формулы. Символически это правило записывается в следующем виде:

Данное исчисление задумано так, чтобы вывод в нём оказался приемлемым способом получения общезначимых формул. Аксиомы характеризуют семантику логических связок, например, аксиому вида 8 можно интуитивно понимать так: если имеет место высказывание B, то также имеет место высказывание A или B. Правило вывода модус поненс символически представляет общеупотребительное умозаключение: если имеет место A и известно, что A влечёт B, то имеет место B. В дальнейшем мы докажем, что с помощью вывода в этом исчислении можно получить все общезначимые формулы и только их. Связь исчисления H с семантикой языка P L Глава 1. Исчисления высказываний мы начнём исследовать в следующем разделе, а сейчас рассмотрим пример вывода в этом исчислении.

Пример 1.3.1. Построим вывод формулы A A (где A произвольная пропозициональная формула):

3) (A (A A)) (A A) получается из формул 1 и 2 по M P ;

5) A A получается из формул 4 и 3 по M P.

1.3.2. Корректность исчисления Семантика языка P L логики высказываний определена путём сопоставления формулам истинностных значений в интерпретациях. Среди всех формул мы выделили логические законы. Естественное желание при изучении языка P L отвлечься от его семантики и механически получать результаты об этом языке и о его семантике, например, результаты об общезначимости. Таким механическим способом мог бы стать вывод в некотором исчислении, но при условии, что любая выводимая формула является общезначимой. Поэтому к любому исчислению, предназначенному для получения общезначимых формул, предъявляется естественное требование корректности: любая выводимая в этом исчислении формула должна быть общезначимой. В данном разделе мы докажем, что исчисление H удовлетворяет этому требованию, иначе говоря, является корректным.

Замечание 1.3.2. Заданная семантика языка P L слишком проста, чтобы почувствовать значительную пользу от исчисления (семантические вопросы об общезначимости формул можно решить с помощью таблиц истинности), но чем сложнее семантика, тем сильнее желание перейти от неё к исчислению. Однако мы знакомимся с исчислением высказываний для того, чтобы затем нам было легче перейти к языкам с более сложной семантикой и исчислениям в таких языках.

Утверждение о корректности исчисления H будет вытекать из следующей теоремы. Также эта теорема выявит то, что вывод из гипотез формализует правильное рассуждение в предположении истинности всех гипотез.

Теорема 1.3.3 (обобщённая теорема о корректности исчисления высказываний H). Пусть произвольное множество формул, A произвольная формула. Тогда если A, то A.

Д о к а з а т е л ь с т в о. Применим индукцию по длине вывода A.

База индукции. Вывод состоит из одной формулы A. Тогда A аксиома или гипотеза.

Легко проверить, что каждая аксиома исчисления H является общезначимой формулой: для этого достаточно составить таблицу истинности для каждой схемы аксиом, считая символы, обозначающие формулы в этой 38 Герасимов А. С. Курс математической логики и теории вычислимости схеме, пропозициональными переменными, а затем воспользоваться теоремой 1.1.25 о подстановке в тавтологию. Таким образом, если A аксиома, то A, следовательно, A.

Индукционный переход. Предположим, что доказываемое утверждение верно для любой формулы, являющейся последней в выводе длины, меньшей n (n > 1). Рассмотрим вывод A длины n. Случаи, когда формула A является аксиомой или гипотезой, уже разобраны выше. Остаётся разобрать случай, когда A получена из некоторых предшествующих формул B и B A этого вывода по правилу M P. Применив индукционное предположение к B и к B A, получим B и B A. Отсюда, согласно таблице истинности импликации, A.

Следствие 1.3.4. Пусть произвольное множество общезначимых формул, A произвольное формула. Тогда если A, то A.

Д о к а з а т е л ь с т в о. По теореме 1.3.3 из A следует A. В силу общезначимости всех формул из A влечёт A.

Следствие 1.3.5 (корректность исчисления высказываний H). Всякая выводимая в исчислении H формула общезначима, т. е. для любой формулы A, если A, то A.

Д о к а з а т е л ь с т в о. Возьмём в качестве пустое множество и применим теорему 1.3.3, помня, что A равносильно A, и A равносильно Следствие 1.3.6. Исчисление H непротиворечиво, т. е. не существует формулы A такой, что A и ¬A.

Д о к а з а т е л ь с т в о. Если бы нашлась такая формула A, что A и ¬A, то в силу корректности исчисления имели бы A и ¬A, что невозможно.

1.3.3. Теорема о дедукции. Допустимые правила В математических рассуждениях для доказательства утверждения вида A влечёт B нередко прибегают к такому способу: предполагают, что верно A, и в этом предположении доказывают B. Для исчисления H этот способ обосновывается следующей теоремой.

Теорема 1.3.7 (теорема о дедукции для исчисления высказываний H).

Пусть произвольное множество формул, A, B произвольные формулы. Тогда, A B, если и только если A B.

Д о к а з а т е л ь с т в о. То, что A B влечёт, A B, обосновывается применением правила M P к данному A B и очевидному, A A.

Докажем, что, A B влечёт A B. Воспользуемся индукцией по длине вывода, A B.

Глава 1. Исчисления высказываний База индукции. Вывод состоит из одной формулы B. Тогда возможны лишь 3 случая: (a) B является аксиомой, (b) B совпадает с A, (c) B принадлежит. Разберём каждый из этих случаев.

вида 1) получаем A B. Следовательно, A B.

(b) Согласно примеру 1.3.1 имеем A A, следовательно, A A, т. е. A B (поскольку B совпадает с A в рассматриваемом случае).

(c) По правилу M P из B (B принадлежит ) и B (A B) (аксиома вида 1) получаем A B.

Индукционный переход. Предположим, что доказываемое утверждение верно для любого вывода длины, меньшей n (n > 1). Рассмотрим вывод, A B длины n. Если не имеет место ни один из уже разобранных случаев (a), (b), (c), то формула B получена по правилу M P из некоторых предшествующих формул C и C B этого вывода. Применив индукционное предположение к, A C и к, A C B, получим () A C и () A (C B). По правилу M P из () и аксиомы вида (A (C B)) ((A C) (A B)) получим (A C) (A B). Отсюда и из () по правилу M P получим A B.

Условимся, что далее в разделе 1.3 символы и (возможно, с индексами) будут обозначать произвольные множества пропозициональных формул, если не указано иное.

Исчисление H удобно для некоторых теоретических исследований в силу того, что выводы в нём имеют простую структуру, поскольку в этом исчислении всего лишь одно правило вывода. Однако искать выводы в этом исчислении неудобно. Как мы могли видеть в примере 1.3.1, поиск вывода простой формулы потребовал бы некоторой изобретательности. Мы хотим иметь более удобные средства для доказательства выводимости формул.

Кроме того, желательно формализовать с помощью исчисления H обычные способы математических рассуждений (т. е. способы рассуждений, которые применяются в математических доказательствах). Здесь мы приведём вспомогательные правила, которые соответствуют обычным способам математических рассуждений. Такие вспомогательные правила иначе называют техникой естественного вывода.

Теорему 1.3.7 о дедукции можно записать в виде следующих вспомогательных правил:

Первое правило понимается так: если, A B, то A B. Как мы отметили перед формулировкой теоремы о дедукции, это правило соответствует одному из обычных способов рассуждений в математике. Это вспомогательное правило называется правилом введения импликации (или, короче, -введением). Второе правило понимается аналогичным образом: если Далее, если A и A B, то по M P получаем B. Таким образом, имеем ещё одно вспомогательное правило называемое правилом удаления импликации (или, короче, -удалением).

40 Герасимов А. С. Курс математической логики и теории вычислимости С помощью приведённых вспомогательных правил можно устанавливать выводимость некоторых формул (в том числе и из гипотез), не строя выводы целиком. При этом для доказательства выводимости некоторой формулы обычно пользуются правилами снизу вверх: чтобы установить выводимость, указанную в правиле под чертой, достаточно установить все выводимости, указанные над чертой.

Пример 1.3.8. Докажем, что для любых формул A, B и C По -введению достаточно доказать Для этого, в свою очередь, по -введению достаточно доказать Опять по -введению достаточно доказать ( ) получается по -удалению из что очевидно (см. подчёркнутую формулу и определение вывода из гипотез), и что достаточно доказать для завершения доказательства исходного утверждения. ( ) получается по -удалению из что очевидно, и так же очевидного Итак, требуемая выводимость доказана.

Проведённое доказательство удобно записать в следующем виде:

Глава 1. Исчисления высказываний Таблица 1.6. Допустимые в исчислении H правила.

Перечислим некоторые вспомогательные правила в таблице 1.5, для систематизации повторив некоторые уже известные нам.

Каждое из этих вспомогательных правил имеет вид Запись ( ) назовём допустимым (в исчислении H) правилом, если верно утверждение: 1 A1 ;... ; n An влечёт A. Подчеркнём, что, согласно данному определению, допустимые правила не являются правилами вывода рассматриваемого исчисления, а являются своеобразными записями утверждений указанного вида.

Докажем, что в таблице 1.5 действительно приведены только допустимые правила.

Д о к а з а т е л ь с т в о. Допустимость -введения и -удаления установлена ранее в этом разделе.

Для доказательства допустимости ¬-введения применим теорему о дедукции к, A B и к, A ¬B. Получим () A B и () A ¬B.

По правилу M P из аксиомы вида 9 (A B) ((A ¬B) ¬A) и () получим (A ¬B) ¬A. Отсюда и из () по правилу M P получим ¬A, что и требуется.

¬-удаление также допустимо: из ¬¬A и аксиомы вида 10 ¬¬A A по правилу M P получим A.

Далее, -введение допустимо: из A, B и аксиомы вида A (B (A B)), дважды применив правило M P, получим A B.

Каждое правило, называемое -удалением, допустимо: из A B и аксиомы вида 4 A B A по правилу M P получим A; аналогично, из A B и аксиомы вида 5 A B B по правилу M P получим B.

Каждое правило, называемое -введением, допустимо: из A и аксиомы вида 7 A A B по правилу M P получим A B; аналогично, из B и аксиомы вида 8 B A B по правилу M P получим A B.

42 Герасимов А. С. Курс математической логики и теории вычислимости Наконец, установим, что -удаление допустимо. По теореме о дедукции из, A C и, B C следует A C и B C. Отсюда и из аксиомы вида 6 (A C) ((B C) (A B C)), дважды применив правило M P, получим A B C. Применив M P к A B A B (что, очевидно, верно) и A B C, получим, A B C.

Видно, что допустимые правила, перечисленные выше, соответствуют обычным способам математических рассуждений. Например, ¬-введение соответствует способу рассуждения, называемому приведением к абсурду (нелепости, противоречию): чтобы доказать ¬A, достаточно допустить A и получить из этого допущения противоречие, т. е. для некоторого B вывести одновременно B и ¬B. -удаление соответствует способу доказательства разбором случаев: чтобы доказать, что из A или B следует C, достаточно доказать, что и из A следует C, и из B следует C.

Пример 1.3.9. Докажем, что для любых формул A и B (В силу теоремы о дедукции эту выводимость можно переписать в виде A, ¬A B и прочитать так: из противоречия выводима любая формула.) Представим доказательство в таком же виде, как и в конце примера 1.3.8:

Упражнение 1.3.10. Докажите, что следующее правило, называемое правилом сечения, допустимо:

Упражнение 1.3.11. Докажите, что следующее правило, являющееся одним из вариантов -удаления, допустимо:

Упражнение 1.3.12. Докажите, что следующее правило, являющееся одним из вариантов -удаления, допустимо:

Глава 1. Исчисления высказываний Упражнение 1.3.13. Докажите, что следующие правила допустимы:

Упражнение 1.3.14. Докажите выводимость всех логических законов, перечисленных в разделе 1.1.3.

1.3.4. Полнота исчисления В разделе 1.3.2 мы установили корректность исчисления H: всякая выводимая в исчислении H формула общезначима. В этом разделе мы докажем обратное утверждение так называемую теорему о полноте этого исчисления: всякая общезначимая формула выводима в исчислении H.

Сначала дадим несколько определений, которые будут использоваться в доказательстве.

Определение 1.3.15. Множество формул называется непротиворечивым, если не существует формулы A такой, что A и ¬A. Иначе называется противоречивым.

Определение 1.3.16. Множество формул называется полным, если для любой формулы A A или ¬A. Иначе называется неполным.

Определение 1.3.17. Пусть произвольное множество формул. Интерпретацию языка P L логики высказываний, в которой истинны все формулы множества, называют моделью множества. Если существует модель множества, то говорят, что имеет модель (или совместно).

Теорема 1.3.18. Всякое множество замкнутых формул, имеющее модель, непротиворечиво.

Д о к а з а т е л ь с т в о. Пусть множество имеет модель M. Тогда для любой формулы G верно M G. Если бы множество было противоречивым, то для некоторой формулы A выполнялось бы A и ¬A.

Тогда по обобщённой теореме 1.3.3 о корректности исчисления H мы имели бы M A и M ¬A, что невозможно. Поэтому множество непротиворечиво.

Теорему о полноте исчисления высказываний мы получим как следствие теоремы 1.3.19, обратной к только что доказанной теореме и формулируемой ниже.

Теорема 1.3.19. Всякое непротиворечивое множество формул имеет модель.

Доказательству теоремы 1.3.19 мы предпошлём две леммы, но сначала изложим идею всего доказательства. Для непротиворечивого множества формул и любой переменной p имеет место ровно одно из трёх: (1) p, (2) ¬p или (3) p и ¬p. Мы ищем модель множества, т. е. интерпретацию M, в которой истинны все формулы этого множества. По обобщённой теореме 1.3.3 о корректности исчисления H в случае (1) должно 44 Герасимов А. С. Курс математической логики и теории вычислимости быть M p, а в случае (2) M ¬p и, значит, M p. В случае (3) пока непонятно, какое истинностное значение сопоставить переменной p. Чтобы до конца определить искомую интерпретацию M, достаточно найти полное и непротиворечивое множество, содержащее : для такого множества случай (3) не может иметь места. Наконец, показав, что в заданной интерпретации M действительно истинны все формулы из, получим, что то же самое свойство имеет место и для подмножества множества.

Лемма 1.3.20. Пусть непротиворечивое множество формул, A формула. Тогда хотя бы одно из множеств {A} или {¬A} непротиворечиво.

Д о к а з а т е л ь с т в о. Предположим, что оба множества {A} и {¬A} противоречивы. Тогда найдутся такие формулы B и C такие, что По ¬-введению (см. с. 41) из, A B и, A ¬B получаем ¬A.

Аналогично из, ¬A C и, ¬A ¬C получаем ¬¬A.

Итак, имеем ¬A и ¬¬A, что противоречит непротиворечивости. Поэтому сделанное предположение неверно.

Лемма 1.3.21 (лемма Линденбаума). Всякое непротиворечивое множество формул содержится в некотором непротиворечивом полном множестве формул.

Д о к а з а т е л ь с т в о. Очевидно, язык P L счётен. Пусть A1, A2,...

все пропозициональные формулы, перечисленные в некотором порядке.

Положим 0. Для каждого i N+ определим множество i. Если i1 {Ai } непротиворечиво, то положим i i1 {Ai }. Иначе (в этом случае i1 {¬Ai } непротиворечиво по лемме 1.3.20) положим i1 {¬Ai }. Для каждого i N множество i непротиворечиво по построению.

Пусть iN i. По определению множество содержит. Для каждой формулы A множество содержит либо A, либо ¬A, и потому полно.

Чтобы утверждать, что годится в качестве искомого множества, осталось лишь доказать непротиворечивость. Если бы было противоречивым, то нашлась бы формула A такая, что A и ¬A. Тогда, поскольку в выводе может использоваться только конечное число формул из, найдётся j, при котором j A и j ¬A, что противоречит непротиворечивости j. Значит, непротиворечиво.

Д о к а з а т е л ь с т в о теоремы 1.3.19. В силу леммы 1.3.21 достаточно доказать существование модели множества, считая, что непротиворечиво и полно. Тогда для каждой пропозициональной переменной p верно либо p, либо ¬p, но не то и другое одновременно. Мы ищем интерпретацию, в которой все формулы из истинны, поэтому, согласно обобщённой теореме 1.3.3 о корректности исчисления H, в первом случае переменной p мы должны сопоставить истину, а во втором ложь. Так и определим интерпретацию M языка P L, сопоставив каждой переменной p истинностное значение 1, если p, и значение 0 иначе (т. е. если ¬p).

Глава 1. Исчисления высказываний Чтобы доказать, что любая формула из истинна в интерпретации M, достаточно доказать, что для любой формулы A M A тогда и только тогда, когда A. Воспользуемся индукцией по построению формулы A.

База индукции. A переменная или истинностная константа. Если A переменная, то доказываемое утверждение следует из определения интерпретации M. Если A истинностная константа F, то M F и F (иначе из F и аксиомы вида 11 по правилу M P получили бы, что из выводима любая формула). Если A истинностная константа T, то M T и T ( T получается по правилу M P из произвольной выводимой из формулы и аксиомы вида 12).

Индукционный переход. Предположим, что доказываемое утверждение верно для формул B и C.

1. Пусть A имеет вид ¬B. M A тогда и только тогда, когда M B. По индукционному предположению M B равносильно B. В силу непротиворечивости и полноты имеем: B тогда и только тогда, когда ¬B, т. е. когда A.

2. Пусть A имеет вид B C. M A тогда и только тогда, когда M B и M C. По индукционному предположению M B и M C, если и только если B и C.

Из B, C по -введению получаем B C. С другой стороны, из B C по -удалению получаем B и C. Таким образом, B и C тогда и только тогда, когда B C, т. е. когда A.

Оставшиеся случаи 3 (A имеет вид B C) и 4 (A имеет вид B C) рассматриваются аналогично случаю 2 и остаются в качестве упражнения.

Упражнение 1.3.22. Разберите случаи 3 и 4 в доказательстве предыдущей теоремы.

Теорема 1.3.23 (теорема о компактности для логики высказываний).

Пусть множество формул. Тогда если всякое конечное подмножество множества имеет модель, то имеет модель.

Д о к а з а т е л ь с т в о. Пусть всякое конечное подмножество множества имеет модель. Однако предположим, что не имеет модели.

Тогда по теореме 1.3.19 множество противоречиво, т. е. существует формула A такая, что A и ¬A. Найдётся конечное множество такое, что 0 A и 0 ¬A. Таким образом, 0 противоречиво.

По теореме 1.3.18 из противоречивости 0 следует, что 0 не имеет модели. Это противоречит условию доказываемой теоремы, поэтому предположение неверно, а имеет модель.