Эквивалентные преобразования кванторных формул.

1. Закон отрицания кванторов:

хР(х)  хР(х),

 хР(х)  хР(х).

Эти эквивалентности являются обобщением законов де-Моргана.

Пример. Пусть Р – сдал экзамен, а М – студент учебной группы. Тогда высказывание хР(х) ( “не все студенты группы сдали экзамен”) эквивалентно высказыванию хР(х) (“существуют студенты группы, которые не сдали экзамен”)

2) Законы коммутативности одноименных кванторов.

ху Р(х, у)  ухР(х,у),

ху Р(х, у)  ух Р(х, у).

Однако, для разноименных кванторов действительна импликация:

ху Р(х, у)  у х Р(х, у).

3) Законы пронесения и вынесения кванторов (эквивалентности предваренных приведенных формул):

• х(Р(х)Z)хP(x) )ZZхР(х),

х(Р(х)Z)хP(x) )ZZхР(х),

х(Р(х)Z)хP(x) )ZZхР(х),

х(Р(х)Z)хP(x) )ZZхР(х).

Пример.х(F(x)Q(y))H(x)Q(y))х(Q(y)(H(x)F(x))Q(y)х(H(x) )F(x))

• х(P₁(x)P₂(x))хP₁(x)хP₂(x),

х(P₁(x)P₂(x))хP₁(x)хP₂(x),

Это т.н. законы дистрибутивности квантора  относительно операции  и  относительно .

Для квантора  относительно  и  относительно  действительны соотношения (верно лишь в одну сторону):

(хP₁(x)хP₂(x))  х(P₁(x)P₂(x)),

х(P₁(x)P₂(x))  хP₁(x)х P₂(x).

Примечание.

1) Предикатная формула, построенная только с привлечением булевых логических операций  и кванторов ,  так, что логическая операция  (обращение) встречается лишь перед символами предикатов, называются приведенной формой. Так, х P₁(x)х P₂(x, у) – приведенная формула, а формулы хР(х)хQ(x,y),

хР(х)хQ(x,y) – не приведенные формулы (т.к. “”

2. Предикатная формула вида >|₁x >|₂x…>|_nxF, где >|_i, где F – бескванторная формула, называется предваренной (пренексной) нормальной формой – П.Н.Ф.

Так ху( P₁(x)P₂(x, у)) – приведенная П.Н.Ф., а ху( P₁(x)P₂(x, у)) – П.Н.Ф., но не предваренная формуле.

4)Законы переименования связанных переменных:

хР(х) уР(у),

хР(х) уР(у).

Эти равносильности означают, что переименование связанных переменных не меняет истинности высказываний.

Утверждения. 1) Для любой предикатной формулы существует равносильная ей приведенная форма.

2)Для любой предикатной формулы существует эквивалентная ей П.Н.Ф.