Исчисление высказываний как формальная система
Обновлено: 04.11.2024
Так построенная грамматика предписывает определенный способ расстановки опущенных скобок, при этом скобки у конъюнкции и дизъюнкции расставляются слева направо, а у импликации --- справа налево (это соответствует традиционному чтению), так что выражение [math]A \rightarrow B\&C\&D \rightarrow E[/math] следует понимать как [math]A \rightarrow (((B\&C)\&D) \rightarrow E)[/math] . Все выражения, которые отличаются только наличием дополнительных незначащих скобок (не изменяющих порядок операций), мы будем считать одинаковыми.
Иногда полезно ограничивать свободу расстановки скобок:
Попробуем научиться вычислять значение высказываний. Зададим некоторое множество истинностных значений $V$ и функции оценки $f_\&, f_\vee, f_\to: V \times V \to V$, и $f_\neg: V \to V$, по функции на каждую из связок и на отрицание. Также зададим оценку переменных, функцию, сопоставляющую множеству переменных $P$ некоторого высказывания $\alpha$ --- функцию $f_P: P \to V$.
переменные $v_1 \dots v_n$, то оценку данного высказывания $\left\vert\alpha\right\vert$ мы определим следующим рекурсивным образом.
Возьмем дерево разбора высказывания, и возьмем его корень. В зависимости от правила, по которому получен корень, результатом оценки мы назовем:
Любое выражение оценивается по этому определениюДокажем индукцией по длине формулы, $n$; это традиционный способ доказательств различных фактов про выражения. Данное доказательство подходит для первого варианта грамматики.
База: $n=1$. Анализ грамматики показывает, что такая строка может состоять только из имени пропозициональной переменной. Очевидно, что указанный способ оценки позволяет такую строку оценить всегда.
Переход: пусть $n\ge 1$ и для $n$ все доказано. Рассмотрим строку длины $n+1$. В дереве разбора данной строки есть некоторый корень, рассмотрим его. Он может быть:
Зафиксируем множество истинностных значений [math]V[/math] . Почти всюду всегда достаточно [math]V = \<[/math] И, Л [math]\>[/math] (И - истина, Л - ложь). Зафиксируем оценки для связок ( [math]\&, |, \rightarrow[/math] ) и отрицания, придав им традиционные значения. В таком случае, единственный произвол в оценке выражения связан с выбором оценки пропозициональных переменных [math]f_p[/math] .
Правило вывода (элемент [math]R[/math] ) - упорядоченная [math]n[/math] -ка выражений, где первое [math]n - 1[/math] выражение --- посылка, а последнее --- заключение правила.
Расширим грамматику из предыдущего раздела:
Назовем [math]\psi, \phi, \pi[/math] схемами выражений. Если вместо всех данных букв подставить корректные выражения из грамматики, получим корректное выражение. При этом, одинаковые буквы должны меняться на одинаковые выражения.
Читайте также: