logo
Predmet

[Править]Логика первого порядка

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

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

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

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

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

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

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

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

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