Алгебра множеств. Законы алгебры множеств. Доказать один из законов алгебры множеств.
Алгеброй
множеств7) называется
пара 
,
где 
—
некоторая совокупность множеств, а 
—
набор операций над множествами. Обычно
полагают, что 
—
множество всех подмножеств универсума 
,
а в качестве
берут
рассмотренные выше операции 
Законы алгебры множеств.
1. Коммутативность.
относительно операции объединения, относительно операции пересечения.
А
В=В
А
А
В=В
А
2. Ассоциативность.
относительно операции объединения, относительно операции пересечения.
А (В С)=(А В) С А (В С)=(А В) С
3. Дистрибутивность.
пересечения относительно объединения, объединения относительно пересечения.
А (В С)=( А В) (А С) А (В С)=( А В) (А С)
4. Закон де Моргана.
относительно объединения, относительно пересечения.
=
=
5. Законы поглощения.
относительно объединения, относительно пересечения.
A (A B)=A A (A B)=A
A ( В )= А В A ( B)= А В
6. A A=A A A=A
7. A
=J
A
=
8. A =A A J=A
9. A J=J A =
10. Закон двойного отрицания.
=A
11. A
B=B
A
12. A\B = A
13. A B=( B) (A )
Все эти законы могут быть доказаны с помощью поэлементной схемы доказательства.
Покажем, например, справедливость закона 12.
Пусть N= A\B, M= A .
Покажем, что N
M.
Пусть x
A\B,
т.е. x
A
и x
B.
Так как x
B,
то x
.
Отсюда x
A
и x
,
т.е. x
A
=M.
Покажем, что M N.
Пусть x M= A , т.е. x A и x . Отсюда x A и x B, т.е. x A\B =N.
Замечание.
Для сокращения записи в дальнейшем будем считать, что операция пересечение “сильнее” чем объединение, разность, симметрическая разность, поэтому, там где это возможно мы будем опускать скобки. Кроме того, иногда мы будем опускать знак операции пересечения (как в алгебре знак операции умножения). Так, например, запись ABC\B означает (A B C)\C. Здесь кроме выше оговоренных правил применен закон ассоциативности, позволяющий опускать скобки при выполнении последовательности операций объединения или пересечения множеств.
Доказательства. Некоторые приемы доказательств (графический; доказательство равенства соотношений типа X=Y; от противного). Примеры доказательства равенства множеств.
Множество. Мощность множества. Нахождение мощности объединения множеств (для двух множеств, для трех множеств, для n-множеств). Привести пример.
под множеством понимается, совокупность каких либо объектов произвольной природы, обладающая некоторым общим признаком.
Пусть даны два множества A и B. Тогда они называются равномощными, если между ними существуетбиекция . Из свойств биекции следует, что равномощность является отношением эквивалентности. Мощностью или кардинальным числом множества A называется соответствующий ему класс эквивалентности. Мощность множества обозначается | A | . Тот факт, что два множества равномощны, записывается: | A | = | B | .
Мощность объединения двух множеств:
Мощность объединения трех множеств:
Доказательство:
Мощность объединения
множеств:
Теорема. 
-
некоторые множества,
тогда мощность
объединения
множеств определяется
по формуле
Правая часть этой
формулы является суммой
слагаемых, 
-е
по порядку слагаемое имеет вид 
,
где 
есть
сумма чисел мощностей 
по
всем возможным пересечениям k
разных множеств из множеств
Пример. На потоке из 100 студентов 28 человек изучают английский язык, 30 человек - немецкий язык, 42 человека - французский язык. Причем 8 человек изучают два языка - английский и немецкий, 10 человек изучает английский и французский языки, 5 человек - немецкий и французский языки. 3 человека изучают все 3 языка. Сколько студентов не изучает ни один из перечисленных языков?
Пусть 
- множество студентов, 
(студентов). 
- множество студентов,
изучающих английский
язык, 
; 
- множествостудентов,
изучающих немецкий язык 
, 
- множество студентов,
изучающих французский язык, 
.
Соответственно множества студентов,
изучающих по 2 или 3 иностранных языка
заданы следующим образом: 
.
- множество студентов,
изучающих иностранные языки.
-
множество студентов, не изучающих
иностранный язык.
