Page 80 - 4570

79

Необхідно зауважити, що для логіки предикатів зберігаються всі
рівносильності та правила рівносильних перетворень логіки висловлювань.

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

Усі закони і тотожності, які справедливі у логіці висловлювань,
залишаються справедливими і у логіці предикатів. Однак у логіці предикатів
існують додаткові закони, які використовують для еквівалентного перетворення
формул, що містять квантори та змінні.
1. Заміна зв’язаної змінної
Уведення нового позначення зв’язаної змінної не змінює змісту формули
логіки предикатів за умови, якщо ніяка вільна змінна у будь-якій частині
формули не буде після перейменування зв’язаною змінною, наприклад:
1) х Р(х) = у Р(у);
2)  х Р(х) = у Р(у);
3)  х у Р(х, у) =  z t (z, t).
2. Комутативні властивості кванторів
У логіці предикатів можна змінювати місцями тільки однойменні
квантори, наприклад:
1)  х  у Р(х, у) =  у  х Р(х, у);
2) х у Р(х, у) = у х Р(х, у);
3)  х у Р(х, у)  у  х Р(х, у).
Приклад 2.33. Для предиката  xy ДОРІВНЮЄ(х+1, у) показати, що
зміна місцями кванторів приводить до невідповідності між висловлюваннями
до і після зміни місцями кванторів.
Розв’язання. Заданий предикат є висловлюванням і означає, що «для будь-
якого числа х існує число у, яке більше його на одиницю». Наведене
висловлювання є істинним. Але якщо поміняти порядок розташування
кванторів на протилежний, то отримаємо таке висловлювання: y x
ДОРІВНЮЄ(х+1, у). Одержане висловлювання означає, що «існує таке число у
(одне), яке на одиницю більше будь-якого числа х». Це висловлювання не
відповідає попередньому і є хибним, що підтверджує закон комутативної
властивості кванторів.
3. Дистрибутивні властивості кванторів
Нехай формула Р(х) містить пов’язану змінну х, а формула Q не містить
пов’язаної змінної х, тоді:
1) х (Р(х)  Q) = х Р(х)  Q;
2)  х (Р(х)  Q) =  х Р(х)  Q;
3) х (Р(х)  Q) = х Р(х)  Q;
4)  х (Р(х)  Q) =  х Р(х)  Q.
4. Закон де Моргана для кванторів
Нехай Р(х) – формула, що містить пов’язані і вільні змінні. Тоді
справджуються рівносильності:
 хР (х) =  х Р(х); (2.7)
  хР(х) =  х Р(х). (2.8)