Логіка і множини

реферат

5. Функції множин

Припустимо, що функції висловів p(x), q(x) відносяться до множин P, Q, тобто P = {x : p(x)} і Q = {x : q(x)}. Визначимо наступні операції над множинами перетин P ЎЙ Q = {x : p(x) ЎД q(x)};

обєднання P ЎИ Q = {x : p(x) ЎЕ q(x)};

доповнення CP = {x : p(x)};

різницю P Q = {x : p(x) ЎД q(x)}.

Ці означення легко перефразувати у форму

P ЎЙ Q = {x : x ЎК P і x ЎК Q};

P ЎИ Q = {x : x ЎК P або x ЎК Q};

СP = {x : x P};

P Q = {x : x ЎК P і x Q}.

Множина P є підмножиною Q і позначається P ? Q або Q ? P, якщо кожен елемент P є елементом Q. Іншими словами, для множин P = {x : p(x)} і Q = {x : q(x)} маємо P ? Q тоді і тільки тоді, коли p(x) Ўъ q(x) для всіх допустимих значень x ЎК U.

Множини P і Q називаються рівними P = Q якщо вони містять ті ж самі елементи, іншими словами, якщо P ? Q і Q ? P.

Множина 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).

Делись добром ;)