Свойства операций над множествами

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 C) (B C), (A B) C=(A C) (B C) – дистрибутивность.

4. Поглощение A A = A, A A = A.

5. Существование универсальных границ.

А Ø = A; A Ø = Ø; A U = U; A U = A

6. Двойное дополнение

7. Ø

8. Законы двойственности или закон Де – Моргана

Лекция 2: «Теория булевых функций. Булева алгебра»

Определение: Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией () и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры). Названия операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант

X & 0 = 0

X & I = X, где I – аналог универсального множества.

6. Инвальтивность (двойное отрицание) .

7. Дополнимость X V = I, X & = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2ⁿ

Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение - &, дополнение - , пустое множество – 0, а универсальное – I.

Все аксиомы булевой алгебры справедливы в операциях над множествами.

Date: 2015-04-23; view: 655; Нарушение авторских прав