Читать онлайн «Основы формальных логических языков»

Санкт-Петербургский Государственный Институт Точной Механики и Оптики (Технический Университет) Факультет Информационных Технологий и Программирования Кафедра Компьютерных технологий М. А. Коротков Е. О. Степанов Основы формальных логических языков Санкт-Петербург 2003  УДК 510. 62, 510. 63, 510. 65, 510. 675, 510. 676. Коротков М. А. , Степанов Е. О. Основы формальных логических языков. СПб: СПб ГИТМО (ТУ), 2003. 84с. Данное учебное пособие посвящено основам формальных логических языков. В нем дается краткое изложение языков логики первого и второго порядков, эле- ментов теории доказательств, теории моделей и формальной теории множеств. Пособие основано на курсе лекций, читаемом на кафедре Компьютерных тех- нологий Санкт-Петербургского Государственного Института Точной Механики и Оптики. Пособие предназначено для студентов компьютерных и математических спе- циальностей. Утверждено к печати Ученым Советом факультета Информационных Техно- логий и Программирования, протокол №5 от 09. 01. 03. ISBN 5-7577-0122-6 c Санкт-Петербургский Государственный Институт Точной Механики и Оп- ° тики (Технический Университет), 2003. c М. А. Коротков, Е. О. Степанов, 2003. ° Оглавление 1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Языки логики предикатов первого порядка . . . . . . . . . . . . . . 8 2. 1 Алфавит и сигнатура . . . . . . . . . . . . . . . . . . . . . . . 8 2. 2 Синтаксис языка первого порядка . . . . . . . . . . . . . . . . 9 2. 3 Свободные и связанные переменные . . . . . . . . . . . . . . . 12 2. 4 Семантика языков логики первого порядка . . . . . . . . . . 13 3 Языки логики второго порядка . . . . . . . . . . . . . . . . . . . . . 18 4 Логические языки с равенством . . . . . . . . . . . . . . . . . . . . . 19 5 Арифметика Пеано . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6 Элементы теории доказательств . . . . . . . . . . . . . . . . . . . . . 30 6. 1 Формальные cистемы . . . . . . . . . . . . . . . . . . . . . . . 30 6. 2 Естественная дедукция . . . . . . . . . . . . . . . . . . . . . . 32 6. 3 Подстановки в термах и формулах . . . . . . . . . . . . . . . 36 6. 4 Корректность и полнота естественной дедукции . . . . . . . . 40 7 Основы теории моделей . . . . . . . . . . . . . . . . . . . . . . . . . . 48 8 Сравнение языков логики разных порядков . . . . . . . . . . . . . . 53 9 Формальная теория множеств . . . . . . . . . . . . . . . . . . . . . . 57 9. 1 Аксиоматика Цермело-Френкеля. Основные аксиомы . . . . . 59 9. 2 Отношение порядка . . . . . . . . . . . . . . . . . . . . . . . . 65 9. 3 Аксиома регулярности . . . . . . . . . . . . . . . . . . . . . . 68 9. 4 Аксиома бесконечности . . . . . . . . . . . . . . . . . . . . . . 69 9. 5 Ординалы и стандартная модель арифметики . . . . . . . . . 71 9. 6 Аксиома выбора . . . . . . . . . . . . . . . . . . . . . . . . . . 79 9. 7 Теория множеств и основания математики . . . . . . . . . . . 80 4 Введение 1 Введение Формальная логика.