Предваренная нормальная форма (п.н.ф.)

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

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

Пример 7. .

Привести формулу к виду ПНФ.

1) удалить логические связки “”:

;

2) удалить логические связки “”:

;

3) применить закон :

;

4) применить закон де Моргана :

;

5) применить закон де Моргана :

6) применить закон :

;

7) переименовать связанную переменную x=z:

;

8) переименовать связанную переменную x=w:

;

9) вынести квантор w, x и y влево:

;

10) преобразовать матрицу к виду КНФ:

;

Задание7: Привести к ПНФ.

;