Логика высказываний

Московский государственный университет
имени М. В. Ломоносова
Факультет вычислительной математики 
и кибернетики
С. И. Гуров
ЛОГИКА
ВЫСКАЗЫВАНИЙ
Учебное пособие
Издательство Московского
университета
2015

УДК 510.63 
ББК 22.12   
          Г95
Печатается по решению редакционно-издательского совета 
факультета вычислительной математики и кибернетики
МГУ имени М. В. Ломоносова
Р	


д-р. физ.-мат. наук, профессор 
В. А. Захаров
Г95
Гуров С. И.
Логика высказываний: Учебное пособие. – М.: Издательство Мос 
ковского университета, 2015. – 268 с. – (Бакалавриат. Учебные пособия).
ISBN 978-5-19-011105-7
Предлагаемое учебное пособие предназначено для студентов, начинающих изучать математическую логику, оно также может быть использовано при самообразовании.
Подчёркиваются алгебраические аспекты исчислений высказываний 
классической и интуиционистской логик. Изложены методы характеризации формул логики высказываний, подробно рассмотрены гильбертовские исчисления, система натурального вывода и исчисление секвенций для исчисления высказываний. Для каждой из трёх систем рассматривается соответствующая мета 
теория. Рассматриваются семантические 
методы характеризации формул. 
Пособие содержит большое количество примеров, позволяющих читателю легко освоиться с вводимыми понятиями.
УДК 510.63 
ББК 22.12
ISBN 978-5-19-011105-7
© С. И. Гуров, 2015
© Факультет вычислительной математики 
и кибернетики МГУ имени М. В. Ломоносова, 2015
© Издательство Московского университета, 2015

Оглавление
3
Оглавление
1
Алгебра логики
6
1.1
Классическая алгебра высказываний C2 . .
6
1.1.1
Высказывания, формулы и интерпретация
. . . . . . . . . . . . . . . . . .
6
1.1.2
Булева алгебра. Оператор замыкания.
Язык функций и язык формул . . . .
15
1.2
Бинарные отношения на множестве формул
24
1.2.1
Типы формул алгебры логики. Тавтологии.
. . . . . . . . . . . . . . . .
24
1.2.2
Логическая эквивалентность . . . . .
28
1.2.3
Логическое следование . . . . . . . .
34
1.3
Характеризация формул C2
. . . . . . . . .
41
1.3.1
Элементарные методы характеризации 41
1.3.2
Метод семантических таблиц . . . . .
45
1.3.3
Метод резолюции
. . . . . . . . . . .
52
1.4
Об интуиционистской логике I . . . . . . . .
61
1.4.1
Кризис оснований математики и интуиционизм . . . . . . . . . . . . . . .
61
1.4.2
Тр¼хзначная
интерпретация
фрагмента интуиционистской логики . . .
67
2
Исчисления высказываний
70
2.1
Логические исчисления . . . . . . . . . . . .
70
2.1.1
Синтаксическое задание исчислений
71
2.1.2
Семантика исчисления. Метаязык и
метатория. О теории доказательств .
75
2.2
Исчисление высказываний H
. . . . . . . .
80
2.2.1
Синтаксис и семантика ИВ H
. . . .
80
2.2.2
Свойства выводимости
. . . . . . . .
86
2.2.3
Теорема о дедукции . . . . . . . . . .
96

Оглавление
2.2.4
Дедуктивная эквивалентность . . . .
103
2.3
Метатеория ИВ H . . . . . . . . . . . . . . .
106
2.3.1
Корректность и непротиворечивость
106
2.3.2
Семантическая полнота . . . . . . . .
109
2.3.3
Различные виды дедуктивной полноты и разрешимость
. . . . . . . . . .
119
2.3.4
Независимость системы аксиом
. . .
121
2.3.5
Элементарное доказательство семантической полноты ИВ H
. . . . . . .
124
2.4
Исчисления высказываний H1 . . . . . . . .
127
2.4.1
Описание ИВ H1 . . . . . . . . . . . .
127
2.4.2
Свойства ИВ H1 . . . . . . . . . . . .
129
2.5
Типы классических ИВ и их представления
137
2.5.1
ИВ гильбертовского типа . . . . . . .
137
2.5.2
Выводимость как оператор замыкания 146
3
Секвенциальные исчисления
148
3.1
Исчисление N натурального вывода . . . . .
148
3.1.1
Определение
исчисления
N
натурального типа
. . . . . . . . . . . . .
149
3.1.2
Доказательство в виде дерева. Новые
допустимые правила в ИC N . . . . .
160
3.1.3
Основные свойства ИC N . . . . . . .
168
3.1.4
Метатеория ИC N . . . . . . . . . . .
173
3.1.5
Поиск вывода формул в ИC N . . . .
181
3.2
Исчисление секвенций S
. . . . . . . . . . .
195
3.2.1
Определение ИC S . . . . . . . . . . .
196
3.2.2
Свойства ИC S. Метатеория и поиск
доказательств
. . . . . . . . . . . . .
202
3.2.3
Допустимость
правила
сечения
и
непротиворечивость ИC S
. . . . . .
213
4
Интуиционистские ИВ и ИС
218
4.1
Синтаксис интуиционистского ИВ I . . . . .
218
4.1.1
Аксиоматика и основные свойства . .
218
4.1.2
Системы NI и SI
. . . . . . . . . . .
223

Оглавление
5
4.2
Семантика ИИВ . . . . . . . . . . . . . . . .
227
4.2.1
Логические матрицы
. . . . . . . . .
227
4.2.2
Шкалы Крипке . . . . . . . . . . . . .
230
Персоналия и авторский указатель
238
Список литературы
266

Глава 1. Алгебра логики
Глава 1
Алгебра логики
Логика бывает разной. Одинаковым бывает только е¼ отсутствие.
Стас Янковский.
Различают философскую логику (науку о наиболее
общих законах человеческого мышления) и е¼ составную часть  формальную логику, в которой исследуются структура рассуждений и доказательств на основе анализа их формы. Теория познания определяет два способа
получения нового знания: пут¼м опыта и пут¼м умозаключений. Законы формальной логики призваны обеспечить
правильный вывод нового знания из уже известного, т.е.
пут¼м умозаключений. Данное учебное пособие находится
в рамках формальной логики.
1.1
Классическая алгебра высказываний
C2
1.1.1
Высказывания, формулы и интерпретация
Алгебра логики изучает структуру и свойства высказываний. Под высказыванием понимают предложение на
естественном или искусственном языке, которое принципиально (при точном определении условий места, времени,
наличия тех или иных обстоятельств и т. д.) можно как-то
оценить с точки зрения его истинности. Такими оценками
могут быть: ¾истинно¿, ¾ложно¿, ¾вероятно¿ (более или
менее), ¾обязательно¿, ¾необходимо¿, ¾возможно¿ (в той

1.1. Классическая алгебра высказываний C2
7
или иной степени), ¾невозможно¿ и т. д. Далее в алгебре
логики отвлекаются от всех прочих характеристик высказывания, в том числе и от его смысла (!), и рассматривают
только его истинностную оценку. В связи с этим заметим,
что любая формализация пренебрегает теми или иными
сторонами содержания в пользу формы1.
В
классической
алгебре
логики
высказывание

это утвердительное или отрицательное повествовательное
предложение, про которое можно сказать, истинно оно или
ложно. Таким образом, количество истинностных значений высказывания здесь минимально возможно: их только два  ¾истинно¿ и ¾ложно¿, которые мы будем обозначать 1 и 0 соответственно. В силу этого классическую
алгебру логики называют двухвалентной и обозначают
C2. На множестве данных истинностных значений вводят рефлексивное отношение порядка ⩽, полагая 0 ⩽1.
Установленная истинность высказывания считается неизменной в данном рассмотрении. Высказывания указанного
типа называют в логике дискриптивными, или описательными. Отметим, что высказывания соответствуют суждениям в философской логике (если отвлечься от структуры
последних), выражающим связь между понятиями и обладающим свойством быть истинными или ложными.
Пример 1.1. 2 Привед¼нные ниже выражения являются
высказываниями в C2.
1. Земля  шар.
2. Земля плоская.
3. Курица не птица.
4. 6 делится на 2 и на 3.
5. Здесь раст¼т дерево.
1 Подчеркн¼м, что в алгебре логике сначала дают оценку высказыванию, а затем уже отвлекаются от его смысла: иначе потенциально можно дать любую истинностную оценку любому выражению.
2 В данном пособии принята сквозная в пределах глав общая нумерация примеров, определений, теорем и лемм.

Глава 1. Алгебра логики
6. Все совершенные числа ч¼тные.
Истинность/ложность высказываний (1)(4) раз и навсегда установлена. Высказывания, аналогичные (5), называют неопредл¼нными. Их принято включать в дискриптивные высказывания, поскольку при конкретизации
соответствующих условий они получают оценку ¾истинно¿ или ¾ложно¿. Истинностная оценка высказывания (6)
неизвестна, однако она не зависит от каких-либо привходящих обстоятельств. Последний пример также показывает, что хотя установление истинности/ложности высказываний может потребовать значительных усилий, в логике важна лишь принципиальная возможность указанной
оценки.
Пример 1.2. Привед¼нные ниже выражения высказываниями в C2 не являются.
7. Ты кто такой?
8. Как хорошо быть генералом!
9. В
завтрашнем
футбольном
матче
¾Спартак¿
¾Динамо¿ победит ¾Спартак¿
10. Я лгу.
11. x + y = 2.
Выражение (7) не является повествовательным, то есть
утверждающим или отрицающим нечто. Повествовательное предложение (8) относится к так называемым оценочным, выражающими субъективное мнение того или иного лица, и поэтому в классической логике они не рассматриваются. Истинность утверждения (9) не выражается адекватно в терминах ¾истина/ложь¿, однако для него
возможны оценки, например, вероятностного типа. Утверждение (10)  его называют парадоксом лжеца  принципиально не может быть ни истинным, ни ложным3. Истинность выражения (11) зависит от конкретных значений
3 В античной Греции был обнаружен парадокс, возникший из со

1.1. Классическая алгебра высказываний C2
9
входящих в него переменных из некоторой области определения, отличной от {0, 1}. Выражения такого типа называют высказывательными формами.
Перейдем теперь к операциям над высказываниями.
Отметим сначала, что каждое из высказываний (1), (2),
(5) и (6) представляет собой одно неразложимое утверждение. Такие высказывания называют простыми (элементарными, атомарными). С другой стороны, высказывания (3) и (4) примера 1.1 включают в себя более простые
утверждения: высказывание (3) есть отрицание некоторого факта, в высказывании (4) утверждается совместная
справедливость двух свойств.
Поскольку в классической алгебре логике высказывания бывают либо истинными, либо ложными, и рассматривается они только с этой точки зрения, каждому элементарному высказыванию сопоставляют пропозициональную4 или логическую переменную, принимающую
значения 1 или 0. Эти переменные мы будем обозначать
строчными латинскими буквами, возможно с индексами,
с середины алфавита: p, q, . . . , z, а вс¼ их множество 
V ar.
держащего фразу ¾Критяне, вечные лжецы...¿ стихотворения, приписываемому полулегендарному поэту-прорицателю Эпимениду из
Крита (IV в. до н.э.). В философской традиции парадокс принял
форму ¾Критянин Эпименид заявил, что все критяне  лжецы¿.
Однако, если все критяне  лжецы, то Эпименид, поскольку он сам
критянин, лж¼т и, следовательно, не все критяне лжецы. Выходит,
из высказывания Эпименида следует только существование критянина, который не лж¼т. Это не является невозможным, и поэтому
здесь нет никакого парадокса. Парадокс возникает при трактовке
отрицания, в которой утверждение Эпименида, поскольку он сам
критянин, означает ¾Все критяне говорят только правду¿. Данный
недостаток исправлен в вышепривед¼нном изречении, восходящем
к Ж. Буридану.
Отметим, что невозможность истинностной оценки подобных выражений лежит в основе ряда замечательных теорем математической логики.
4 propositio (лат.)  высказывание, суждение

Глава 1. Алгебра логики
Высказывания, которые получаются из других высказываний с помощью грамматических связок ¾не¿, ¾и¿,
¾или¿, ¾если..., то...¿ (¾из... следует...¿), ¾тогда и только
тогда, когда¿ (¾..., если и только если...¿, ¾эквивалентно¿)
называют сложными или составными. Указанные грамматические связки заменяют логическими связками ¬5,
N , ∨,


 и ≡, т.е. отрицания, конъюнкции, дизъюнкции,
импликации и тождества соответственно. В результате такой замены образуются формулы из пропозициональных
переменных или формулы алгебры логики над введ¼нным
множеством логических связок; они относятся к синтаксису логики.
Формулы алгебры логики и соответствующие им сложные высказывания будем обозначать прописными латинскими буквами из начала алфавита6: A, B, . . ..
Напомним правила построения формул алгебры логики и понятия, с ними связанные.
1) любая пропозициональная переменная;
Определение 1.3. Формулой (алгебры логики) над множеством Φ =
n
¬ , N , ∨,


, ≡
o
логических связок называется выражение вида
2)
(¬A), (A N B), (A ∨B), (A


B), (A ≡B), где A и
B  формулы над Φ.
Аналогично определяются формулы над произвольным множеством связок.
5 В отечественном типографском наборе ранее часто использовали знак
.
6 Отметим, что в логической литературе часто используются традиционные обозначения элементарных высказываний произвольными прописными латинскими буквами (и именно с начала алфавита),
а формул над ними  выбором особых либо шрифта, либо алфавита. Так же традиционно для формул используют готический шрифт,
хотя встречаются и рукописный шрифт, и греческий алфавит. В последнее время, однако, наблюдается тенденция к упрощению обозначений.