Квантификация предикатов.

Навешивание квантора на предикат уменьшает в нем число свободных переменных и превращает его предикат от меньшего числа переменных.

Пример.

Пример.

Пример.

- высказывания, истинностное значение которых обусловлено универсумом рассмотрения М.

Примечание.

1. формулы вида х_i Pⁿ(x₁, x₂,…, х_i,…, x_n) часто называют экзистенциональной квантификацией формул Pⁿ(x₁, x₂,…, х_i,…, x_n) относительно х_i, а формулы вида х_i Pⁿ(x₁, x₂,…, х_i,…, x_n) – универсальной квантификацией формулы Pⁿ(x₁, x₂,…, х_i,…, x_n) относительно х_i.

2. Высказывание хP(х)=u, если предикат Р(х) является тождественно-истинным, а хP(х)=u, если предикат Р(х) – выполним.

3. Если предметная область М предиката конечна, то его универсальная и экзистенциональная квантификации являются соответственно обобщением конъюнкции и дизъюнкции всех формул P(а_i) (где а_i М), т.е. имеем равносильности:

4. Равносильные выражения

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

 хР(х)=хР(х), т.е. взаимовыразимость кванторов означает, что один квантор определяет сокращенную запись другим. Именно поэтому в логике предикатов первого уровня достаточно только один из кванторов.

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

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)Для любой предикатной формулы существует эквивалентная ей П.Н.Ф.