Математична логіка (стр. 8 из 8)

Аналогічно, ¬(

хР(х))=¬(Р(а₁) Р(а₂) ... Р(а_n))= (а₁) (а₂) ... (а), що еквівалентне х (х).

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

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

x_i, або х_i, а формула М не містить кванторів. Вираз Q₁x₁Q₂x₂…Q_nx_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.