Законы алгебры предикатов

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

Законы алгебры предикатов включают:

Имя закона	Равносильные формулы
Коммутативности	∀x∀y(F(x, y))≡∀y∀x(F(x, y)) ∃x∃y(F(x, y))≡∃y∃x(F(x, y))
Дистрибутивности	∀x(F1(x))&∀x(F2(x))≡∀x(F1(x)&F2(x)) – для формул с кванторами всеобщности по одной переменной х ∃x(F1(x))∨∃x(F2(x))≡∃x(F1(x)∨F2(x)) – для формул с кванторами существования по одной переменной х
Идемпотентности	"x(F(x))∨"x(F(x))≡"x(F(x)) "x(F(x))&"x(F(x))≡"x(F(x)) $x(F(x))∨$x(F(x))≡$x(F(x)) $x(F(x))&$x(F(x))≡$x(F(x))
Исключения третьего	"x(F(x))∨¬"x(F(x))=и $x(F(x))∨¬$x(F(x))=и
Противоречия	"x(F(x))&¬"x(F(x))=л $x(F(x))&¬$x(F(x))=л
Отрицание кванторов	∀x(¬F(x))≡¬∃x(F(x)) ∀x(F(x))≡¬∃x(¬F(x)) ∃x(¬F(x))≡¬∀x(F(x)) ∃x(F(x))≡¬∀x(¬F(x))
Дополнения	¬(¬"x(F(x)))≡ "x(F(x)) ¬(¬$x(F(x)))≡ $x(F(x))

Все эквивалентные преобразования формул, по аналогии с алгеброй высказываний, основаны на правиле подстановки: если в составе формулы F есть подформула F_i и для F_i существует эквивалентная подформула F_j, то возможна подстановка формулы F_j в формулу F без нарушения ее истинности.

Однако для алгебры предикатов есть дополнительное правило: если в формуле F, содержащей свободную переменную x, выполнить всюду подстановку вместо переменной x терма[3] t, то получим формулу F(t). Такая подстановка называется правильной:

Например,

Подстановка называется неправильной, если:

1) в результате подстановки свободная переменная окажется в области действия квантора:

Здесь свободная переменная х₂ заменена связанной квантором существования переменной х₃;

2) связанная переменная будет заменена термом:

Здесь связанная квантором существования переменная х₃ заменена свободной переменной х₂.

3.2.3. Предварённая нормальная форма

Для удобства анализа сложных формул рекомендуется преобразовывать их к нормальной форме. Если в алгебре высказываний приняты две нормальные формы ДНФ и КНФ, то в алгебре предикатов – кроме ДНФ и КНФ есть предварённая нормальная форма (ПНФ), суть которой сводится к разделению формулы на две части: префикс и матрицу. Для этого все кванторы выносят влево по правилам логики предикатов, формируя префикс, а логические связки соединяют предикаты формулы, формируя матрицу. В результате будет получена формула: ℜ_x1 ℜ_x2…ℜ_xn(M), ℜ∈{∀, ∃}, где ℜ_x1 ℜ_x2…ℜ_xn – префикс, М – матрица, причем матрица в формате КНФ.

Алгоритм приведения к ПНФ:

Шаг 1: исключить в формуле всюду логические связки ↔ и →:

(F₁↔F₂)=(F₁→F₂)&(F₂→F₁)=(¬F₁∨F₂)&(¬F₂∨F₁),

(F₁→F₂)=(¬F₁∨F₂),

Шаг 2: продвинуть отрицание до элементарной формулы по правилам:

¬∀_x(F)=∃_x(¬F), ¬∃_x(F)=∀_x(¬F), ¬(F₁∨F₂)=(¬F₁&¬F₂), ¬(F₁&F₂)=(¬F₁∨¬F₂),

Шаг 3: переименовать связанные переменные по правилу: найти самое левое связанное вхождение предметной переменной, такое, что существует еще одно вхождение этой же переменной, затем сделать замену связанного вхождения на вхождение новой переменной. Операцию повторять, пока возможна замена связанных переменных,

Шаг 4: вынести кванторы новых связанных переменных влево, не нарушая их последовательности,

Шаг 5: преобразовать бескванторную матрицу к виду КНФ, т. е. М=D₁&D₂&D₃&…, где D_i=(F_i∨F_j∨F_k∨…).

Дата добавления: 2014-01-04