Колізія змінних, заміна зв'язаної змінної, комутативні і дистрибутивні властивості кванторів, закон де Моргана для кванторів
Всі закони і тотожності, які справедливі у логіці висловлень, залишаються справедливими і у логіці предикатів. Крім того, у логіці предикатів існують додаткові законі, що призначені для еквівалентного перетворення формул, що містять квантори та змінні.
Слід зауважити, що перенесення квантора на початок формули може змінити зміст предикатного висловлення. Так, наприклад, "х 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)).
Таким чином, у загальному випадку дистрибутивні властивості кванторів можна записати такою схемою:
(Q1x)F(x)Ú (Q2y) H(у)= (Q1x)(Q2y) (F(x) Ú H(у));
Q1x)F(x) Ù (Q2y) H(у)= (Q1x)(Q2y) (F(x) Ù H(у)),
Де Q1, Q2— будь-який з кванторів $ або ".
4. Закон де Моргана для кванторів:
Ø(("x)F(x)) = ($x)ØF(x);
Ø($x)F(x)) = ("x)ØF(x).
Проілюструємо цей закон таким прикладом. Нехай предикат F(x) означає, що «х є простим числом». Коли х послідовно приймає значення ряду натуральних чисел — х = {1,2, 3, 4, 5, 6, 7, ...}, предикат відповідно змінює істиннісне значення:
F(1) = X, F(2) = I, F(3) = I;
F(4) = X, F(5) = I, F(6) = X, F(7)= I, ....
Переконаємося у справедливості першої формули для заперечення квантора загальності:
Ø(("x)F(x)) = «не всі х є простими числами» = «існують такі х, які є непростими числами» = ($х)ØF(x) = I.
Обидва наведені висловлення істинні. Тепер переконаємося у справедливості другої формули для заперечення квантора існування:
Ø(($x)F(x)) = «немає жодного х, яке було б простим» = «всіх є непростими числами» = ("x)ØF(x) = X.
Ці висловлення є хибними.
Запитання
1. Що розуміють під колізією змінних?
2. До яких наслідків може призвести перенесення квантора на початок формули? Наведіть приклади коректного і некоректного перенесення кванторів на початок формули.
3. Поясніть суть заміни зв'язаної змінної.
4. Сформулюйте комутативні властивості кванторів.
5. За дотримання якої умови правомірно використовування дистрибутивних властивостей кванторів?
6. Яким чином можна обійти обмеження дистрибутивних властивостей кванторів?
7. Запишіть формули закону де Моргана для кванторів.
Завдання
1. Опустіть знаки заперечення безпосередньо на предикати або булеві змінні:
а) Ø($х) (Ø("y) (B(y)Ú ($z)С(z)) ÙØА(х)));
б) Ø("y) (Ø$х) (А(у, z)Ú B(x))Ú C(z));
в) Ø($x) (Ø"y) (A(x) ® B)) Ú C(x, y));
г) Ø("u) Ø("v)(P(u) ® Q(v) ® A(z)).
2. Встановіть, чи еквівалентні задані предикати:
а) ($х)(А(х) Ù ØВ(у))и ("z)(А(z) ® В(у));
б) ("x)((A(x) ® В(х)) Ù (А(х) ®ØВ(х))) и Ø($у) А(у).
3. Винести за дужки квантори:
а) ($ v) C(v, у)Ù (($х) А(х) Ú В);
б) ($х)($y) А(х, у) Ù ($х)($у) В(х, у);
в) ($х) А(х, у) Ú (("x) B(x)Ú ("y) С(у));
г) ($x)("y)A(x, у) Ù ($х)($z) (В(х, z) Ù ($y)A(x, у)).
4. Довести загальнозначущість таких формул:
а) ("x)P(x) ® ($y)P(y);
б) ("x)P(x) Ú (($y)ØP(y)).
5. Довести, що формула ("x)P(x) Ù ($у)ØР(у)суперечлива.
6. Довести, що формула Р(а)®Ø(($х)Р(х)) несуперечлива.
