Прикладная логика

Н. Н. Непейвода 

ПРИКЛАДНАЯ 

ЛОГИКА 

Учебное пособие 

Третье издание, 
существенно переработанное и дополненное 

Москва 
Берлин 
2019 

УДК 517.11(075)
ББК 22.12я73  
        Н53 

Первое издание книги было частично поддержано Минвузом России, 
гранты 94-1.17-336, программа «Фундаментальные исследования 
в естествознании» и «Логические операторы», Новосибирский центр 
по математическим наукам, 1996. Второе издание книги было 
поддержано фирмой «Новософт», г. Новосибирск 

Непейвода, Н. Н. 

Н53 
 
Прикладная логика : учебное пособие / Н. Н. Непейвода. — 
3-е изд., существ. перераб. и доп. — Москва , Берлин : Директ-Медиа, 
2019. — 575 с. : ил. DOI: 10.23681/561272

ISBN 978-5-4499-0126-2 

Данное пособие содержит введение в язык современной математики и методы 
современной логики, основные важнейшие для приложений и методологии результаты логики ХХ века, советы по применению методов и методологии логики в информатике и информационном анализе сложных задач, методологический и философский анализ следствий приведённых результатов и методов. Впервые в мировой литературе оно содержит систематическое изложение конструктивной математики с 
точки зрения как современной информатики, так и многоуровневого анализа её 
успехов и уроков. Его можно использовать совместно с обучающими программами 
высокого уровня и программами проверки рассуждений, подобными AGDA. 
Рекомендовано Государственным комитетом Российской Федерации по высшему образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям «Математика», «Прикладная математика», 
«Лингвистика», «Философия» и «Психология». 
Предыдущие версии книги выпущены издательствами УдГУ, 1997 (1-е издание); 
НГУПресс, 2000 г. (2-е издание, исправленное и дополненное). 

Текст приводится в авторской редакции. 

ISBN 978-5-4499-0126-2 
© Непейвода Н. Н., текст, 2019 
© Издательство «Директ-Медиа», оформление, 2019 

УДК 517.11(075)
ББК 22.12я73  

Α. Α. Марков 
Α. Г. Драгалин 
Β. Α. Журавлёв 

(09.09.1903— 
(10.04.1941 — 
(01.02.1941 — 

11.10.1979). 
18.12.1998). 
27.01.2007). 

Посвящаю эту книгу душам: моих учителей академика Андрея Андреевича Маркова и профессора Альберта Григорьевича Драгалина, научившим меня не только науке, 
но и умению быть самим собой; ректора Удмуртского государственного университета Виталия Анатольевича Журавлёва, сделавшего возможным противоречившее всем 
устоявшимся обычаям и инструкциям преподавание, которое заставило меня развить 
и углубить свои взгляды и подарило много н о в х идей. 

Благодарю свою жену Людмилу, с которой мы вместе прошли жизнь и которая мно¬
го дала мне и как человек, и как оригинальнй педагог и логик; моей дочери 
нтонине, 
которая стала моим продолжателем и поддерживала меня в работе над книгой. 

так е коллектив дГ 
и б ы в и х моих студентов (за искл чением последней 
группы, у которой я начал преподавать и о у т и л глубину и быстроту деградации об¬
разования и студенчества до состояния «онижедети»). 

i 

Оглавление 

Введение 
x 

In.1. Что такое современная логика? 
x 

In.2. Методологические принципы, на которых основано данное изложение 
xix 

In.3. Как работать с данной книгой? 
xxiv 

In.4. Введение ко второму изданию 
xxvii 

In.5. Введение к третьему изданию 
xxviii 

I 
Язык математики 
1 

1. Необходимость точного языка в математике 
2 

1.1. 
Как и почему появился я з к математической логики? 
2 

1.2. 
Зачем изучать формальный язык математики? 
7 

2. Простейшие высказывания 
13 

2.1. Что такое высказывание? 
13 

2.2. 
Математическая интерпретация высказываний 
18 

2.3. 
Предметы и унивёрс. Термы 
19 

2.4. 
Предикаты и элементарные формулы 
21 

2.5. 
екоторе обозначения 
23 

3. Запись высказываний. Логические формулы 
26 

3 6 
Таблицы истинности 
30 

ii 

ОГЛАВЛЕНИЕ 

4. Методы перевода с естественного языка на математический и обратно 
38 

4 1 Кванторы 
бласти действия 
38 

4.2. 
"Многоэтажные" кванторы. Дополнительные 
ограничения 
40 

4.3. 
«Если на клетке слона увидишь надпись "буйвол", не верь глазам своим» 47 

4.4. 
Таблицы истинности и формулировка отрицаний 
51 

4.5. 
р о с т е й и е преобразования классических формул 
53 

4.6. 
арадокс кучи куч 
55 

4.7. 
Равенство. Единственность и неединственность 
56 

5. Базовые математические понятия 
62 

5.1. Множества. Диаграммы Эйлера и Венна 
62 

5.2. Кортежи, n-ки, наборы, прямые произведения, прямые суммы 
71 

5.3. 
т н о е н и я 
76 

5 7 
Графы 
102 

II 
Классическая логика 
115 

6. Индукция 
116 

6.2. Об индуктивных определениях 
121 

6 3 
Трансфинитная индукция и ординал 
125 

6.3.1. 
Построение начального отрезка ординалов 
125 

6.3.2. 
Свойства вполне упорядоченных множеств 
127 

6.3.3. 
Представления ординалов. Действия над ординалами 
130 

6.3.4. 
остроение функций рекурсией по определени 
либо параметру 135 

7. Введение в синтаксис 
138 

7.2. Корректность синтаксических определений 
145 

7.3. Свободные и связанные переменные. Подстановка 
150 

8. Семантика классической логики 
155 

8.2. Теория, модель, логическое следствие 
159 

8.3. Теорема о замене эквивалентнх 
163 

8.4. Булевы алгебры и алгебраическая семантика 
164 

8.5. Языки высших порядков 
167 

iii 

ОГЛАВЛЕНИЕ 

9. Семантические таблицы для классической логики 
170 

9.1. 
т таблиц истинности к семантическим таблицам 
170 

9.2. 
равила разбиения формул в семантических таблицах 
172 

9.3. Семантические таблицы с кванторами 
175 

9.4. С о к р а ё н н е семантические таблиц 
180 

9.5. Исчисления традиционного типа 
186 

9.6. Секвенции и формализация семантических таблиц 
191 

9.7. Семантические таблицы с равенством и для теорий 
195 

9.8. Теорема полноты 
198 

10. Элементы нестандартного анализа 
213 

10.2. 
естандартная модель 
217 

10.3. Hестандартная действительная ось 
219 

10.4. 
естандартне переформулировки 
223 

10.5. Суперструктуры и теорема Лося 
227 

10.5.1. 
ксиома выбора, некоторые её следствия и альтернатив 
. . . . 227 

10.5.2. 
льтрафильтры и структуры 
231 

11. Естественный вывод в классической логике 
234 

11.1. 
структуре математических доказательств 
234 

11.2. Правила естественного вывода 
236 

11.2.1. Общая структура. Импликация и конъюнкция 
236 

11.2.2. Дизъюнкция и разбор случаев 
238 

11.2.3. Отрицание. Приведение к абсурду и "от противного". A V —A . 239 
11.2.4. Hекоторые полезные выводимые правила 
240 

11.3. Естественный в в о д как граф 
244 

11.4. 
равила формулировки отрицанийи согласованность с классической 
истинностью 
246 

11.5. Теорема полноты естественного вывода 
250 

11.6. Логика с равенством и ее полнота 
254 

11.7. Метод резолюций и его сравнение с методом 

естественного вывода 
255 

11.8. Окольные пути как средство сокращения вывода 
261 

11.9. 
есколько слов о я з к е 
ролог 
263 

12. Основы теории определений 
266 

12.2. С о к р а а и е определения 
267 

12.3. Теорема 
рейга об интерполяции 
268 

12.4. Теорема Бета об определимости 
271 

iv 

ОГЛАВЛЕНИЕ 

13. 
еполнота и не ор ализуе ость 
273 

13.1. Теорема Тарского о невыразимости истины 
273 

13.2. Аксиоматическое описание вычислимости 
275 

13.3. 
редставимость через доказуемость 
285 

13.4. Неполнота 
291 

13.5. Вокруг теоремы Гёделя 
292 

13.6. Формализация неформализуемых понятий 
297 

13.7. 
онстр 
302 

I I I 
Введение в неклассические логики 
305 

14. Основы λ-исчисления 
306 

14.2. λ-конверсии 
308 

14.3. Теорема о сходимости (Чёрча-Россера) 
313 

14.4. λ-исчисление 
315 

14.5. Комбинаторная логика 
316 

14.6. Эквивалентность S, K и λ-исчисления 
319 

14.7. Типизация 
320 

14.8. Эквивалентность вчислимости и λ 
323 

15. Корни неклассических логик 
324 

15.1. Корни неклассических логик в традиционной логике 
324 

15.1.1. Закон то дества 
324 

15.1.2. Закон непротиворечия 
326 

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

15.1.4. Закон достаточного основания 
328 

15.2. Сила и недостатки классической логики 
331 

15.3. Использование доказательств 
332 

15.3.1. Сведение новой задачи к уже решенным 
333 

15.3.2. Вявление условий, при которх мо но пользоваться данным 
утвердением 
334 

15.3.3. 
олучение построения, д а е г о некоторый результат 
335 

15.3.4. 
роизнесение заклинания, дабы освятить своё либо предло ен
ное заказчиком р е е н и е 
336 

15.4. 
чём не принято говорить сейчас 
337 

16. Интуиционистская логика 
339 

16.1.1. Брауэр: идея конструктивности 
339 

16.1.2. Формализация и первые интерпретации 
342 

16.1.3. Разногласия и н о в е идеи 
342 

16.1.4. 
ериод после Брауэра 
343 

v 

Г Л В Л Е Е 

16.1.5. Вторая героическая эпоха: математические результаты и 

п о п т к и прило ений 
345 

16.2. 
нтерпретация реализуемости 
345 

16.3. 
ормализация Гливенко-Гейтинга 
351 

16.4. 
ервые модели интуиционистской логики 
353 

16.5. 
одели Крипке 
355 

16.6. Семантические таблицы для интуиционистской логики 
359 

16.7. Полнота семантических таблиц 
364 

16.8. Фундаментальные результаты теории доказательств 
365 

16.9. Реализуемости и вариации интуиционистских принципов 
369 

16.10. нтуиционистская логика и категории 
371 

17. Семантики Крипке и базирующиеся на них логики 
374 

17.1. 
б а я идея 
374 

17.2. 
одальные логики и их модели Крипке 
376 

17.2.1. Язык и общая конструкция модели 
376 

17.2.2. Свойства отноения достиимости и конкретные логики 
. . . 377 

17.2.3. Нешкальные логики 
378 

17.3. Временные, динамические и программные логики 
379 

18. 
роблема отрицания 
381 

18.1. Три стороны классического отрицания и четвёртая — содержательного 
381 

18.2. 
инимальная логика 
383 

18.3. Логика с с и л ь н м отрицанием 
384 

18.4. Логика неполной информации 
386 

18.5. 
снов 
логики противодействия 
387 

18.6. Паранепротиворечивая логика 
388 

I V 
Конструктивные и методологические аспекты логики 
389 

19. Конструктивизм 
391 

19.2. Соглашения об обозначениях 
392 

19.3. Предпосылки конструктивизма 
393 

19.4. Появление конструктивизма 
397 

19.4.1. Интуиционизм и программа Гильберта 
400 

19.5. Базовые принцип 
и методы конструктивизма 
403 

19.5.1. Принцип конечной информации и чум-пространства 
403 

19.5.2. 
етод провокации и некорректные задачи 
410 

19.6. 
нтуиционистская логика как конструктивная 
418 

vi 

Г Л В Л Е Е 

20. 
лгорит 
и реализуе ость 
428 

20.2. Советский конструктивизм 
430 

20.3. Недостатки советского конструктивизма 
437 

21. Интуиционизм как альтернатива алгоритмическому конструктивизму 
445 

21.1. 
формализации незнания 
445 

21.2. 
ромеуточные вариант 
конструктивизма 
448 

21.3. 
одели конструктивных теорий 
450 

21.4. Различие вместо равенства 
451 

21.5. 
нализ логических принципов 
451 

21.6. 
еудачная попытка прило ения 
456 

22. Доказательства и программы 
459 

22.2. Систем 
в с и х типов 
461 

22.3. 
ризраки и классификация выводов 
462 

22.4. Теорема о верификации 
463 

22.5. Проблема совместимости операторов на примере exit 
464 

23. Методологические следствия теорем о неполноте 
467 

23.1. 
б о б ё н н е вчислительные систем 
467 

23.2. 
б о б е н и е колмогоровской сло ности 
470 

23.3. 
б о б е н и е теоремы Чейтина 
471 

23.4. 
бобённая теорема Гёделя о неполноте 
472 

23.5. Алгоритмическая случайность и антиномии Канта 
473 

23.6. Закон комитета 
476 

23.7. Трёхглавый дракон 
477 

23.8. 
редел Чейтина и парадокс изобретателя 
479 

23.9. Следствия для организации творческой работы 
481 

23.10Предел Чейтина и языки программирования 
483 

24. Прикладная логика 
485 

25. Формализация и деформализация 
489 

25.2. 
роцесс р е е н и я задачи 
490 

25.4.2. В б о р логики 
493 

25.4.3. Замена понятий 
500 

25.4.4. 
странение м е а и х факторов 
500 

25.4.5. Эффективность 
501 

vii 

Г Л В Л Е Е 

25.6. 
еформализация 
504 

25.6.1. Нетривиальность процесса деформализации 
504 

25.6.2. 
спекты деформализации 
504 

25.7. Эстетика, эффективность и адекватность 
506 

25.8. Следствия и благодарности 
508 

б и е принцип 
и в в о д 
. В а н е й и е определения 
510 

viii