2.6.4. Приведенная форма и предваренная нормальная форма предиката

Определение. Формула логики предикатов, в которой из операций логики высказываний имеются только конъюнкция, дизъюнкция и отрицание, причем отрицание относится только к элементарным предикатам, называется Приведенной формой предиката.

Теорема 1. Для всякого предиката существует равносильная ему приведенная нормальная форма.

Доказательство. Действительно, все операции в данной предикатной формуле можно выразить через конъюнкцию, дизъюнкцию и отрицание (например, в виде ДНФ). Если после этого некоторые отрицания будут относиться к частям формулы, содержащим кванторы, то отрицания можно “снять” с кванторов согласно равносильностям 1 и 2, а “снять” отрицания с конъюнкций и дизъюнкций можно, следуя законам де Моргана. После всех описанных преобразований предикат, очевидно, будет представлен в приведенной форме.

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

Теорема 2. Для всякого предиката существует равносильная ему предваренная нормальная форма.

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

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

1) Беспорядок имеет вид: "X Р или $Х Р, где Р – не зависит от Х. Тогда "Х или $Х можно просто отбросить, поскольку "ХР º Р и $ХР º Р.

2) Беспорядок имеет вид: "ХР(Х) или $ХР(Х). Если переменная Х еще встречается в формуле, то предварительно сделав замену согласно формулам

"XP(X) º "TP(T), $XP(X) º $TP(T),

Где T – переменная, не встречающаяся в формуле, беспорядок представляется в виде правой части одной из формул 10 – 13. Применяя эти формулы (т. е., заменяя правые части на левые), беспорядок устраняется.

Проделав такие преобразования конечное число раз, все беспорядки будут ликвидированы, что и требовалось доказать.

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

< Предыдущая		Следующая >