Свойства универсального множества. Булева алгебра множеств. Число подмножеств

Булева алгебра множеств. Число подмножеств. Бинарные отношения. Отношения эквивалентности и частичного порядка. Отображения, взаимно-однозначные отображения. Мощность множества. Счетные множества и их свойства. Теорема Кантора о несчетности (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)=n², ∃ f: N → A ⇔ |N|=|A|, N ⊂ A

А

N