Книга: Курс математической логики и теории вычислимости

Скачать

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

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

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