Читать онлайн «Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления»

ЛЕКЦИИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ Н. К. Верещагин, А. Шень ЯЗЫКИ И ИСЧИСЛЕНИЯ Издание четвёртое, исправленное Москва Издательство МЦНМО, 2012 УДК 510. 6 ББК 22. 12 В31 Верещагин Н. К. , Шень А. В31 Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. — 4-е изд. , испр. — М. : МЦНМО, 2012. — 240 c. ISBN 978-5-4439-0013-1 Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказы- вается об основных понятиях математической логики (логика высказы- ваний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей). Изло- жение рассчитано на учеников математических школ, студентов-матема- тиков и всех интересующихся математической логикой. Книга содержит около 200 задач различной трудности. Предыдущее издание книги вышло в 2008 г. ББК 22. 12 Тексты, составляющие книгу, являются свободно распространяемыми и доступны по адресу ftp://ftp. mccme. ru/users/shen/logic/firstord Николай Константинович Верещагин Александр Шень Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления Подписано в печать 11. 04. 2012 г. Формат 60 × 90 1/16. Бумага офсетная. Печать офсетная. Печ. л. 15,0. Тираж 1000 экз. Заказ № Издательство Московского центра непрерывного математического образования. 119002, Москва, Б. Власьевский пер. , 11. Тел. (499) 241–74–83. Отпечатано с готовых диапозитивов в ППП «Типография Наука“ ». ” 121099, Москва, Шубинский пер. , 6. c Верещагин Н. К. , ISBN 978-5-4439-0013-1 Шень А. , 2000, 2012  Оглавление Предисловие 5 1. Логика высказываний 8 1. 1. Высказывания и операции . . . . . . . . . . . . . . . . . 8 1. 2. Полные системы связок . . . . . . . . . . . . . . . . . . 15 1. 3. Схемы из функциональных элементов . . . . . . . . . . 22 2. Исчисление высказываний 40 2. 1. Исчисление высказываний (ИВ) . . . . . . . . . . . . . . 40 2. 2. Второе доказательство теоремы о полноте . . . . . . . . 48 2. 3. Поиск контрпримера и исчисление секвенций . . . . . . 53 2. 4. Интуиционистская пропозициональная логика . . . . . 58 3. Языки первого порядка 72 3. 1. Формулы и интерпретации . . . . . . . . . . . . . . . . . 72 3. 2. Определение истинности . . . . . . . . . . . . . . . . . . 76 3. 3.