Исчисление высказываний и алгебра высказываний. Основные проблемы исчисления высказываний


Произвольную формулу F исчисления высказываний можно содержательно интерпретировать как составленное высказывание, истинность или ошибочность которого зависит от истинности элементарных высказываний, что к нему входят. Таким образом, каждой формуле F исчисления высказываний можно аналогично тому, как это было сделано в алгебре высказываний, поставить в соответствие функцию истинности f.

Возникает вопрос, как связано такое содержательное «истинносне» толкование (интерпретация) формул исчисления высказываний с их формальной выводной.

Теорема 5.5. Любая теорема исчисления высказываний ЧВ является тождественно истинным высказыванием (тавтологией).

Доведение. Тождественная истинность всех аксиом легко проверяется непосредственно построением соответствующих таблиц истинности для каждой из них (рекомендуем это сделать самостоятельно).

Следовательно, докажем, что оба правила выведения исчисления высказываний превращают тождественно истинные формулы в тождественно истинные.

Если A(p1, p2,...,pn) - тождественно истинная формула, то для произвольного набора значений a1, a2,...,an ее пропозицийних переменных A(a1, a2,...,an) является истинной. Следовательно, тождественно истинной будет и любая формула A, что получается из формулы A путем подстановки вместо пропозицийних переменных p1, p2,...,pn произвольных формул B1, B2,....Bn, поскольку последние могут приобретать лишь значения 0 или 1.

Докажем, что когда формулы A и AB является тождественно истинными, тогда формула B, которую мы достаем из них по правилу вывода, также является тождественно истинной. Допустим противоположное: пусть B не является тождественно истинной формулой, то есть существует набор значений ее переменных, на котором она приобретает значение 0. Тогда подставим этот набор в формулу AB, поскольку A является тавтологией, то достанем выражение 10, значением которого является 0. Последнее противоречит предположению о тождественной истинности формулы AB.

Таким образом, мы убедились в том, что все аксиомы исчисления высказываний ЧВ являются тождественно истинными формулами алгебры высказываний, а применение обоих правил выведения (подстановки и вывода) к тождественно истинным формулам опять приводит к тождественно истинным формулам. Следовательно, все выводные формулы (теоремы) исчисления высказываний являются тождественно истинными формулами алгебры высказываний.

Справедливой является и обратная теорема, которую подадим без доведения.

Теорема 5.6. Любая тождественно истинная формула алгебры высказываний является теоремой исчисления высказываний ЧВ.

Две последних теоремы позволяют решить три важных проблемы исчисления высказываний : проблему несуперечности, проблему полноты и проблему развязности. Рассмотрим их последовательно.

1. Проблема несуперечности.

Для каждой формальной теории кардинальным является вопрос несуперечности. Действительно, такая теория строится последовательным присоединениям новых теорем, которые формально выводят из аксиом с помощью правил выведения. Следовательно, нет ни одной гарантии, что в этом процессе мы не дойдем до противоречия. Iнакше говоря, возникает вопрос, или при постепенном нагромождении теорем формальной теории (исчисление) не случится так, что одна из теорем будет противоречить другим. Именно так возникает проблема несуперечности исчисления.

Исчисление является непротиворечивым, если невозможно одновременно вывести из аксиом исчисления как формулу A, так и ее отрицание A.

Следствие 5.1. Исчисление высказываний ЧВ является непротиворечивой формальной теорией.

Действительно, если формула A выводная в исчислении высказываний, то формула A не может быть выводной, потому что за теоремой 5.5 формула A является тождественно истинной в алгебре высказываний, а формула A - тождественно ошибочной. Следовательно, A не может быть теоремой исчисления высказываний ЧВ.

2. Проблема полноты.





Вернуться назад