Материал: discrete_mathematics

Нехай для деякого предиката 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

За цих умов формула A набуває значення 0, а формула B – значення 1.

3. Перевірити, чи випливає в логіці предикатів із наведених нижче припущень зроблений з них висновок, тобто чи коректні міркування. Якщо міркування правильні, то побудувати відповідний дедуктивний ланцюжок; якщо ж некоректні, – то відповідний контрприклад.

Припущення: 1) деякі вписані в коло чотирикутники є прямокутниками; 2) кожний прямокутник є паралелограмом.

Висновок: отже, деякі вписані в коло чотирикутники є паралелограмами.

Уведемо на множині M усіх чотирикутників такі предикати:

P(x) – x – чотирикутник, вписаний у коло, Q(x) – x – прямокут-

ник, R(x) – x – паралелограм. Тоді припущення можна записати у вигляді таких предикатних формул:

1) x(P(x) Q(x)), 2) x(Q(x) → R(x)),

а висновок – у вигляді формули x(P(x) R(x)).

Із припущення 1) випливає, що для якогось a M виконується

P(a) Q(a) = 1, тобто P(a) = 1 та Q(a) = 1.

Звідси та із припущення 2) маємо

R(a) = 1.

Отже, P(a) R(a) = 1, тому формула x(P(x) R(x)) істинна вM. ◄ Формула A перебуває в прeнeкснiй формi, якщо вона має вигляд Qx1 ...Qxn B, дe Qxk − кванторний прeфікс xk або xk , B −

бeзкванторна формула.

Формулу в прeнeкснiй формi називають прeнeксною фор

мулою.

Розглянемо важливі рівносильні співвідношення, які дозволяють змінювати області дії кванторів. Нехай B – предикатна формула, що не містить вільних входжень змінної x. Тоді справджуються такі рівносильності:

Ці співвідношення означають, що формулу, яка не містить вільних входжень x, можна виносити за межі області дії кванто-

72

ра, що зв'язує x. З іншого боку, ці самі рівносильності дають змогу включати відповідну формулу B до області дії квантора за змінною x, від якої B не залежить.

Приклад 1.26. Знайдeмо прeнeксну форму для формули

х yA(x, y) xB(x)→ ← xA(x, y).

Спочатку проаналізуємо, які змінні є вільними, а які – зв'язаними. Вільна змінна для всієї формули – лише y. Змінні х та y зв'язані в різних підформулах цієї формули. Оскільки є різні квантори зі змінною х, то спочатку замінимо цю змінну у двох останніх кванторах на нові змінні, наприклад z і t. Також треба змінити зв'язану змінну y, наприклад на v. Отримуємо формулу

х vA(x, v) zB(z) → ← xA(t, y).

У підформулі

х vA(x, v) zB(z)

послідовно виносимо квантори згідно з правилами 2) і 6); квантор, який виноситься, підкреслюватимемо:

х vA(x,v) zB(z) = (за правилом 6).

z( х vA(x,v) B(z)) = (за правилом 2).

z( х( vA(x,v) B(z))) = (за правилом 2).

z( х( v(A(x,v) B(z)))) = (знімаємо зовнішні дужки).

z х v(A(x,v) B(z)).

Перетворення застосовані коректно, оскільки формули не містять вільних змінних, які б потрапляли в розширену область дії кванторів. ◄

Завдання для самостійної роботи

1. Довести, що формула логіки предикатів

x y (P(x) ← P(y))

логічно загальнозначуща. Чи є такою наступна формула?y x (P(x) ← P(y)).

2.Довести, що формула тотожно істинна: (а) x(P(x) Q(x)) → ( xP(x) x Q(x)); (б) ( x P(x) → xQ(x)) ~ x(P(x) → Q(x)).

3.Довести чи спростувати твердження про те, що запропонована формула тотожно істинна:

(а) xP(x) x(P(x) → Q(x)) → xQ(x);

73

(б) xP(x) x(P(x) → Q(x)) → xQ(x); (в) xP(x) x(P(x) → Q(x)) → xQ(x);

(г) x(P(x) → (Q(x) → R(x))) → x(P(x) Q(x) → R(x)).

4.Довести, що формули A та B логіки предикатів рівносильні: (а) A = x(P(x) Q(x)), B = xP(x) xQ(x);

(б) A = ← ( x P(x)), B = x (← P(x)).

5.Побудувавши відповідну інтерпретацію (контрприклад), довести, що формули A та B логіки предикатів не є рівносильними:

(а) A = x(P(x) Q(x)), B = x P(x) xQ(x); (б) A = x(P(x) Q(x)), B = x P(x) xQ(x); (в) A = xP(x) → x Q(x), B = x (P(x) → Q(x)).

6. Довести чи спростувати твердження про рівносильність формул A та B логіки предикатів:

(а) A = y x (P(x) → Q(y)), B = y( x P(x) → Q(y)); (б) A = x(P(x) → Q(y)), B = x(P(x)) → Q(y);

(в) A = x(P(x) → Q(y)), B = x(P(x)) → Q(y).

7. Побудувати пренексну форму для формул:

(а) хA(x) → y( zB(x,y,z) → ← xA(x) xC(x, y));

(б) х ← yA(x,y) → xB(x) → ← yA(x, y); (в) ←хA(x) xB(x) x( yC(x,y) → A(y));

(г) хA(x) → y( zB(x,y,z) → ← xA(x)).

8. Визначити, які з тверджень 1–5 логічно еквівалентні:

1.Неправильно, що всі числа, кратні 4, є точними квадратами.

2.Усі числа, кратні 4, не є точними квадратами.

3.Не всі числа, кратні 4, є точними квадратами.

4.Існує число, кратне 4, яке не є точним квадратом.

5.Деякі числа, не кратні 4, не є точними квадратами.

У подальших вправах перевірити, чи випливають у логіці предикатів із припущень зроблені з них висновки, тобто чи коректними були здійснені міркування. Якщо міркування правильне, то побудувати відповідний дедуктивний ланцюжок; якщо ж міркування некоректне, то побудувати відповідний контрприклад.

9.

1) Кожне число, кратне 51, кратне 17 і кратне 3.

2) Кожне число кратне 3 тільки тоді, коли сума цифр його запису в десятковій системі числення кратна 3.

74

3) Сума цифр запису числа 10712 не кратна 3. Отже, 10712 не кратне 51.

10.

1) Якщо хтось може розв'язати дану задачу, то знайдеться здібний студент, який зробить це.

2) Петренко – здібний студент, але не зміг розв'язати цю задачу. Отже, ніхто не здатен розв'язати дану задачу.

1.9.Секвенції і секвенційні форми для логіки предикатів

Логіка предикатів, на відміну від логіки висловлень, вводить нові логічні операції – квантори. Розглянемо секвенційні правила для кванторів.

За означенням індексована формула 1 А(х) є істинною за її інтерпретації в області M, якщо є значення предметної змінної x, яке робить істинним формулу A(x). Таке значення x позначимо у. Однак у секвенційному численні немає прив'язки до конкретної області M, тому будемо тлумачити y як певну предметну змін-

ну. Іншими словами, формулу 1 А(х) можна замінити на формулу 1А(х), де y – нова змінна. Ураховуючи наявність у секвенції

інших формул множини ∑, отримуємо правило

1 1 xA(x), ∑

1 A( y), ∑

заумови, що нова змінна у не входить до ∑ { xA(x)}.

Розглянемо тепер правило для 0 А(х). За означенням хибність цієї формули означає хибність формули А(х) за всіх значень x із області предметної інтерпретації. У секвенції такі значення задаються її вільними змінними, тому здається, що правило можна записати у вигляді

де {z1,…, zт} – усі вільні змінні ∑ { xA(x)} . Однак у такому правилі не враховано два моменти:

75