ДИСКРЕТНАЯ МАТЕМАТИКА. ЛЕКЦИЯ 13

Лекция 13. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму

Предваренная нормальная форма

В исчислении высказываний существуют две нормальные формы – конъюнктивная и дизъюнктивная. В исчислении предикатов также имеется нормальная форма, называемая предваренной нормальной формой.

Определение. Формула F исчисления предикатов находится в предваренной нормальной форме тогда и только тогда, когда формула F имеет вид

(Q1x1)…(Qnxn)(M),

где каждое (Qixi), [image], есть или (" xi) или ($ xi), а M есть формула, не содержащая кванторов. (Q1x1)…(Qnxn) называется префиксом, а M - матрицей формулы F.
Для приведения формулы исчисления предикатов к предваренной нормальной форме рассмотрим ряд эквивалентностей, содержащих кванторы.
Пусть F - формула, содержащая свободную переменную x (обозначим этот факт как F[x]). Пусть G -формула, не содержащая переменную x. Пусть Q есть или " или $ . Тогда имеют место следующие эквивалентности:

(13.1)
(13.2)
(13.3)
(13.4)

Эквивалентности (13.1) и (13.2) очевидны, т.к. G не содержит x и, следовательно, может быть внесена в область действия квантора Q. Докажем эквивалентности (13.3) и (13.4). Пусть I - произвольная интерпретация с областью D . Если [image] истинна в I, то (" x)F[x] ложна в I. Это означает, что существует такой элемент e в D, что F[e] ложна, т.е. истинна в I. Следовательно, [image] истинна в I. С другой стороны, если [image] ложна в I, то (" x)F[x] истинна в I. Это означает, что F[x] истинна для каждого элемента x в D, т.е. ложна для каждого элемента x в D. Следовательно, [image] ложна в I. Т.к. и [image] всегда принимают одно и то же истинностное значение при произвольной интерпретации, то по определению [image]. Таким образом (13.3) доказано. Аналогично можно доказать и (13.4).
Предположим далее, что F[x] и H[x] - две формулы, содержащие свободную переменную x . Нетрудно доказать, что

(" x)F[x] Ù (" x)H[x] = (" x)(F[x] Ù H[x]), (13.5)
($ x)F[x] Ú ($ x)H[x] = ($ x)(F[x] Ú H[x]), (13.6)

т.е. квантор всеобщности " и квантор существования $ можно распределять по Ù и Ú соответственно.
Однако " и $ нельзя распределять по Ú и Ù соответственно, т.е.

(" x)F[x] Ú (" x)H[x] ¹ (" x)(F[x] Ú H[x]), (13.5)
($ x)F[x] Ù ($ x)H[x] ¹ ($ x)(F[x] Ù H[x]). (13.6)

В подобных случаях можно поступить следующим образом. Т.к. каждая связанная переменная в формуле может рассматриваться лишь как место для подстановки любой переменной, то каждую связанную переменную x можно переименовать в z, т.е. (" x)H[x] = (" z)H[z]. Если мы выберем переменную z, которая не встречается в F[x], то

(" x)F[x] Ú (" x)H[x] = (" x)F[x] Ú (" z) H[z] =
= (" x) (" z)(F[x] Ú H[z]) (13.7)

Аналогично

($ x)F[x] Ù ($ x)H[x] = ($ x)F[x] Ù ($ z) H[z] =
=($ x) ($ z)(F[x] Ù H[z]) (13.8)

Т.о., в общем случае имеем

(Q1x)F[x] Ú (Q2x)H[x]=(Q1x)(Q2z)(F[x] Ú H[z]), (13.9)
(Q3x)F[x] Ù (Q4x)H[x]=(Q3x)(Q4z)(F[x] Ù H[z]), (13.10)

где Q1,Q2 суть " и $ , а z не входит в F[x]. Конечно, если Q1=Q2=$ , а Q3=Q4=" , то не обязательно переименовывать переменную x. Можно напрямую использовать формулы (13.5) и (13.6).

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

Шаг1.Используем

.

Шаг 2. Используем

,

или

или

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

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

Шаг 4. Используем эквивалентности (13.1)-(13.6), (13.9),(13.10).

Пример 13.1. Привести к предваренной нормальной форме формулу (" x)P(x)® ($ x)Q(x).

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

(" x) (" y)((($ z)P(x,z) Ù P(y,z)) ® ($ u)Q(x,y,u)).