1.1.6. Равносильные формулы

Две формулы A{Xi,X2, ,Х„) и B{Xi,X2,Х) называются равносильными, если их значения совпадают при любых значениях, входящих в них переменных Xi, Х2,Х Для равносильных формул используется обозначение Л = В.

В логике выделяют следующие равносильные формулы:

(1.1)

и дополнительно к этим формулам еще две

В) = {~ЛУВ) В) = -{Лк-В).

(1.2)

1.1.7. Алгебра Буля

Представим теперь теорию, которая имеет переменные, формулы, построенные из атомарных формул (переменных) с помощью трех операций П,и,~ - ана)Югов логических связок &,V,~i и аналогов 1,0 двух истинностных значений T, L. Если формулы (1.1) при замене в них &, V, ~1, Т, -L на П, U, ~, 1,0 остаются справедливыми, то мы имеем новую абстрактную алгебру, называемую алгеброй Буля.

Таким образом, алгебра высказываний - это пример алгебры Буля, обязанной своим происхождением Jюгикe Аристотеля.

Алгебра высказываний - это логическая булева алгебра. Существуют и не логические булевы алгебры. Примером является теория множеств Кантора [4]. Переменные - это подмножества множества X. Роль операций П,и,~ играют пересечение П, объединение U и дополнение \ (до X), а вместо 0,1 надо взять пустое множество 0 и само X.

1.1.8. Истинные и общезначимые формулы

Формула A{Xi,...,X„) называется истинной (выполнимой), если существует набор значений переменных Хю,Хо такой, что A{Xio,Хпо) = Т.

Формула A{Xi, ...,Хп) называется общезначимой, если при любом наборе переменных она истинна. Для общезначимой формулы используется символическая запись

1.1.9. Проблема разрешимости

Пусть дана произвольная формула A{Xi,Х). Можно ли как-то проверить, что она является общезначимой? Если существует такой способ (алгоритм), позволяющий в конечное число шагов убедиться в этом, то говорят, что проблема проверки обхдезначимости формул алгебры высказываний разрешима.

Теорема 1.3. Проблема разрешимости в алгебре высказываний имеет положительное решение.

Доказательство.

Рассматривая набор переменных {X-i ,Х) на множестве { L, Т}, имеем 2" возможных комбинаций. Для каждой комбинации

легко вычислить истинностное значение формулы А. Это можно сделать, написав программу для компьютера. Найдя все значения формулы, мы узнаем всегда ли она истинна. Если «да», то формула А общезначима.

Теорема 1.3 доказана.

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

1.1.10. Логическое следствие

Пусть даны формулы Ai,...,Am,B. Формула В является логиче-crcujH следствием формул Ai,...,Am, если, придавая значения переменным X-i ,Хп, от которых зависят все рассматриваемые формулы, всякий раз, когда истинны одновременно все формулы .Al,Am, истинна и формула в.

Для логического следствия используется запись

.Al, Am \= в.

Для проверки наличия логического следования достаточно построить истинностную таблицу.

Пример 1.1. Проверить, что

X, Y, (Z&X -.Y) 1= Z. (1.3)

Имеем истинностную таблицу;

Из второй строки видно, что (1.3) есть логическое следствие.

Теорема 1.4 (о дедукции. Эрбран (1930)). Если А \= В, то \={АВ).

Доказательство.

Используем таблицу истинности для связки Из уоювия А\= В вытекает, что если Л = Т, то В = Т. Но тогда \={А В), ибо случай, когда А = Т, В = исключен.

Теорема 1.4 доказана.

Следствие 1.1. .ai,...,are 1= В тогда и только тогда, когда \= (А11&...&А1Ж В) .