Исчисление высказываний — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Язык исчисления высказываний== ===Определения=== {{Определение |definition= Языком исчисления вы...»)
 
Строка 34: Строка 34:
 
|definition=
 
|definition=
 
''Высказывание'' - любая формула, порожденная данными грамматиками.
 
''Высказывание'' - любая формула, порожденная данными грамматиками.
 +
}}
 +
 +
==Вычисление значений высказываний==
 +
<wikitex>Теперь попробуем научиться вычислять значение высказываний.
 +
Зададим некоторое множество истинностных значений $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=<wikitex>Если дано некоторое высказывание $\alpha$, в котором используются пропозициональные
 +
переменные $v_1 \dots v_n$, то ''оценку'' данного высказывания $|\alpha|$ мы определим
 +
следующим рекурсивным образом.
 +
 +
Возьмем дерево разбора высказывания, и возьмем его корень. В зависимости от правила, по которому получен корень, результатом оценки мы назовем:
 +
 +
* пропозициональная переменная $v_i$: $f_P (v_i)$
 +
* конъюнкция выражений $\alpha$ и $\beta$: $f_\& (|\alpha|,|\beta|)$
 +
* дизъюнкция выражений $\alpha$ и $\beta$: $f_\vee (|\alpha|,|\beta|)$
 +
* импликация выражений $\alpha$ и $\beta$: $f_\to (|\alpha|,|\beta|)$
 +
* отрицание выражения $\alpha$: $f_\neg (|\alpha|)$
 +
* во всех остальных случаях оценка выражения равна оценке потомка в дереве.</wikitex>
 +
}}
 +
 +
{{Теорема
 +
|statement=
 +
Любое выражение оценивается по этому определению
 +
|proof=
 +
<wikitex>Докажем индукцией по длине формулы, $n$; это традиционный способ доказательств
 +
различных фактов про выражения. Данное доказательство подходит для первого
 +
варианта грамматики.
 +
 +
База: $n=1$. Анализ грамматики показывает, что такая строка может состоять только из имени пропозициональной переменной. Очевидно, что указанный способ оценки позволяет такую строку оценить всегда.
 +
 +
Переход: пусть $n\ge 1$ и для $n$ все доказано. Рассмотрим строку длины $n+1$.
 +
В дереве разбора данной строки есть некоторый корень, рассмотрим его. Он может быть:
 +
* термом --- при этом это не пропозициональная переменная, так как длина строки больше 1. Значит, это либо выражение в скобках --- тогда все доказано по предположению индукции, поскольку длина выражения в скобках --- $n-1$, либо отрицание. Тогда применение функции $f_\neg$ к оценке строки длины $n$ даст оценку выражения.
 +
* импликацией, конъюнкцией или дизъюнкцией, при этом примененный вариант правила добавляет новые терминальные символы в строку. Значит, здесь дерево разбора разделит строку на две, причем длины строго меньшей, чем $n$. В этом случае очевидно, что значение выражения будет вычислено.
 +
* выражением, импликацией, конъюнкцией или дизъюнкцией, при этом примененный вариант правила не добавляет новых терминальных символов. В этом случае, спустившись (возможно, несколько раз) вниз по дереву мы дойдем либо до терма, либо до вариантов правил для импликации, конъюнкции или дизъюнкции, добавляющих терминальные символы, и окажемся в условиях предыдущих пунктов.</wikitex>
 
}}
 
}}

Версия 19:35, 12 января 2012

Язык исчисления высказываний

Определения

Определение:
Языком исчисления высказываний мы назовем язык [math]L[/math], порождаемый следующей грамматикой со стартовым нетерминалом <выражение>:
  • <выражение> ::= <импликация>
  • <импликация> ::= <дизъюнкция> [math]|[/math] <дизъюнкция> [math]\rightarrow[/math] <импликация>
  • <дизъюнкция> ::= <конъюнкция> [math]|[/math] <дизъюнкция> [math]\vee[/math] <конъюнкция>
  • <конъюнкция> ::= <терм> [math]|[/math] <конъюнкция> [math]\&[/math] <терм>
  • <терм> ::= <пропозициональная переменная> [math]|[/math] (<выражение>) [math]|[/math] [math]\neg[/math] <терм>


Определение:
<пропозициональная переменная> формально не определяется. Договоримся, что это - буква латинского алфавита (возможно, с нижним индексом).

Расстановка скобок

Так построенная грамматика предписывает определенный способ расстановки опущенных скобок, при этом скобки у конъюнкции и дизъюнкции расставляются слева направо, а у импликации --- справа налево (это соответствует традиционному чтению), так что выражение [math]A \rightarrow B\&C\&D \rightarrow E[/math] следует понимать как [math]A \rightarrow (((B\&C)\&D) \rightarrow E)[/math]. Все выражения, которые отличаются только наличием дополнительных незначащих скобок (не изменяющих порядок операций), мы будем считать одинаковыми.

Иногда полезно ограничивать свободу расстановки скобок:

  • <выражение> ::= <импликация>
  • <импликация> ::= <дизъюнкция> [math]|[/math] (<дизъюнкция> [math]\rightarrow[/math] <импликация>)
  • <дизъюнкция> ::= <конъюнкция> [math]|[/math] (<дизъюнкция> [math]\vee[/math] <конъюнкция>)
  • <конъюнкция> ::= <терм> [math]|[/math] (<конъюнкция> [math]\&[/math] <терм>)
  • <терм> ::= <пропозициональная переменная> [math]|[/math] (<выражение>) [math]|[/math] [math]\neg[/math] <терм>


Определение:
Высказывание - любая формула, порожденная данными грамматиками.


Вычисление значений высказываний

<wikitex>Теперь попробуем научиться вычислять значение высказываний. Зададим некоторое множество истинностных значений $V$ и функции оценки $f_\&, f_\vee, f_\to: V \times V \to V$, и $f_\neg: V \to V$, по функции на каждую из связок и на отрицание. Также зададим оценку переменных, функцию, сопоставляющую множеству переменных $P$ некоторого высказывания $\alpha$ --- функцию $f_P: P \to V$.</wikitex>


Определение:
<wikitex>Если дано некоторое высказывание $\alpha$, в котором используются пропозициональные переменные $v_1 \dots v_n$, то оценку данного высказывания $


Теорема:
Любое выражение оценивается по этому определению
Доказательство:
[math]\triangleright[/math]

<wikitex>Докажем индукцией по длине формулы, $n$; это традиционный способ доказательств различных фактов про выражения. Данное доказательство подходит для первого варианта грамматики.

База: $n=1$. Анализ грамматики показывает, что такая строка может состоять только из имени пропозициональной переменной. Очевидно, что указанный способ оценки позволяет такую строку оценить всегда.

Переход: пусть $n\ge 1$ и для $n$ все доказано. Рассмотрим строку длины $n+1$. В дереве разбора данной строки есть некоторый корень, рассмотрим его. Он может быть:

  • термом --- при этом это не пропозициональная переменная, так как длина строки больше 1. Значит, это либо выражение в скобках --- тогда все доказано по предположению индукции, поскольку длина выражения в скобках --- $n-1$, либо отрицание. Тогда применение функции $f_\neg$ к оценке строки длины $n$ даст оценку выражения.
  • импликацией, конъюнкцией или дизъюнкцией, при этом примененный вариант правила добавляет новые терминальные символы в строку. Значит, здесь дерево разбора разделит строку на две, причем длины строго меньшей, чем $n$. В этом случае очевидно, что значение выражения будет вычислено.
  • выражением, импликацией, конъюнкцией или дизъюнкцией, при этом примененный вариант правила не добавляет новых терминальных символов. В этом случае, спустившись (возможно, несколько раз) вниз по дереву мы дойдем либо до терма, либо до вариантов правил для импликации, конъюнкции или дизъюнкции, добавляющих терминальные символы, и окажемся в условиях предыдущих пунктов.</wikitex>
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Исчисление_высказываний&oldid=16291»