Изменения
→Вычисление значений высказываний
==Вычисление значений высказываний==
Зададим некоторое множество истинностных значений $V$ и функции
оценки $f_\&, f_\vee, f_\to: V \times V \to V$, и $f_\neg: V \to V$,
по функции на каждую из связок и на отрицание. Также зададим ''оценку''
переменных, функцию, сопоставляющую множеству переменных $P$ некоторого
высказывания $\alpha$ --- функцию $f_P: P \to V$.</wikitex>
{{Определение
|definition=Если дано некоторое высказывание $\alpha$, в котором используются пропозициональные
переменные $v_1 \dots v_n$, то ''оценку'' данного высказывания $|\left\vert\alpha|\right\vert$ мы определим
следующим рекурсивным образом.
* пропозициональная переменная $v_i$: $f_P (v_i)$
* конъюнкция выражений $\alpha$ и $\beta$: $f_\& (|\left\vert\alpha|\right\vert,|\left\vert\beta|\right\vert)$* дизъюнкция выражений $\alpha$ и $\beta$: $f_\vee (|\left\vert\alpha|\right\vert,|\left\vert\beta|\right\vert)$* импликация выражений $\alpha$ и $\beta$: $f_\to (|\left\vert\alpha|\right\vert,|\left\vert\beta|\right\vert)$* отрицание выражения $\alpha$: $f_\neg (|\left\vert\alpha|\right\vert)$
* во всех остальных случаях оценка выражения равна оценке потомка в дереве.
}}
Любое выражение оценивается по этому определению
|proof=
различных фактов про выражения. Данное доказательство подходит для первого
варианта грамматики.
* термом --- при этом это не пропозициональная переменная, так как длина строки больше 1. Значит, это либо выражение в скобках --- тогда все доказано по предположению индукции, поскольку длина выражения в скобках --- $n-1$, либо отрицание. Тогда применение функции $f_\neg$ к оценке строки длины $n$ даст оценку выражения.
* импликацией, конъюнкцией или дизъюнкцией, при этом примененный вариант правила добавляет новые терминальные символы в строку. Значит, здесь дерево разбора разделит строку на две, причем длины строго меньшей, чем $n$. В этом случае очевидно, что значение выражения будет вычислено.
* выражением, импликацией, конъюнкцией или дизъюнкцией, при этом примененный вариант правила не добавляет новых терминальных символов. В этом случае, спустившись (возможно, несколько раз) вниз по дереву мы дойдем либо до терма, либо до вариантов правил для импликации, конъюнкции или дизъюнкции, добавляющих терминальные символы, и окажемся в условиях предыдущих пунктов.</wikitex>
}}
