5.8. Закони і тотожності у логіці предикатів

Колізія змінних, заміна зв'язаної змінної, комутативні і дистрибутивні властивості кванторів, закон де Моргана для кванторів

Всі закони і тотожності, які справедливі у логіці висловлень, залишаються справедливими і у логіці предикатів. Крім того, у логіці предикатів існують додаткові законі, що призначені для еквівалентного перетворення формул, що містять квантори та змінні.

Слід зауважити, що перенесення квантора на початок формули може змінити зміст предикатного висловлення. Так, наприклад, х F(x)  х G(x) не еквівалентне х (F(x)  G(x)). У загальному випадку слід перейменувати зв'язані змінні, щоб запобігти колізії— ситуації, коли у формулі одна й та ж змінна знаходиться в області дії протилежних кванторів. Наприклад, у формулі х (F(x))  х (Q(x)) змінна х одночасно знаходиться в області дії кванторів  і .

Розглянемо висловлення, що використовує предикат рівності ДОРІВНЮЄ двох чисел: х у ДОРІВНЮЄ(х + 1, у). Дане висловлення означає, що для будь-якого числа х існує число у, яке більше його на одиницю. Наведене висловлення є істинним. Однак, якщо поміняти порядок розташування кванторів на протилежний, то одержимо таке висловлення: у х ДОРІВНЮЄ(х + 1, у). Одержане висловлення означає, що існує таке число у (одне!), яке на одиницю більше будь-якого числа х. Це висловлення не відповідає попередньому і є хибним.

Для еквівалентних перетворень предикатних висловлень з кванторами необхідно використовувати наведені нижче закони. Перш ніж безпосередньо перейти до розглядання законів дій з кванторами, введемо такі позначення: .F(x) і Н(х) — одномісні предикати, Р(х, у) — двомісний предикат.

1. Заміна зв'язаної змінної:

(х) F(x) = (у) F(y);

(x) F(x) = (y) F(y).

Введення нового позначення зв'язаної змінної (тобто перейменування зв'язаної змінної) не змінює зміст формули логіки предикатів, якщо виконується така умова: ніяка вільна змінна у будь-якій частині формули не повинна після перейменування бути зв'язаною. Іншими словами, для нового позначення зв'язаної змінної слід обирати букву, яка відсутня у формулі. Наприклад:

(x) (у) Р(х, у) = (x) (z) Р(х, z).

У даному прикладі здійснено операцію перейменування зв'язаної змінної у.

2. Комутативні властивості кванторів:

(x) (y) Р(х, у) = (у) (x) P(x, у);

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

Змінювати місцями можна тільки однойменні квантори.

(x) (у) Р(х, у)  (у) (x) P(x, у).

3. Дистрибутивні властивості кванторів:

(x)F(x)  G = (x)(F(x)  G);

(x)F(x)  G = (x)(F(x)  G);

(x)F(x)  G = (x)(F(x)  G);

(х)F(х)  G = (x)(F(x)  G),

де G — формула логіки предикатів, яка не містить х;

(x)F(x)  (x)H(x) = (x)(F(x)  H(х));

(x)F(x)  (х)H(х) = (x)(F(x)  H(x)).

Сформульований дистрибутивний закон справедливий тільки для квантора загальності  при кон'юнкції  і квантора існування  при диз'юнкції , оскільки інші комбінації призводять до нерівностей:

(x)F(x)  (х)H(х)  (x)(F(x)  H(х));

(x)F(x)  (х)H(х)  (x)(F(x)  H(х)).

Для подолання цього обмеження дистрибутивного закону, слід використовувати заміну зв'язаної змінної:

(x)F(x)  (х)H(х) = (x)F(x)  (у)H(у) = (x)(y) (F(x)  H(y));

(x)F(x)  (х)H(х) = (x)F(x)  (y)H(у) = (х)(у) (F(x)  H(y)).

Таким чином, у загальному випадку дистрибутивні властивості кванторів можна записати такою схемою:

(Q₁x)F(x)  (Q₂y) H(у) = (Q₁x)(Q₂y) (F(x)  H(у));

Q₁x)F(x)  (Q₂y) H(у) = (Q₁x)(Q₂y) (F(x)  H(у)),

Де Q₁, Q₂ — будь-який з кванторів  або .