Реферат: Логіка і множини

Множина Pназивається власною підмножиною Qі позначається P⊂Qабо Q⊃P, якщо P⊆Qі P¹Q.

Наступні властивості функцій множин можуть бути легко доведені на основі їх аналогів в логіці.

Розподільний закон. ЯкщоP,Q,Rє множини, то

(a) P∩(Q∪R) = (P∩Q) ∪(P∩R);

(b) P∪(Q∩R) = (P∪Q) ∩(P∪R).

логіка тавтологія еквівалентність квантифікатор

Закон де Моргана. ЯкщоP,Qє множини, то

(a) С (P∩Q) = СP∪ СQ;

(b) С(P∪Q) = СP∩ СQ.

Зробимо це, наприклад, для першого розподільного закону. Припустимо, що функції p(x), q(x), r(x) відносяться до множин P, Q, R, тобто P= {x: p(x)}, Q= {x: q(x)} і R= {x: r(x)}. Тоді

P∩(Q∪R) = {x: p(x) ∧(q(x) ∨r(x))}

(P∩Q) ∪(P∩R) = {x: (p(x) ∧q(x)) ∨(p(x) ∧r(x))}.

Припустимо, що x∈P∩(Q∪R). Тоді p(x) ∧(q(x) ∨r(x)) істинно. По першому розподільному закону для логічних функцій маємо тавтологію

(p(x) ∧(q(x) ∨r(x))) «((p(x) ∧q(x)) ∨(p(x) ∧r(x)))

Звідси слідує, що (p(x) ∧q(x)) ∨(p(x) ∧r(x)) істинно, так що x∈(P∩Q) ∪(P∩R). А це значить, що

(1) P∩(Q∪R) ⊆(P∩Q) ∪(P∩R).

Тепер припустимо, що x∈(P∩Q) ∪(P∩R). Тоді (p(x) ∧q(x)) ∨(p(x) ∧r(x)) істинно. З першого розподільного закону для логічних функцій слідує, що p(x) ∧(q(x) ∨r(x)) істинно, так що x∈P∩(Q∪R). Це дає

(2) (P∩Q) ∪(P∩R) ⊆P∩(Q∪R).

Потрібний результат слідує з (1) і (2).

6. Логіка квантифікаторів

Повернемось до прикладу"xє парне число". Обмежимо xмножиною цілих чисел Z . Tоді вислів "xє парне число" істинний лише для деяких xвZ. Звідси слідує, що вислів "деякіx∈Zпарні" істинний, якщо вислів "всіx∈Z непарні" хибний.

В загальному випадку розглянемо функцію вислів p(x) в якій змінна xналежить певній множині. Введемо наступні позначення для висловів

∀x, p(x) (для всіхx, p(x) істинний);

і

∃x, p(x) (для деякихx, p(x) істинний).

Символ ∀(для всіх) і ∃(для деяких) називаються відповідно універсальним квантифікатором і квантифікатором існування. Зауважимо, що змінна xне є суттєва, вона може бути замінена будь якою іншою, так що ∀x, p(x) і ∀y, p(y) означають одне й те ж саме.

(Теорема Лагранжа) Кожне натуральне число є сума квадратів чотирьох цілих чисел. Це можна записати як

∀n∈N, ∃a, b, c, d∈Z, n= a2 + b2 + c2 + d2.

(Гіпотеза Гольдбаха) Кожне парне число більше 2 є сума двох простих чисел. Це можна записати як