Булева алгебра множеств. Число подмножеств. Бинарные отношения. Отношения эквивалентности и частичного порядка. Отображения, взаимно-однозначные отображения. Мощность множества. Счетные множества и их свойства. Теорема Кантора о несчетности (0,1). Мощность континуума.
<F(U), ˅,˄, ˉ > - сигнатура булевой алгебры.
А = <М, Q1,….Qn>-алгебра (М-носитель алгебры, Qi-операции)
Пусть А-любое множество. Символом Р(А)={X/ X∈A} обозначается множество – степень (∑ всех возможных подмножеств множества А).
U- универсум. Универсальное множество —множество, содержащее все мыслимые объекты. Универсальное множество единственно.
Свойства универсального множества
· Любой объект, какова бы ни была его природа, является элементом универсального множества.
· В частности, само универсальное множество содержит себя в качестве одного из многих элементов.
· Любое множество является подмножеством универсального множества.
· В частности, само универсальное множество является своим подмножеством.
· Объединение универсального множества с любым множеством равно универсальному множеству.
· В частности, объединение универсального множества с самим собой равно универсальному множеству.
· Пересечение универсального множества с любым множеством равно последнему множеству.
· В частности, пересечение универсального множества с самим собой равно универсальному множеству.
· Исключение универсального множества из любого множества равно пустому множеству.
· В частности, исключение универсального множества из себя равно пустому множеству.
· Исключение любого множества из универсального множества равно дополнению этого множества.
· Дополнение универсального множества есть пустое множество.
· Симметрическая разность универсального множества с любым множеством равна дополнению последнего множества.
· В частности, симметрическая разность универсального множества с самим собой равна пустому множеству.
Элементы Булевой алгебры: а) числа b) переменные с) операции d) выражения e) функции f) законы.
Операции ˅,˄, ˉ - связаны между собой законами.
1. Закон коммутативности: A˅B=B˅A, A˄B=B˄A;
2. Закон ассоциативности: A˅(B˅C)=(A˅B)˅C, A˄(B˄C)=(A˄B)˄C;
3. Закон дистрибутивности: A˅(B˄C)=(A˅B) ˄(A˅C), A˄(B˅C)=(A˄B) ˅(A˄C);
4. Закон двойного отрицания 
5.Законы де Моргана: 
6. Законы поглощения: A˅ (A˄B)=A, A˄ (A˅B)=B;
Определение: Бинарным отношением между множествами X и Y называется любое подмножество ρ прямого произведения X х Y.
Если X = Y => ρ ⊆ X x Y – бинарное отношение на Х
ρ ⊆ X x Y:
1) рефлексивное, если (х;х) ∈ρ (каждый элемент находится в отношении сам с собой).
2)симметричное, если (x,y) ∈ρ => (y,x)∈ρ;
3)транзитивное, если (x,y) ∈ρ, (y,z) ∈ρ => (x,z) ∈ρ;
4) антисимметричное, если (x,y) ∈ρ, (y,x) ∈ρ => x=y
Отношение ρ на Х, при условии, что выполнено 1, 2, 3 называется отношением эквивалентности: x ~ y;
Классом эквивалентности X (x) элемента x называется подмножество элементов, эквивалентных x. Из вышеприведённого определения немедленно следует, что, если y ∈ X (x) то X (y)= X (x).
Множество всех классов эквивалентности обозначается 
.
Определение: отношение ρ на Х, при условии, что выполнено 1, 4, 3 называется отношением частичного порядка;
Пусть P(U) – множество всех подмножеств множества U, отношение включения ⊆ на P(U) является отношением частичного порядка.
Определение: отношение ρ на Х, при условии, что выполнено 4, 3 называется отношением строгого частичного порядка;
Определение: ρ называется функцией из Х в У, или отображением, если каждому x∈ X поставлено в соответствие единственное значение y из Y:
f: X → Y ∀x ∈ X →! f(x) ∈ Y: y=f(x); При этом Х -область определения, У - область значения.
х- прообраз (аргумент)
у- образ (значение);
Определение: f называется отображением на (сюръекцией), если образ f(x) совпадает со всем множеством Y: (f(x)=Y ⇔∀y ∈ Y ∃x ∈ X: y=f(x))
Определение: f называется взаимооднозначным отображением (инъекцией) если для любого х1 ≠ х2 из Х, значения f(x1) ≠f(x2) (Образы различных элементов различны)
Определение: f называется взаимно-обратным отображением (биекцией), если оно инъективно и сюръективно.
Определение: число элементов множества А называется мощностью этого множества и обозначается |А|;
Определение: множества Ч и У называются равномощными(имеющими равную мощность), если между ними установлено взаимно-однозначное соответствие: ∃ f: X → Y ⇔ |X|=|Y|;
Ex: f(n)=n2, ∃ f: N → A ⇔ |N|=|A|, N ⊂ A
А
N
