Читать онлайн «Математическая логика и теория алгоритмов. Учебник»

Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ С. В. СУДОПЛАТОВ, Е. В. ОВЧИННИКОВА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ УЧЕБНИК для дистанционного образования НОВОСИБИРСК 2006  Рецензенты: А. Г. Пинус — д-р физ. -мат. наук, проф. ; В. М. Зыбарев — канд. техн. наук, доц. Сергей Владимирович Судоплатов Елена Викторовна Овчинникова Математическая логика и теория алгоритмов В книге излагаются основные классические исчисления математи- ческой логики: исчисления высказываний и исчисления предикатов, а также элементы теории алгоритмов и неклассических логик. Книга предназначена для студентов технических вузов, изучающих математическую логику и теорию алгоритмов в рамках дистанционно- го образования. c Судоплатов С. В. , Овчинникова Е. В. , 2006. ° Оглавление Предисловие 4 Г л а в а 1. Исчисления высказываний 5 § 1. 1. Определение формального исчисления . . . . . . . . . . . . . . . . . . . . . . 5 § 1. 2. Исчисление высказываний генценовского типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 § 1. 3. Эквивалентность формул . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 § 1. 4. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 § 1. 5. Семантика исчисления секвенций . . . . . . . . . . . . . . . . . . . . . . . . . 16 § 1. 6. Исчисление высказываний гильбертовского типа . . . . . . . . . . . . . . . . 20 § 1. 7. Алгоритмы проверки общезначимости и противоречивости в ИВ . . . . . 22 § 1. 8. Логические задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 § 1. 9. Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Г л а в а 2. Логика и исчисление предикатов 30 § 2. 1. Формулы сигнатуры Σ. Истинность формулы на алгебраической системе . 31 § 2. 2. Секвенциальное исчисление предикатов . . . . . . . . . . . . . . . . . . . . . 37 § 2. 3. Эквивалентность формул в ИПCΣ . . . . . . . . . . . . . . . . . . . . . . . . 43 § 2. 4. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 § 2. 5. Теорема о существовании модели . . . . . . . . . . . . . . . . . . . . . . . . . 46 § 2. 6. Исчисление предикатов гильбертовского типа . . . . . . . . . . . . . . . . . 48 § 2. 7.