2. Якщо A та B – формули, то
(← A), (A B), (A B), (A → B), (A ~ B)
–теж формули.
3.Якщо A – формула, а x – предметна змінна в A, то
( x(A)) і ( x(A))
–теж формули.
4.Інших формул, крім утворених за правилами 1–3, немає. Це означення дозволяє стверджувати, що всі формули алгеб-
ри висловлень є формулами логіки предикатів, оскільки висловлення – це нульмісні предикати. За допомогою означення неважко також переконатися, що вирази
( x( y (A(x, y)) → (B(x) ( z(C(x, z))))),
( x( y(A(x, y) B(x)) → ( y(C(x, y))))
є формулами логіки предикатів. Для зручності можна запровадити деякі домовленості про скорочення кількості дужок у формулах. По-перше, залишимо всі умови скорочення кількості дужок, які було прийнято в алгебрі висловлень, виходячи з пріоритету логічних операцій. По-друге, випускатимемо всі зовнішні дужки. Вважатимемо, що квантори мають більший пріоритет, ніж логічні операції. Випускатимемо також дужки, що позначають область дії квантора, якщо остання є елементарною формулою. Нарешті, не писатимемо дужки між кванторами, що йдуть один за одним. Правила асоціативності залишаються такими самими, як і для пропозиційної логіки. Що стосується кванторних операцій, то вони виконуються в порядку, зворотному до їх написання (справа наліво).
Нехай F(x1, x2, …, xn) – деяка формула логіки предикатів, а множина M – деяка предметна область. Для інтерпретації F(x1, x2, …, xn) в M необхідно задати значення символів елементарних предикатів у M як n-місних предикатів у M. За наявності такої логічної (істиннісної) інтерпретації формули F у M можливі три основні ситуації.
1. Існує набір значень змінних, для якого формула F набуває значення 1. У цьому разі формулу F називають виконуваною в області M.
2. Якщо формула F набуває значення 1 (виконувана) для всіх наборів значень з області M, то її називають тотожноістинноювM.
67
3. Якщо формула F невиконувана в області M, то її називають
тотожно хибною в M.
Наведені означення можна узагальнити, якщо розглядати різні предметні області, а саме: якщо для формули F існує область M, в якій вона виконувана, то формулу F називають виконува ною; формулу, тотожно істинну в будь-яких областях M, нази-
вають тотожно істинною, або логічно загальнозначущою; фор-
мула, невиконувану в усіх областях M, називають тотожно хиб ною, або суперечністю.
Приклад 1.21. Формула
xA(x, y) → xA(x, y)
виконувана й тотожно істинна в усіх одноелементних областях M. Формула
F(x1, x2, …, xn) ¬ F(x1, x2, …, xn)
тотожно істинна, а формула
F(x1, x2, …, xn) ¬ F(x1, x2, …, xn)
тотожно хибна.
Тотожноістиннимиєформули xP(x) → P(y) іP(y) → xP(x).◄
Формули F1 і F2 називають рівносильними (еквівалентни ми), якщо за всіх можливих підстановок значень замість їхніх змінних вони набувають однакових значень; позначають F1 = F2
або F1 ≡ F2.
Зауваження. Слід розуміти відмінність відношення рівносильності ≡ від операції еквівалентності ~. Операція еквівалентності ~ є операцією булевої алгебри, яка двом булевим предикатам ставить у відповідність новий предикат, у той час як рівносильність є бінарним відношенням на множині формул. Утім, ці поняття поєднані в тому сенсі, що рівносильність формул F1 і F2
свідчить про тотожну істинність формули F1 ~ F2 і навпаки, тотожна істинність формули F1 ~ F2 свідчить про рівносильність F1 і
F2. Зазначимо також, що всі тотожно істинні (усі тотожно хиб ні) формулирівносильні між собою.
Множина всіх тотожно істинних формул логіки предикатів є складовою частиною всіх формальних математичних теорій, тому її дослідження й опис – важлива задача математичної логіки. Значення цієї множини підкреслює також той факт, що їй, як
68
було зазначено вище, належать усі рівносильні співвідношення (тотожності) логіки предикатів.
Як і в логіці висловлень, постають дві проблеми: перша – опис або побудова множини всіх тотожно істинних формул, друга – перевірка тотожної істинності заданої формули логіки предикатів.
Якщо існує процедура розв'язання другої проблеми, то на її основі можна сформулювати такий алгоритм, що породжує шукану множину T тотожно істинних формул. Послідовно будуємо всі формули, кожну з них за відомою процедурою перевіряємо на тотожну істинність і вносимо до множини T ті, для яких результат перевірки позитивний.
Однак на відміну від логіки висловлень, де така процедура існує та зводиться до обчислення значень формули на скінченній множині значень її параметрів, у логіці предикатів області визначення предметних і предикатних змінних формул нескінченні.
Метод обчислення значення формули шляхом підстановки значень замість змінних і послідовного виконання зазначених дій є зручним для встановлення виконуваності заданої формули або доведення нерівносильності певних формул. Для цього достатньо підібрати одну відповідну підстановку, тобто побудувати контрприклад. Застосовувати цей метод можна також, коли предметна область M скінченна. Пов'язано це з тим, що для скінченної множини M = {a1, a2, …, an} кванторні формули можна перетворити на рівносильні їм формули логіки висловлень:
xP(x) = P(a1) P(a2) … P(an),xP(x) = P(a1) P(a2) … P(an).
Замінивши всі квантори за допомогою наведених співвідношень, будь-яку формулу логіки предикатів можна перетворити на рівносильну пропозиційну форму, або формулу логіки висловлень. Істинність останньої на скінченній множині M можна перевірити за допомогою скінченної кількості підстановок й обчислень.
Для доведення ж рівносильності предикатних формул, заданих на нескінченних предметних областях, прямий перебір непридатний, і доводиться застосовувати різні опосередковані методи.
69
Наприклад, вище за допомогою простих міркувань було доведено рівносильність формул, що описують переставність однойменних кванторів у двомісних предикатах, тобто доведено тотожну істинність формул
x yA(x, y) ~ y xA(x, y) та x yA(x, y) ~ y xA(x, y).
Приклад 1.22. Аналогічними міркуваннями доведемо рівносильність, що описує дистрибутивність квантора x відносно кон'юнкції
x(A(x) B(x)) = xA(x) xB(x).
Нехай ліва частина цього співвідношення істинна для деяких предикатів A та B. Тоді для будь-якого a M істинною є кон'юнкція A(a) B(a). Тому A(a) та B(a) одночасно істинні для довільних a, отже, формула xA(x) xB(x) істинна. Якщо ж ліва частина хибна, то це означає, що для деякого a M хибним є або A(a), або B(a). Тому хибне або xA(x), або xB(x), а отже, хибною є й права частина. ◄
Подібним методом можна довести дистрибутивність квантора x відносно диз'юнкції:
x(A(x) B(x)) = xA(x) xB(x).
Приклад 1.23. Доведемо, що квантори x і x недистрибутивні щодо диз'юнкції і кон'юнкції. Дійсно, істинні лише імплікації
xA(x) xB(x) → x(A(x) B(x)),x(A(x) B(x)) → xA(x) xB(x).
Якщо один із предикатів A(x) або B(x) тотожно істинний, то ліва й права частини першої імплікації одночасно істинні. Якщо ж існуватимуть такі значення a, b M, що A(a) та B(b) хибні, то ліва частина хибна, а права може бути або хибною, або істинною. Для її істинності достатньо, щоб для кожного a M істинним був принаймні один із предикатів. Це означає, що знак імплікації → не можна замінити на знак еквівалентності ~, отже, ліва і права частини першої імплікації нерівносильні. ◄
Пропонуємо самостійно проаналізувати другу імплікацію та довести її істинність.
Приклад 1.24. Доведемо ще одне корисне й популярне в логіці та математиці рівносильне співвідношення:
← ( xP(x)) = x(← P(x)).
70
Нехай для деякого предиката P і предметної області M ліва частина істинна. Тоді не існує a M, для якого P(a) істинне. Отже, для всіх a M P(a) хибне, тобто ¬ P(a) істинне. Тому права частина істинна. Якщо ж ліва частина хибна, то існує b M, для якого P(b) істинне, тобто ¬ P(b) – хибне. Отже, права частина також хибна. ◄
Аналогічно можна довести рівносильність
¬ ( xP(x)) = x(¬ P(x)).
Приклад 1.25.
1. Побудувавши відповідну інтерпретацію (контрприклад), довести, що формули A та B логіки предикатів не є рівносиль-
ними: A = x (P(x) Q(x)), B = x P(x) x Q(x).
Для предметної області M = {a, b} визначимо предикати P і Q так: P(a) = 0, P(b) = 1 та Q(a) = 1, Q(b) = 0. Тоді формула A буде хибною, а формула B – істинною.
2. Довести чи спростувати твердження про рівносильність таких формул A та B логіки предикатів:
(а) A = x(P(x) → (Q(x) → R(x))), B = x(P(x) → (R(x) → Q(x)));
(б) A = x(P(x) → (Q(x) → R(x))), B = x(Q(x) → (R(x) → P(x))).
Формули A та B першої пари рівносильні. Це твердження можна довести, перебравши, наприклад, усі вісім можливих комбінацій значень предикатів P, Q і R для довільного об'єкта x із предметної області та переконавшись, що в усіх восьми випадках формули
(P(x) → (Q(x) → R(x))) і (P(x) → (R(x) → Q(x)))
набувають однакових значень.
Цю рівносильність можна обґрунтувати й такими міркуваннями. Формула
(P(x) → (Q(x) → R(x)))
набуває значення 0 тоді й тільки тоді, коли для якогось x із предметної області виконується P(x) = 1, Q(x) = 1 і R(x) = 0. Друга формула
(P(x) → (R(x) → Q(x)))
такожнабуваєзначення0 лишезатихсамихумов.
Формули A та B другої пари нерівносильні. Контрприклад: для предметної області M = {a} покладемо
P(a) = Q(a) = 1 і R(a) = 0.
71