Читать онлайн «Курс математической логики и теории вычислимости»

А. С. Издательство «ЛЕМА» Санкт-Петербург 2011 УДК 510. 6+510. 2+510. 5+512. 54. 05+004. 05 ББК 22. 12 Г37 Герасимов А. С. Курс математической логики и теории вычислимо- сти: Учебное пособие. 3-е изд. , испр. и доп. — СПб. : Издательство «ЛЕМА», 2011. — 284 с. ISBN 978-5-98709-292-7 Настоящее учебное пособие предназначено для изучения математической ло- гики и теории алгоритмов. В нём описаны языки логики высказываний и логики предикатов первого порядка, семантика этих языков. На основе общего поня- тия исчисления изложены исчисления гильбертовского типа, секвенциальные ис- числения и метод резолюций как способы формального математического доказа- тельства. Рассмотрены основные формальные аксиоматические теории — элемен- тарная арифметика и теория множеств Цермело-Френкеля. Теория алгоритмов представлена теорией вычислимости, в рамках которой дано несколько точных определений понятия алгоритма и доказана неразрешимость некоторых проблем. Дополнительная глава посвящена исчислению для формального доказательства правильности программ некоторого императивного языка программирования. В данной книге имеется более 190 упражнений. Это учебное пособие адресовано в первую очередь студентам, специализи- рующимся по информатике, но будет полезно студентам разных математических специальностей (направлений подготовки), а также всем желающим начать си- стематическое изучение математической логики. Александр Сергеевич Герасимов Курс математической логики и теории вычислимости Подписано в печать 12. 01. 2011. Формат 60 × 84/16. Бумага офсетная. Тираж 25 экз. Усл. п. л. 16,7. Заказ N 1865. Отпечатано в ООО «Издательство ”ЛЕМА”» 199004, Россия, Санкт-Петербург, В. С. Герасимов, 2009, 2010, 2011 Оглавление Предисловие 7 Начальные соглашения об обозначениях 9 Глава 1. Исчисления высказываний 11 1. 1. Пропозициональные формулы и булевы функции . . . . . . . 11 1. 1. 1. Формальные языки . . . . . . . . . . . . . . . . . . . . . 11 1. 1. 2. Язык логики высказываний . . . . . . . . . . . . . . . . 13 1. 1. 3. Семантика языка логики высказываний. Логические законы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1. 1. 4. Выражение булевой функции формулой.