Geum.ru

Программы и учебный план отделения теоретической и прикладной лингвистики Издательство Московского университета 2009

Вид материалаДокументы
Подобный материал:
1   ...   43   44   45   46   47   48   49   50   ...   55

2. Логика высказываний.


2.1. Язык логики высказываний.

2.1.1. Логические связки и таблицы истинности. Приведение формул к дизъюнктивной и конъюнктивной нормальным формам. Булевы функции. Полные системы булевых функций.

2.1.2. Теорема Поста. Полиномы Жегалкина.

2.2. Гильбертовский вариант исчисления для логики высказываний. Алфавит, формулы, схемы аксиом и правила вывода исчисления высказываний. Вывод, выводимая формула. Семантическая корректность исчисления высказываний. Вывод из гипотез. Теорема о дедукции для исчисления высказываний. Теорема о семантической полноте исчисления высказываний.

2.3. Генценовский вариант исчисления для логики высказываний. Понятие секвенциального вывода. Эквивалентность гильбертовского и генценовского вариантов исчисления высказываний. Теорема об устранении сечения. Алгоритм поиска вывода в исчислении высказываний.

3. Логика первого порядка.


3.1. Язык первого порядка. Понятие переменной, предиката, квантора. Сигнатура языка первого порядка, терм, формула. Применение языков первого порядка для описания фрагментов естественных языков. Примеры языков первого порядка: языки теории полей, групп, частичного упорядочения, язык арифметики.

3.2. Семантика языков первого порядка.

3.2.1. Интерпретация языка первого порядка. Выполнимые формулы, общезначимые формулы. Равносильность формул языка первого порядка. Основные равносильности.

3.2.2. Предваренные формулы. Приведение формулы к предваренной форме.

3.3. Исчисление предикатов.

3.3.1. Схемы аксиом и правила вывода исчисления предикатов. Вывод из гипотез в исчислении предикатов. Теорема о дедукции для исчисления предикатов. Теорема о корректности исчисления предикатов.

3.3.2. Теорема Гёделя о полноте исчисления предикатов. Невозможность аксиоматизации предиката равенства в языке первого порядка. Нормальные модели. Исчисление предикатов с равенством, его корректность и полнота относительно нормальных моделей.

3.3.3. Неразрешимость исчисления предикатов.

3.4. Теории первого порядка.

3.4.1. Примеры теорий первого порядка: теория равенства, теория плотного линейного порядка, теория групп, теория полей, арифметика Пеано.

3.4.2. Теорема Гёделя о полноте для теорий первого порядка. Теорема Лёвенгейма — Скулема. Теорема компактности для языков первого порядка.

3.4.3. Невозможность аксиоматизации свойства конечности в языке первого порядка. Существование счетных нестандартных моделей арифметики.

4. Логика второго порядка.


4.1. Логика второго порядка, основные отличия ее от логики первого порядка. Определение предиката равенства. Формула, выражающая конечность. Аксиоматизация арифметики. Неперечислимость логики второго порядка.

5. Неклассические логики.


5.1.1. Интуиционистская логика высказываний. Конструктивное понимание логических связок, семантика Крипке.

5.1.2. Аксиомы интуиционистского исчисления высказываний. Теорема о корректности и полноте интуиционистского исчисления высказываний относительно семантики Крипке.

5.1.3. Доказательство невыводимости законов исключенного третьего и снятия двойного отрицания в интуиционистском исчислении высказываний. Свойство дизъюнктивности для интуиционистской логики. Невозможность задания интуиционистских связок истинностными таблицами с конечным числом значений.

5.2. Многозначная логика.

5.3. Модальная логика.

5.3.1. Язык модальной логики. Примеры модальностей в естественном языке. Системы аксиом для логик K, K4, S4, S5, GL, Grz. Семантика Крипке для модального языка.

5.3.2. Классы шкал Крипке, соответствующие основным аксиомам логик K, K4, S4, S5, Grz. Полнота K, K4, S4, S5, Grz относительно семантики Крипке. Вложение интуиционистской логики высказываний в S4.

5.4. Временная логика. Временные операторы, языки временных логик. Логика данной шкалы времени. Примеры временных логик: логики линейного времени, логики ветвящегося времени. Перевод формул языка пропозициональной временной логики на языки классической логики первого и второго порядка. Пример неэлементарной временной логики. Разрешимость линейных временных логик. Временные логики и верификация программ.

литература

Обязательная литература


Булос Дж., Джеффри Р. Вычислимость и логика. М., 1994. [С. 12–55, 131–152, 167–180, 253–274.]

Лавров И. А, Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., 1995. [С. 50–107, 124–147.]

Мендельсон Э. Введение в математическую логику. М., 1984. [С. 19–81, 86–102.]

Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М., 1972. [С. 11–68, 81–110.]

Столл Р. Р. Множества, логика, аксиоматические теории. М., 1968. [С. 72–191.]

Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., 1991. [С. 17–90, 96–98, 103–133.]

Дополнительная литература


Гейтинг А. Интуиционизм. М., 1965.

Катленд Н. Вычислимость: Введение в теорию рекурсивных функций. М., 1983. [С. 9–33, 75–114.]

Клини С. К. Математическая логика. М., 1973. [С. 11–176, 270–296.]

Линдон Р. Заметки по логике. М., 1968. [С. 11–88.]

Справочная книга по математической логике / Под ред. Дж. Барвайза. Ч. 1. Теория моделей. М., 1982. [С. 13–55.]

Успенский В. А. Лекции о вычислимых функциях. М., 1960. [С. 24–32, 53–81.]

Фейс Р. Модальная логика. М., 1974.

Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М., 1983. [С. 11–52.]

Van Benthem J. Essays in logical semantics: Studies in linguistics and philosophy. Dordrecht, 1986.

Van Dalen D. Logic and structure. Universitext. Springer-Verlag, 1994.

Gamut L. T. F. Logic, language, and meaning. Chicago, 1991.

McCawley J. D. Everything that linguists have always wanted to know about logic. Chicago, 1981.

Программу составили Л. Д. Беклемишев, Е. Ю. Ногина, В. Е. Плиско, Т. Л. Яворская