Лекции по дискретна математика


Категория на документа: Математика



- допълнение на множеството A (до универсалното множество U) означаваме = { x | x  A и x  U } = U A;

под фамилия от множества ще разбираме множество от множества;

най-общо под алгебра ще разбираме непразно множество, в което са въведени операции; алгебрата на подмножествата на дадено множество (U) с по-горе въведените операции се нарича булева алгебра на името на Джордж Бул;

Свойства на операциите: (A, B, C са множества)
1. Комутативност: A  B = B  A, A  B = B  A
2. Асоциативност: (A  B)  C = A  (B  C),
(A  B)  C = A  (B  C)
3. Идемпотентност: A  A = A, A  A = A
4. Дистрибутивност: A  (B  C) = (A  B)  (A  C)

A  (B  C) = (A  B)  (A  C)
5. Константи: A   = A, A   = , A  U = U, A  U = A
6. Допълнение: A  = U, A  = , = A
7. Закони на Де Морган: ,

Примерно доказателство на законите на Де Морган:
нека x  ; тогава x  A  B  x  A, x  B  x  , x  
x  ; нека x  ; тогава x  A и x  B  x  A  B 
x  ; сега от аксиомата за обема  ;
ще бележим J2 = { 0, 1};
нека A е множество; фамилията от всички подмножества на A наричаме булеан на A и бележим с 2A = { S | S  A } ;
например = { , { 0, 1}, { 0}, { 1} };

нека a и b са произволни елементи; множеството { a, { a, b}} ще бележим с (a, b) и ще наричаме наредена двойка от елементите
a и b; ясно е, че (a, b)  (b, a);

дефинираме декартово произведение на множествата A и B:
A x B = { (a, b) | a  A, b  B}, т.е. декартовото произведение на две множества A и B е множеството от всички наредени двойки с първи елемент от A и втори елемент от B;
ако M е множество, декартовото произведение M x M бележим с M2 и наричаме декартов квадрат на М;

Примери:
ако в евклидовата равнина E е въведена координатна система, то на всяка точка е съпоставена биективно наредена двойка реални числа, така че E = R x R = R2;
J2 x J2 = { (0, 0), (0, 1), (1, 0), (1, 1) };

ясно е, че ако A, B и C са множества, то
(A x B) x C  A x (B x C), тъй като наредената двойка (a, (b, c)) се различава от ((a, b), c); можем да разгледаме асоциативен вариант на декартовото произведение:
дефинираме тройно декартово произведение на множествата
A, B и C: A x B x C = { (a, b, c) | a  A, b  B, c  C } ; елементите
(a, b, c) на A x B x C наричаме наредени тройки;
ще считаме, че (A x B) x C = A x (B x C) = A x B x C, т.е. наредените двойки ((a, b), c) и (a, (b, c)) ще отъждествяваме с наредената тройка
(a, b, c);
аналогично можем да дефинираме n-кратно декартово произведение на множествата A1, A2, …, An:
A1 x A2 x …x An = { (a1, a2, …, an)|ai  Ai } ; елементите
(a1, a2, …, an) на A1 x A2 x …x An наричаме наредени n-орки; ще считаме, че (A1 x A2 x … x Ai) x (Ai+1 x Ai+2 x … x An) = A1 x A2 x …x An
за всяко i = 1, 2, …, n-1;

Индуктивно дефиниране на множество



Сподели линка с приятел:





Яндекс.Метрика
Лекции по дискретна математика 9 out of 10 based on 2 ratings. 2 user reviews.