Теоретический минимум по математической логике за 3 семестр — различия между версиями
(→1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.) |
(→3. Вывод из допущений. Теорема о дедукции.) |
||
Строка 30: | Строка 30: | ||
==3. Вывод из допущений. Теорема о дедукции.== | ==3. Вывод из допущений. Теорема о дедукции.== | ||
+ | |||
+ | {{TODO: вывод из допущений}} | ||
+ | |||
+ | Будем обозначать буквами <tex>\Gamma, \Delta, \Sigma</tex> списки формул (возможно, пустые). | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Пусть <tex>\Gamma</tex> - некоторые список высказываний, <tex>\alpha</tex> - некоторое высказывание в исчислении <tex>\langle L, A, R \rangle</tex>. Тогда будем говорить, что <tex>\alpha</tex> '''выводится''' из <tex>\Gamma</tex> (запись: <tex>\Gamma \vdash \alpha</tex>), если существует доказательство <tex>\alpha</tex> в исчислении <tex>\langle L, A_1, R \rangle</tex>, где <tex>A_1</tex> - это <tex>A</tex> с добавленными формулами из <tex>\Gamma</tex>. Элементы <tex>\Gamma</tex> называются допущениями, предположениями, или гипотезами. | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |statement= | ||
+ | Пусть справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>. Тогда справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex> | ||
+ | }} | ||
+ | |||
+ | {{Теорема | ||
+ | |about= о дедукции | ||
+ | |statement= | ||
+ | Пусть справедливо <tex>\Gamma \cup \{\alpha\} \vdash \beta</tex>. Тогда справедливо <tex>\Gamma \vdash \alpha \rightarrow \beta</tex>. | ||
+ | }} | ||
==4. Теорема о полноте исчисления высказываний.== | ==4. Теорема о полноте исчисления высказываний.== |
Версия 00:57, 14 января 2012
Содержание
- 1 1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.
- 2 2. Доказуемость. Аксиомы исчисления высказываний. Корректность исчисления высказываний.
- 3 3. Вывод из допущений. Теорема о дедукции.
- 4 4. Теорема о полноте исчисления высказываний.
- 5 5. Исчисление предикатов. Общезначимость и выводимость.
- 6 6. Теорема о дедукции в исчислении предикатов. Корректность и полнота исчисления предикатов.
- 7 7. Натуральный вывод. Секвенциальное исчисление предикатов. Устранение сечений.
- 8 8. Интуиционизм. Интуиционистское исчисление высказываний. Модели Крипке.
- 9 9. Теории первого порядка, примеры. Структуры и модели.
- 10 10. Аксиоматика Пеано. Формальная арифметика.
- 11 11. Рекурсивные функции и отношения. Реализация операций сложения, умножения, ограниченного вычитания.
- 12 12. Выразимость отношений и преставимость функций в формальной арифметике. Представимость примитивов Z, N, U и S.
- 13 13. Бета-функция Геделя. Представимость рекурсивных функций в формальной арифметике.
- 14 14. Геделева нумерация. Выводимость и рекурсивные функции.
- 15 15. Непротиворечивость и омега-непротиворечивость. Первая теорема Геделя о неполноте арифметики.
- 16 16. Первая теорема Геделя в форме Россера. Вторая теорема Геделя о неполноте арифметики.
- 17 17. Теория множеств. Парадоксы. Аксиоматика Цермело-Френкеля (равенство множеств, конструктивные аксиомы)
- 18 18. Аксиоматика Цермело-Френкеля (аксиомы бесконечности, выбора, подстановки, фундирования).
- 19 19. Ординальные и кардинальные числа, мощность множества.
1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.
Определение: |
Одним из базовых понятий логики высказываний является пропозициональная переменная — переменная, значением которой может быть логическое высказывание |
Определение: |
Языком исчисления высказываний мы назовем язык
| , порождаемый следующей грамматикой со стартовым нетерминалом <выражение>:
Определение: |
Высказывание - любая формула, порожденная данными грамматиками. |
Шаблон:TODO: таблицы истинности
Определение: |
Назовем выражение общезначимым, если его оценка истинна при любой оценке входящих в него пропозициональных переменных. Запись: | .
2. Доказуемость. Аксиомы исчисления высказываний. Корректность исчисления высказываний.
3. Вывод из допущений. Теорема о дедукции.
Шаблон:TODO: вывод из допущений
Будем обозначать буквами
списки формул (возможно, пустые).
Определение: |
Пусть | - некоторые список высказываний, - некоторое высказывание в исчислении . Тогда будем говорить, что выводится из (запись: ), если существует доказательство в исчислении , где - это с добавленными формулами из . Элементы называются допущениями, предположениями, или гипотезами.
Теорема: |
Пусть справедливо . Тогда справедливо |
Теорема (о дедукции): |
Пусть справедливо . Тогда справедливо . |