Материал: discrete_mathematics
ченнями y та z. Перша секвенція 0 A( y), 1 A(z), 0 B(z) визначає значення базових предикатів A та B: A(a) = 0, A(b) = 1, B(b) = 0. Значення В(а) секвенція не визначає, тому воно можу бутидовільним
(позначаємо знаком *). Будуємо таблицю, що |
x |
A(x) |
B(x) |
задає модель (інтерпретацію предикатних |
a |
0 |
* |
символів): |
b |
1 |
0 |
Обчислимо значення формули |
|
|
|
(xA(x) → xB(x)) → x(A(x) → B(x)) |
|
|
|
у цій моделі. Оскільки вільних змінних немає, то початковий стан змінних задається порожньою множиною. У наведеній формулі головною операцією є імплікація, тому обчислюємо значення: антецедента – xA(x) → xB(x); консеквентна – x(A(x) → B(x))
на початковому стані. Антецедент сформовано за допомогою імплікації, тому обчислюємо xA(x) та xB(x).
Бачимо, що в нашій моделі xA(x) набуває значення 0, відповідно xA(x) → xB(x) отримує значення 0 (тут значення кон-
секвента не є важливим), отже, значення
( xA(x) → xB(x)) → x(A(x) → B(x)) = 0,
тобто формула спростовна.
Аналогічно будують модель для незамкненої секвенції 1 B( y), 1 A(z), 0 B(z). Ця модель також задає контрприклад. ◄
3. Чиєвсюдиістинноюформула x(A(x) →B(x)) →(A(x) →xB(x))?
► Зауважимо, що у формулі є вільна змінна x. Будуємо секвенційне виведення цієї формули (коментарі для правил виведення пишемо у фігурних дужках):
|
|
0 x(A(x) → B(x)) → (A(x) → xB(x)) |
|
|
. |
|||||
|
|
1 x(A(x) → B(x)), |
0(A(x) → xB(x))* |
|
||||||
|
|
|
|
|
||||||
|
|
1 x(A(x) → B(x))*, |
|
1 A(x), 0 xB(x) |
|
|
|
|||
|
|
1 A(y) → B(y))*, |
1 A(x), 0 xB(x)) |
|
|
|
||||
|
|
0 A(y), 1 A(x), 0 xB(x)* |
|
|
|
1 B(y), 1 A(x), 0 xB(x)* |
|
|
|
|
|
|
{тут вільні x, y} |
|
|
|
{тут вільні x, y} |
|
|
|
|
|
|
0 A( y), 1 A(x), 0 B(x), 0 B(y), |
|
|
1 B(y), 1 A(x), 0 xB(x)* |
|
|
|
||
|
|
0 xB(x) |
|
|
|
|
1 B(y)×, 1 A(x), 0 B( y) ×, |
|
|
|
|
|
{тут вільні x, y, z} |
|
|
|
|
0 B(x), 0 xB(x) |
|
|
|
|
|
|
|
|
|
× |
|
|
|
|
|
|
! |
|
|
|
|
||||
|
|
|
81 |
|
|
|
|
|
||
У лівій секвенції 0 A( y), 1 A(x), 0 B(x), 0 B( y), 0 xB(x) є неатомарна формула 0 xB(x), але застосування правила 0 не змінює
секвенцію. Отже, секвенція не є замкненою. Щоб отримати контрприклад, будуємо модель із двома константами a та b, вважаючи їх відповідно значеннями x та y. Секвенція визначає значення базових предикатів A та B:
A(b) = 0, A(a) =1, B(a) = 0, B(b) = 0.
Будуємо таблицю, яка задає модель (інтер- |
|
z |
A(z) |
B(z) |
|
a |
1 |
0 |
|
претацію предикатних символів): |
|
|||
|
b |
0 |
0 |
|
Обчислимо значення формули |
|
|||
|
|
|
|
|
x(A(x) → B(x)) → (A(x) → xB(x)) |
|
|
|
|
у такій моделі, вважаючи a значенням x. У цій формулі головною операцією є імплікація, тому обчислюємо значення антеце-
дента x(A(x) → B(x)) |
і консеквента. Головною операцією ан- |
тецедента є квантор |
існування, тому обчислюємо формулу |
A(x) → B(x) за значень x, рівних a та b. Маємо, що |
|
A(a) → B(a) = 0 та A(b) → B(b) =1. |
|
Отже, значення x(A(x) → B(x)) дорівнює 1. |
|
Тепер обчислюємо консеквент |
|
|
A(x) → xB(x). |
Тут А(х) отримує значення 1, а xB(x) – значення 0. Тому |
|
A(x) → xB(x) |
матиме значення 0, як і вся формула в цілому. |
||||||||||
Таким чином, формула спростовна. |
|
|
|
||||||||
Зазначимо, |
що |
якби А не |
залежало від x, то формула |
||||||||
x(A → B(x)) → (A → xB(x)) була б істинною. Дійсно, |
|
|
|
||||||||
|
|
|
|
0 x(A → B(x)) → (A → xB(x)) |
|
|
. |
||||
|
|
|
|
1 x(A → B(x)), |
0(A → xB(x))* |
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
1 x(A → B(x))*, 1 A, 0 xB(x) |
|
|
|
||||
|
|
|
|
|
1 A → B(x) *, 1 A, 1 xB(x) |
|
|
|
|||
|
|
|
0 A ×, 1 A ×, 0 xB(x) |
1 B(x), 1 A, 0 xB(x)* |
|
|
|
||||
|
|
|
|
× |
|
|
1 B(x) ×, 1 A, 0 B(x) ×, 0 xB(x) |
|
|
|
|
×
4. Чи є всюди істинною формула
xA(x) B(x) → x(A(x) B(x))?
82
► Будуємо секвенційне виведення:
|
|
|
|
|
|
0 xA(x) B(x) → x(A(x) B(x)) |
|
|
|
. |
|
|
|
|||||
|
|
|
|
|
|
1 xA(x) B(x)*, |
0 x(A(x) B(x)) |
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
1 xA(x), 0 x(A(x) B(x)) 1 B(x), 0 x(A(x) B(x)) |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
1 xA(x)*, 0 x(A(x) B(x)) |
|
|
|
|
|
|
|
|
. |
|||
|
|
|
|
|
|
1 A( y), 0 x(A(x) B(x))* |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
1 A( y), 0 A( y) B( y)* 0 x(A(x) B(x)) |
|
|
|
|
|
|
|
|||||
|
|
1 A( y)×, 0 A( y)×, 0 x(A(x) B(x)) |
|
1 A( y), 0 B( y), 0 x(A(x) B(x)) |
||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Залишилось побудувати виведення для другої секвенції: |
|
|
|
|||||||||||||
|
|
|
|
|
|
1 A( y), 0 B( y), 0 x(A(x) B(x))* |
|
|
|
. |
|
|
|
|||||
|
|
|
|
|
|
1 A( y), 0 B( y), 0 A( y) B( y)*, 0 x(A(x) |
B(x)) |
|
|
|
||||||||
|
|
|
|
|
|
1 A( y)×, 0 B( y), 0 A( y)×, |
|
1 A( y), 0 B( y), 0 B( y), |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
0 x(A(x) B(x)) |
|
0 x(A(x) B(x)) |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
! |
|
|
|
|
|
|
|
|
|
|
|
Отримали незамкнену секвенцію, яка до- |
|
z |
|
A(z) |
B(z) |
|||||||||||
зволяє побудувати таку модель: |
|
|
|
a |
1 |
0 |
||||||||||||
|
|
На цій моделі початкова формула спростовна. |
◄ |
|
|
|
|
|
|
|
||||||||
|
|
5. Чи є всюди істинною наступна формула? |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
y xA(x, y) → x yA(x, y). |
|
|
|
|
|
|
|
|
|
|||
|
|
► Будуємо секвенційне виведення: |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
0 y xA(x, y) → x yA(x, y) |
|
|
|
|
|
|
. |
|
|
|||
|
|
|
|
|
|
1 y xA(x, y)*, 0 x yA(x, y) |
|
|
|
|
|
|
|
|
|
|||
|
|
Тепер будуємо виведення для першої секвенції: |
|
|
|
|
|
|
|
|||||||||
1 xA(x, z), 0 x yA(x, y)* 1 xA(x, z)*, 0 yA(t, y)
1 xA(x, z), 1 A(z, z), 1 A(t, z), 0 yA(t, y)*
1 xA(x, z), 1 A(z, z), 1 A(t, z)×, 0 A(t, z)×, 0 A(t,t), 0 yA(t, y)*
Дерево виведення замкнене, тому формула є всюди істинною. 6. Чи є всюди істинною формула
x yA(x, y) → y xA(x, y)?
Будуємо секвенційне виведення (використовуємо для введених змінних позначення як для констант: a, b, c, d, e, …):
83
|
|
|
|
0 x yA(x, y) → y xA(x, y) |
|
|
|
. |
|
|
|
|
|
1 x yA(x, y)*, 0 y xA(x, y) |
|
||||
|
|
|
|
|
|
|
|
||
|
|
|
|
{вільних змінних немає, вводимо a} |
|
|
|
|
|
|
|
|
|
1 x yA(x, y), 1 yA(a, y)*, 0 y xA(x, y) |
|
|
|
|
|
|
|
|
|
{вводимонову зміннуb} |
|
|
|
|
|
|
|
|
|
1 x yA(x, y), 1 A(a,b), 0 y xA(x, y)* |
|
|
|
|
|
|
|
|
|
{підставляємо замість y усі вільнізмінні − a,b} |
|
|
|
|
|
|
|
|
|
1 x yA(x, y), 1 A(a,b), 0 y xA(x, y), 0 xA(x, a)*, 0 xA(x,b) |
|
|
|
|
|
|
|
|
|
{вводимоновузмінну c} |
|
|
|
|
|
|
|
|
|
1 x yA(x, y), 1 A(a,b), 0 y xA(x, y), 0 A(c,a), 0 xA(x,b)* |
|
|
|
|
|
|
|
|
|
1 x yA(x, y)* , 1 A(a,b), 0 y xA(x, y), 0 A(c,a), 0 A(d,b) |
|
|
|
|
|
|
|
|
1 x yA(x, y), 1 yA(b, y)* , 1 A(a,b), 0 y xA(x, y), 0 A(c,a), 0 A(d,b) |
|
|
|
|
||
|
|
|
{вводимоновузмінну e} |
|
|
|
|
||
|
|
|
|
1 x yA(x, y), 1 A(b,e)* , 1 A(a,b), 0 y xA(x, y), 0 A(c,a), 0 A(d,b) |
|
|
|
|
|
2. Чи є тотожно істинними формули? (а) (A(x) → xB(x)) → (xA(x) → B(x));
(б) (A(x) → xB(x)) → x(A(x) → B(x)); (в) ( xA(x) → B(x)) →(A(x) →xB(x)); (г) ( xA(x) → B(x)) → (A(x) → xB(x)); (д) ( xA(x) → B(x)) → (A(x) → xB(x)); (е) x(A(x) → B(x)) → (A(x) → xB(x)); (є) (A(x) → xB(x)) → x(A(x) → B(x)); (ж) xA(x) B(x) → x(A(x) B(x));
(з) xA(x) B(x) → x(A(x) B(x)); (и) x(A(x) B(x)) → xA(x) B(x); (і) xA(x) B(x) → x(A(x) B(x)); (ї) x(A(x) B(x)) → xA(x) B(x); (й) x(A(x) B(x)) → xA(x) B(x); (к) x(A(x) B(x)) → xA(x) B(x); (л) x(A(x) B(x)) → xA(x) B(x); (м) A(x) xB(x) → x(A(x) B(x)).
5. Довести рівносильності: |
|
(а) ←xA(x) ~ x ← A(x); |
(б) x yA(x, y) ~ y xA(x, y); |
(в) x yA(x, y) ~ y xA(x, y); |
|
(г) x(A(x) B(x)) ~ xA(x) xB(x); (д) x(A(x) B(x)) ~ xA(x) xB(x).
85