Приведенные и нормальные формы в логике предикатов

Рассмотрим способ упрощения формул, опирающийся на приведен­ные равно-сильности.

Формулы, в которых из логических символов имеются только сим­волы конъюнкция, дизъюнкция и отрицание, причем символ отрицания встречается над символами предикатов, будем называть приведенными.

Например, формула ( x₁)A₁⁽¹⁾)(x₁) ˅ ( x₂)А₂⁽²⁾)(x₂, х₃)- приведенная;

формула ₂ ) A₁⁽¹⁾)(x₂) → А₂⁽¹⁾)(x₁)- неприведенная.

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

Такая приведенная формула называется прuведенной формой данной формулы.

В логике высказываний были введены две нормальные формы - дизъ­юнктивная нормальная форма и конъюнктивная нормальная форма.

В логике предикатов также имеется нормальная форма, цель кото­рой – упро-щение процедуры доказательств.

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

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

Нормальная формула называется нормальной формой данной фор­мулы.

Приведем несколько формул, находящихся в нормальной форме:

( x)( y)(P(x, у) ˄ Q(y)),

( x)( y) ( → Q(y))

Алгоритм преобразования формул в нормальную форму:

1. Исключить логические связки ↔ и → c помощью формул

F ↔ G = (F → G) ˄ (G → F), F → G = ˅ G.

2. Использовать закон = F, законы де Моргана:

= ˄ , = ˅ ,

а также законы

( х) , ( х)

чтобы пронести знак отрицания внутрь формулы.

3. Переименовать связанные переменные, если это необходимо.

4. Использовать равносильные формулы логики предикатов, чтобы вынести кванторы в самое начало формулы для приведения ее к нормаль­ной форме.

Пример.

Привести формулу ( x)P(x) →( x)Q(x) к нормаль­ной форме.

Решение:

( x)P(x) →( x)Q(x) = ˅( x)Q(x) согласно п.1

˅( x)Q(x)= ( x) ˅( x)Q(x) согласно п.2

( x) ˅( x)Q(x)= ( x)( ˅Q(x)) согласно п.4

Следовательно, нормальная форма формулы ( x)P(x) →( x)Q(x) будет иметь вид ( x)( ˅Q(x)).