Материал: discrete_mathematics
У лівій секвенції 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
Розділ 2 МНОЖИНИ ТА ВІДНОШЕННЯ
Основи теорії множин було закладено відомим німецьким математиком Георгом Кантором у другій половині ХІХ ст. Появу цієї теорії з ентузіазмом сприйняли багато авторитетних математиків. Вони побачили в ній засоби створення метамови математики, тобто формальної універсальної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби було зроблено незабаром після виникнення канторівської теорії множин.
Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей – парадоксів, або антиномій, теорії множин. Виникла кризова ситуація. Одні математики, посилаючись на штучність сформульованих антиномій, вважали за краще не помічати суперечності або не надавати їм великого значення. Інші
– зосередили зусилля на пошуках більш обґрунтованих і точних принципів і концепцій, на яких можна було б побудувати несуперечливу теорію множин.
У результаті було запропоновано кілька формальних (або аксіоматичних) систем, що стали фундаментом сучасної теорії множин, отже, і всієї класичної математики. Важливість цих досліджень підкреслює і той факт, що значний внесок до становлення аксіоматичної теорії множин зробили такі видатні математики й мислителі минулого століття, як Б. Рассел, Д. Гільберт, К. Гедель та ін.
Сьогодні теорія множин – це математична теорія, на якій ґрунтується більшість розділів сучасної математики, як неперервної, так і дискретної.
2.1.Поняття множини. Способи задання множин
Для наших цілей достатньо викласти основи інтуїтивної, або наївної, теорії множин, яка в головних своїх положеннях зберігає ідеї й результати її засновника Г. Кантора.