Изменения
minor fix wikitex
[[Математическая логика | На главную <<]][[Лекция 3 | >>]]
[[Категория: Математическая логика]]
==Язык исчисления высказываний==
===Определения===
{{Определение
|definition=
Одним из базовых понятий логики высказываний является пропозициональная переменная — переменная, значением которой может быть логическое высказывание
}}
{{Определение
|definition=
<nowiki><пропозициональная переменная></nowiki> формально не определяется. Договоримся, что это - буква латинского алфавита (возможно, с нижним индексом).
}}
===Расстановка скобок===
Так построенная грамматика предписывает определенный способ расстановки
{{Определение
|definition=<wikitex>Если дано некоторое высказывание $\alpha$, в котором используются пропозициональные
переменные $v_1 \dots v_n$, то ''оценку'' данного высказывания $|\alpha|$ мы определим
следующим рекурсивным образом.
* импликация выражений $\alpha$ и $\beta$: $f_\to (|\alpha|,|\beta|)$
* отрицание выражения $\alpha$: $f_\neg (|\alpha|)$
* во всех остальных случаях оценка выражения равна оценке потомка в дереве.</wikitex>
}}
{{Определение
|id=valid
|definition=
Назовем выражение общезначимым, если его оценка истинна при любой оценке входящих в него пропозициональных переменных. Запись: <tex>\models \alpha</tex>.
{{Определение
|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><\langle L, A, R>\rangle</tex> - конечная последовательность выражений <tex>\alpha_1, ..., \alpha_n</tex> из <tex>L</tex>, такая, что <tex>\forall i \le n</tex> либо <tex>\alpha_i \in A</tex>, либо <tex>\alpha_i</tex> получается с использованием правил вывода из предыдущих выражений.
}}
Высказывание <tex>\alpha</tex> называется доказуемым, если существует доказательство <tex>\alpha_1, ..., \alpha_k</tex>, в котором <tex>\alpha_k == \alpha</tex>. Запись: <tex>\vdash \alpha</tex>.
}}
Расширим грамматику из предыдущего раздела:
* <nowiki><выражение></nowiki> ::= <nowiki><импликация></nowiki><tex>| \psi | \phi | \pi</tex>
* <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>\psi, \phi, \pi</tex> ''схемами выражений''. Если вместо ''всех'' данных букв подставить корректные выражения из грамматики, получим корректное выражение. При этом, одинаковые буквы должны меняться на одинаковые выражения.
{{Определение
|definition=
Все выражения, полученные из схемы путем подстановки выражений вместо букв <tex>\psi, \phi, \pi</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>.
}}
[[Категория: Математическая логика]]
