Исчисление высказываний как формальная система

Исчисление высказываний (ИВ)представляем в виде формальной системы. Алфавит ИВ образуют буквы латинского алфавита с числовыми индексами или без них (эти буквы называются высказывательными переменными или атомами), символы логических связок (отрицание), & (конъюнкция), (дизъюнкция), (импликация), атакже левая иправая скобки.

Правила образования ППФ:

1) все атомы являются ППФ;

2) если А и В – ППФ, то (A), (А & В), (А В), (А В)– также ППФ.

3) других ППФ не существует.

Скобки, расположение которых в ППФ определяется однозначно, мы иногда будем опускать.

Система аксиом ИВ (введена П. С. Новиковым):

1) ,

2) ,

3) ,

4) ,

5) ,

6) ,

7) ,

8) ,

9) ,

10) ,

11) .

В ИВ имеются два правила вывода - подстановка и modus ропепs (дедуктивного вывода).

Правило подстановки применяется к имеющейся ППФ А, содержащей некоторый атом X. Одновременной заменой всех вхождений этого атома в А (X) на произвольную ППФ В мы получим формулу A (В), которуюименуем результатом подстановки в ППФ А (X) формулы В.

Если А (X) – теорема ИВ, то A (В) – тоже теорема ИВ.

Приведем пример. Подставив в аксиому 8 ИВ формулу (С & D) вместо атома С, получаем следующую теорему ИВ:

.

Правило дедуктивного вывода (modus ponens) применяется к имеющейся паре ППФ А и А В; результатом применения данного правила является ППФ В.

Если A и А В являются теоремами ИВ, то В - также теорема ИВ.

Будем трактовать символы , &, , как функции алгебры логики. Тогда каждая ППФ, сконструированная из атомов X ₁, X ₂, …, X_n,на любых наборах их логических значений (0 или 1, ложь или истина) обращается в ложь или истину.

Правильно построенная формула, которая является истинной на всех наборах логических значений ее переменных, именуется общезначимой.

Правильно построенную формулу А именуем невыполнимой (противоречивой), если ППФ А является общезначимой.

Можно проверить, что все аксиомыИВ являются общезначимыми ИПФ. Оба правила вывода сохраняют общезначимость. Получаем справедливость следующего утверждения:

"Каждая теорема ИВ является общезначимой ППФ".

Полноту приведенной системы аксиом утверждает следующий факт:

"Каждая общезначимая ППФ является теоремой ИВ".

Система аксиом П.С.Новикова обладает также свойствами непротиворечивости инезависимости.

Далее подтермином "формула" понимаем ППФ.

Две формулы ИВ называются эквивалентными, если на любом наборе логических значений составляющих их атомов они одновременно обращаются в истину или одновременно обращаются в ложь. Эквивалентность обозначаем символом =.

Легко убедиться, что

(А В)=( А В);

данный факт далее будет играть принципиальное значение.

Литерами будем называть атомы и их отрицания. Таким образом, формула ( А В) составлена из двух литер, А и B.

Формула В есть конъюнктивная нормальная форма (КНФ), если В имеет вид

В ₁ & В ₂ &...& В_m,

где каждая из формул B_i, i= 1 ,…,m, есть дизъюнкция литер. В качестве примера КНФ приведем формулу:

( X ₁ X ₃ X ₄)& (X ₁ X ₂)& (X₂ X ₃ X ₅).

Аналогично, формула В есть дизъюнктивная нормальная форма (ДНФ), если В имеет вид

В ₁ В ₂ ... В_m,

где каждая из формул B _i, i= 1 ,…,m, есть конъюнкция литер. В качестве примера ДНФ приведем формулу:

( X ₁ & X ₃ & X ₄) (X ₁ & X ₂) (X ₂ & X ₃ & X ₅).

В дальнейшем дизъюнкцию литер будем называть дизъюнктом, а конъюнкцию – конъюнктом.

Любая формула ИВ может быть преобразована в эквивалентную ей ДНФ или КНФ с помощью следующего алгоритма.

Шаг 1. А В = А В,

А~В = (А В)& ( А В)

выражение операций импликации и эквиваленции через операции конъюнкции и дизъюнкции.

Шаг 2. А=A,

(А В) = А & В,

(А & В) = А В

продвижение отрицания до атома.

Шаг 3. А (В & C) = (А В)& (А C) (для КНФ),

А & (В C) = (А & В) (А & C) (для ДНФ).

Пример 1. Требуется преобразовать в КНФформулу

Ф=[( А В)& (C &(D А))].

Решение. Ф=[( А В)& (C &(D А))]=(А В)& ( C ( D А))=

=(А В)& ( C D)& ( C А).

Дата добавления: 2015-06-27