Випереджена нормальна форма логіки предикатів

Формула логіки першого ступеня записана у випередженій нормальній формі, якщо вона має вигляд Q₁x₁Q₂x₂…Q _n x _n M, де кожне Q _i x_i (i=1,2,...,n) - це або x_i, або х_i, а формула М не містить кванторів. Вираз Q₁x₁Q₂x₂…Q _n x _n називають префіксом, а М - матрицею формули, записаної у випередженій нормальній формі.

Приклад 2.10. Наступні формули записані у випередженій нормальній формі:

1) x y(P(x, y) Q(y));

2) x y( (x, y)→Q(y));

3) x y z(Q(x, y)→R(z)).

Наведемо послідовність кроків зведення довільної формули логіки першого ступеня до випередженої нормальної форми.

Крок 1. Виключити з формул логічні зв'язки "~" та "→" застосуванням правил Р~Q=(Р→Q) (Q→Р) та Р→Q= Q.

Крок 2. Внести знак заперечення всередину формули, для чого використати закони:

- подвійного заперечення  = Р;

- де Моргана = , =

- ( х Р (х))= х (х) та ( х Р(х))= х (х).

Перейменувати зв'язані змінні, якщо це потрібно.

Крок 3. Винести квантори у префікс, для чого скористатись законами 3 - 8 з підпункту 2.2.

Література

1. Капітонова Ю. В., Кривий С. Л., Летичевський О. А., Луцький Г. М., Печурін М. К. Основи дискретної математики. - К.: Наукова думка, 2002.

2. Середа В. Ю., Математична логіка в шкільному курсі математики. – К.: Радянська школа, 1984.

3. Мендельсон 3. Введение в математическую логику. - М.: Наука, 1971.

4. Новиков П. С. Элементы математической логики. - М.: Наука, 1973.

5. Столл Р. Множества. Логика. Аксиоматические теории. — М: Просвещение, 1968.

6. Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика. – В: Магнолія плюс, 2005.