Свойства операций над множествами.
1. A U B = B U A – коммутативность. A n B = B n A
2. (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C – ассоциативность.
3. (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) – дистрибутивность.
4. Поглощение A U A = A, A n A = A.
5. Существование универсальных границ. А U 0 = A A n 0 = 0 A u U = U A n U = A
6. Двойное дополнение A = A
7. A U A = U A n A = 0
8. Законы двойственности или закон Де – Моргана (AUB) = A n B (AnB) = A U B
Теория булевых функций. Булева алгебра.
Определение. Множество 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. Инвальтивность (X*)* = X
7. Дополнимость X V X* = I, X & X* = 0.
8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y
Булева алгебра всех подмножеств данного множества.
U = {a1, a2… an) [U] = N [P(U)] = 2n
Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.
Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое множество – 0, а универсальное – I.
Дата добавления: 2016-01-06; просмотров: 29; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!