booklet_for_print
.pdf2. Второй закон де Моргана
Дополнение пересечения А и В эквивалентно объединению дополнения А и дополнения В.
А В А В (7)
Левая часть равенства:
А В
А В
Правая часть равенства:
А |
В |
А |
В |
А |
В |
|
|
А |
В |
А В
22
2.Ассоциативность:
АВ С А В С
3. Идемпотентность: |
А |
|
А А А |
||
|
4. Если B A , то А В А
А В
Операция объединения определяется для любого количества множеств. Объединением нескольких множеств называется множество, которое состоит из всех элементов всех данных множеств и не содержит никаких других элементов.
3.2.Пересечение множеств
Если даны два множества, то можно образовать новое множество, составленное из их общих элементов. Общая часть этих множеств называется их пересечением. Пересечение множеств обозначается с помощью знака пересечения: Множества называются непересекающимися, если у них нет общих элементов, т.е. их пересечение пусто ( ).
11
Примеры:
1.А= 1,2,3 В= 2,3,4 . Пересечение множеств А и В обозначается так: А В= 1,2,3 2,3,4 = 2,3
2.М = 2,5 ; N = 3,4
M N =
3.А = В,А,С,Я ; В = И,В,А,Н,О,В
А В = В, А
4.М = x|5 x 10 ; N = x| 3 x 8 M N = x| 5 x 8
С помощью диаграмм Эйлера – Венна пересечение множеств изображается так:
С А В с |
|
с А и с В |
|
||
|
|
|
А С В
Определение: Пересечением двух множеств А и В называется такое множество С, которое состоит из всех элементов, содержащихся как в множестве А, так и в множестве В и не содержит никаких других элементов.
Из определения пересечения следует, что характеристическое свойство элементов множества А В составляется из характеристических свойств пересекаемых множеств с помощью союза «и».
Примеры:
1. Множество А – множество четных натуральных чисел, множество В – множество двузначных чисел. Характеристическое свойство элементов множества А – «быть четным натуральным числом», а характеристическое свойство элементов множества В – «быть двузначным числом». Тогда элементы пересечения данных множеств должны обладать свойством «быть четными и двузначными натуральными числами».
Другой вариант определения дополнения:
Дополнением множества А называется множество, которое состоит из тех и только тех элементов универсального множества, которые не входят в А.
A x x A , x E
Законы де Моргана
Именем де Моргана называются логические законы, связывающие дополнение объединений или пересечений множеств с дополнениями самих множеств.
Де Морган (de Morgan) (1806–1871) – шотландский математик и логик, который независимо от Джорджа Буля пришел к основным идеям математической логики.
Джордж Буль (Boole) (1815 –1864) – английский математик и логик, один из основоположников математической логики.
1. Первый закон де Моргана
Дополнение объединения А и В эквивалентно пересечению дополнения А и дополнения В.
A B A B (6)
Для иллюстрации используем диаграммы:
Левая часть равенства:
А В |
А В |
А В |
А В |
Правая часть равенства:
А |
В |
А |
В |
А В |
|
А |
|
В |
А В |
|
|
|
|
12 |
21 |
Определение: Множество E \ A называется дополнением А до Е и
обозначается чертой вверху: A
|
|
|
|
|
|
|
|
|
|
|
|
|
A E \ A |
|
|
|
|
||||||
Диаграмма Эйлера-Венна выглядит так: |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
Свойства дополнения: |
|
А |
А |
||||||||
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1. |
|
|
A A E |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
2. |
|
|
A A |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
||
3. |
|
= Е |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
||||
4. |
|
E = |
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
5. |
|
A A |
|
|
|
|
6. Если А В, то В А
7. Операции разности и дополнения связаны следующим образом:
A \ B B A
2. N – множество целых чисел, делящихся на 2, M – множество целых чисел, делящихся на 3. Тогда N M – множество целых чисел, делящихся на 6.
Свойства операции пересечения
1. Коммутативность
А В В А С
А С В
2.Ассоциативность
АВ С А В С
3. А А А |
А |
В А
4. Если А В , то А В А
Подобно объединению, операция пересечения определяется и для произвольного количества множеств. Пересечением нескольких множеств называется множество, которое состоит из всех элементов, содержащихся одновременно во всех данных множествах и которое не содержит никаких других элементов.
20 |
13 |
Для объединения и пересечения справедливы следующие свойства
дистрибутивности:
Теорема 1.
Для операции объединения множеств относительно операции пересечения множеств справедлив закон:
А В С А В А С |
(1) |
|
|
Проиллюстрируем эту теорему на диаграммах: Левая часть равенства: А В С
Правая часть равенства: А В А С
Представленные диаграммы наглядно показывают верность равенства (1). Теперь докажем это.
Доказательство:
Обозначим левую часть равенства (1) буквой Р, а правую буквой Q:
P A B C и Q A B A C .
Нам нужно доказать, что P=Q.
14
Так как y C , получаем, что y A \ B C , т.е. y P , а значит,
Q P.
Таким образом, мы доказали равенство P и Q, а значит и формулу (3).
Теорема 2.
Операции разности антидистрибутивны относительно операций объединения и пересечения:
A \ B C A \ B A \ C |
(4) |
|
|
|
|
A \ B C A \ B A \ C |
(5) |
|
|
3.4. Дополнение
Основное (универсальное) множество
Очень часто все рассматриваемые в какой-либо задаче множества являются подмножеством некоторого множества, которое мы будем называть основным (универсальным) и обозначать Е.
На диаграммах Эйлера-Венна универсальное множество Е изображается прямоуголь- Е А ником, ограничивающим рисунок. Пусть А – подмножество множества Е.
Свойства универсального множества
1.Е = Е
2.Е =
3.Е Е Е Е Е
4.Е \ Е
5.Е \ = Е
6.A E E
7.A E A
19
Пример:
Экзамен по математике сдавали 250 абитуриентов. Оценку ниже «5» получили 180 человек, а выдержали этот экзамен 210 абитуриентов. Сколько человек получили оценки «3» и «4» ?
Пусть А – множество абитуриентов, выдержавших экзамен (оценка выше «2»), В – множество абитуриентов, получивших оценки ниже «5» (оценки «2», «3», «4»). Абитуриенты, получившие оценки «3» и «4» образуют множество А В (т.е. оценки выше «2» и ниже «5»), по формуле Грассмана найдем |А В|.
|А|= 210 |В|= 180 |А В|= 250 |
|
A B |
|
|
|
A |
|
|
|
B |
|
|
|
A B |
|
|||
|
|
|
|
|
|
|
|
|||||||||||
|
A B |
|
= 210+ 180 – 250=140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ответ: 140 человек получили отметки «3» и «4».
Теорема 1.
Операции разности и пересечения связаны следующим соотношением дистрибутивности:
A \ B C A C \ B C (3)
Доказательство:
Обозначим левую часть равенства P, а правую Q:
P A \ B C ; Q A C \ B C
Для того, чтобы доказать теорему, необходимо и достаточно доказать, что P=Q, т.е. P Q и Q P .
1. Докажем, что P Q . Пусть x P . Тогда x A \ B и x C . Из того, что x A \ B следует, что x A и x B . Так как x C и x A , x A C . Так как x B , x B C . Из определения
разности следует, что x A C \ B C , т.е. x Q , а значит, P
Q.
2. Докажем, что Q P. Пусть y Q . Тогда y A C и
y B C . Т.к. y A C , y A и y C . Но y B C ,
значит, y B (иначе y B C )
Так как y A и y B , получаем, что y A \ B . 18
Из определения равенства двух множеств (§ 2) вытекает, что для доказательства равенства (1) надо установить два включения: P Q
и Q P .
1. Докажем, что P Q . Для этого следует показать, что любой элемент a P является элементом множества Q.
Пусть a P . Тогда так как P A B C , a A или a B C
a A |
a B C |
|
|
|
|
значит, a A B |
значит, a B и a C (исходя |
|
и a A C (исходя |
из определения операции |
|
пересечения) a B A и |
||
из определения операции |
||
a C A (исходя из |
||
объединения). Элемент a |
||
является общим для данных |
операции объединения. |
|
множеств, и, значит, |
Т.о. a B A C A , или |
|
принадлежит их пересечению: |
a A B A C , т. е. |
|
a A B A C , |
||
a Q |
||
|
||
т. е. a Q |
|
|
|
|
Таким образом, в обоих случаях a Q . То есть, мы доказали, что
PQ .
2.Докажем, что Q P . Пусть b Q A B A C . Тогда b A B и b A C . Здесь также возможны два случая:
b A |
b A |
|
|
значит, b A B C , т.е. |
значит, b A B C , т.е. b P |
b P |
т.к. b A B A C , но |
|
b A , значит b B и b C , т.е. |
|
b B C и, исходя из |
|
определения операции |
|
объединения, b B C A, а |
|
значит b P. |
|
|
|
15 |
Таким образом, в обоих случаях b P . То есть, мы доказали, что Q
P. Таким образом, установлена справедливость равенства (1), что
итребовалось доказать.
Теорема 2.
Для операции пересечения множеств относительно операции объединения множеств справедлив закон:
A B C A B A C (2)
Доказательство предлагается провести самостоятельно.
3.3. Разность множеств
Определение: Разностью множеств А и В называется множество, состоящее из элементов, принадлежащих множеству А, но не принадлежащих множеству В. Обозначается А\В. Графически разность двух множеств выглядит так:
|
|
А |
|
|
В |
|
|
|
|
|
А \ В |
|
|
|
|
|
|
Примеры: |
|
|
|
|
|
|
||
1. X={2,3,4} Y={1,3,5} |
X\Y={2,4} |
|
|
|
|
|||
2. А={В,А,Н,Я} В={М,А,Н,Я} А\В={В} В\А={М} |
|
|
||||||
3. M={x | 5<x<10} |
N={x | 7<x<15} |
|
|
|
|
|||
|
|
|
M |
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
7 |
10 |
15 |
|
х |
|
|
|
|
|
|
|
|
|
|
|
|
|
M\N |
|
|
|
|
|
M\N={x | 5<x<7} |
|
|
|
|
|
|
||
|
|
|
|
16 |
|
|
|
|
Свойства операции разности
1. |
X \ =Х |
|
|
2. |
X \ X |
|
|
3. Если X Y = , то X \ Y X |
X |
Y |
|
|
|
4. Если X Y , то X \ Y = |
Y |
X |
При решении задач часто приходится определять мощность объединения двух или нескольких множеств.
1. |
Если A B = , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
то |
|
A B |
|
|
|
A |
|
|
|
B |
|
A |
|
|
|
|
|
|
|
B |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
2. |
Если A B , |
|
|
|
B |
|
|
|
|
|
|
|
A |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
то |
B \ A |
B |
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
3. Если A B , то верна формула |
|
A B |
|
|
|
A |
|
|
|
B |
|
|
|
A B |
|
, |
||||||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
которая называется формулой Грассмана в честь немецкого математика Германа Грассмана (Grassmann (1809–1887)), а также формула A B A B A B
Эти формулы часто используются при нахождении числа элементов множества, заданного несколькими условиями.
17