1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Категория: В разработке]]
[[Категория: Математическая логика]]
==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. Доказуемость. Аксиомы исчисления высказываний. Корректность исчисления высказываний.==
{{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. Вывод из допущений. Теорема о дедукции.==
{{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. Теорема о полноте исчисления высказываний.==
