Теоретический минимум по математической логике за 3 семестр — различия между версиями
м (Новая страница: «==1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.== ==2. Д...») |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
+ | [[Категория: В разработке]] | ||
+ | |||
+ | [[Категория: Математическая логика]] | ||
+ | |||
==1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.== | ==1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.== | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | Одним из базовых понятий логики высказываний является пропозициональная переменная — переменная, значением которой может быть логическое высказывание | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Языком исчисления высказываний мы назовем язык <tex>L</tex>, порождаемый следующей грамматикой со стартовым нетерминалом <nowiki><выражение></nowiki>: | ||
+ | * <nowiki><выражение></nowiki> ::= <nowiki><импликация></nowiki> | ||
+ | * <nowiki><импликация></nowiki> ::= <nowiki><дизъюнкция></nowiki> <tex>|</tex> <nowiki><дизъюнкция></nowiki> <tex>\rightarrow</tex> <nowiki><импликация></nowiki> | ||
+ | * <nowiki><дизъюнкция></nowiki> ::= <nowiki><конъюнкция></nowiki> <tex>|</tex> <nowiki><дизъюнкция></nowiki> <tex>\vee</tex> <nowiki><конъюнкция></nowiki> | ||
+ | * <nowiki><конъюнкция></nowiki> ::= <nowiki><терм></nowiki> <tex>|</tex> <nowiki><конъюнкция></nowiki> <tex>\&</tex> <nowiki><терм></nowiki> | ||
+ | * <nowiki><терм></nowiki> ::= <nowiki><пропозициональная переменная></nowiki> <tex>|</tex> (<nowiki><выражение></nowiki>) <tex>|</tex> <tex>\neg</tex> <nowiki><терм></nowiki> | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Высказывание - любая формула, порожденная данными грамматиками. | ||
+ | }} | ||
+ | |||
+ | {{TODO | t = таблицы истинности}} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Назовем выражение общезначимым, если его оценка истинна при любой оценке входящих в него пропозициональных переменных. Запись: <tex>\models \alpha</tex>. | ||
+ | }} | ||
==2. Доказуемость. Аксиомы исчисления высказываний. Корректность исчисления высказываний.== | ==2. Доказуемость. Аксиомы исчисления высказываний. Корректность исчисления высказываний.== | ||
+ | |||
+ | {{TODO| t = Доказуемость}} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Формальная система - упорядоченная тройка <tex>\langle L, A, R \rangle</tex>, где <tex>L</tex> --- некоторый язык, <tex>A \subset L</tex> --- множество аксиом, а <tex>R \subset (L^2 \cup L^3 \cup ...)</tex> - множество правил вывода | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition= | ||
+ | Исчисление высказываний - формальная система, использующая в качестве языка язык исчисления высказываний, в качестве аксиом - следующие схемы выражений: | ||
+ | *<tex>(\phi) \rightarrow ((\psi) \rightarrow (\phi))</tex> | ||
+ | *<tex>((\phi) \rightarrow (\psi)) \rightarrow ((\phi) \rightarrow (\psi) \rightarrow (\pi)) \rightarrow ((\phi) \rightarrow (\pi))</tex> | ||
+ | *<tex>(\phi) \rightarrow (\psi) \rightarrow (\phi) \& (\psi)</tex> | ||
+ | *<tex>(\phi) \& (\psi) \rightarrow (\phi)</tex> | ||
+ | *<tex>(\phi) \& (\psi) \rightarrow (\psi)</tex> | ||
+ | *<tex>(\phi) \rightarrow (\phi) \vee (\psi)</tex> | ||
+ | *<tex>(\psi) \rightarrow (\phi) \vee (\psi)</tex> | ||
+ | *<tex>((\phi) \rightarrow (\pi)) \rightarrow ((\psi) \rightarrow (\pi)) \rightarrow ((\phi) \vee (\psi) \rightarrow (\pi))</tex> | ||
+ | *<tex>((\phi) \rightarrow (\psi)) \rightarrow ((\phi) \rightarrow \neg (\psi)) \rightarrow \neg (\phi)</tex> | ||
+ | *<tex>\neg \neg (\phi) \rightarrow (\phi)</tex> | ||
+ | , а правила вывода - все правила, порожденные согласованной заменой букв в <tex>\langle{}\phi, (\phi) \rightarrow (\psi), \psi\rangle</tex>. | ||
+ | }} | ||
+ | |||
+ | {{TODO| t = Корректность исчисления высказываний}} | ||
==3. Вывод из допущений. Теорема о дедукции.== | ==3. Вывод из допущений. Теорема о дедукции.== | ||
+ | |||
+ | {{TODO| t = вывод из допущений}} | ||
+ | |||
+ | Будем обозначать буквами <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. Теорема о полноте исчисления высказываний.== |
Текущая версия на 19:17, 4 сентября 2022
1. Исчисление высказываний, общие определения. Таблицы истинности. Общезначимость.
Определение: |
Одним из базовых понятий логики высказываний является пропозициональная переменная — переменная, значением которой может быть логическое высказывание |
Определение: |
Языком исчисления высказываний мы назовем язык
| , порождаемый следующей грамматикой со стартовым нетерминалом <выражение>:
Определение: |
Высказывание - любая формула, порожденная данными грамматиками. |
TODO: таблицы истинности
Определение: |
Назовем выражение общезначимым, если его оценка истинна при любой оценке входящих в него пропозициональных переменных. Запись: | .
2. Доказуемость. Аксиомы исчисления высказываний. Корректность исчисления высказываний.
TODO: Доказуемость
Определение: |
Формальная система - упорядоченная тройка | , где --- некоторый язык, --- множество аксиом, а - множество правил вывода
Определение: |
Исчисление высказываний - формальная система, использующая в качестве языка язык исчисления высказываний, в качестве аксиом - следующие схемы выражений:
|
TODO: Корректность исчисления высказываний
3. Вывод из допущений. Теорема о дедукции.
TODO: вывод из допущений
Будем обозначать буквами
списки формул (возможно, пустые).
Определение: |
Пусть | - некоторые список высказываний, - некоторое высказывание в исчислении . Тогда будем говорить, что выводится из (запись: ), если существует доказательство в исчислении , где - это с добавленными формулами из . Элементы называются допущениями, предположениями, или гипотезами.
Теорема: |
Пусть справедливо . Тогда справедливо |
Теорема (о дедукции): |
Пусть справедливо . Тогда справедливо . |