Н

9. AUU = U

10. АП 0 = 0

11. АпС/=А

12. AU 0 =А

7. А П (В U С) = (А П В) U (А П С)

8. A U (В П С) = (A U В) П (A U С)

1. A U А = А

2. АпА = А

3. A U В = В U А

4. АпВ = ВпА

5. A U (В U С) = (A U В) U С

6. А П (В П С) - (А П В) П С

Законы для объединения и пересечения:

иже перечислены основные законы, действующие в булевых алгеб­рах.

Законы для дополнений:
1. А = А	4. (A U В) = А П В
2.AUA = U	5. (АП В) = AU В
3. АПА = 0	6 .U = 0

Законы для разностей множеств:
1.А\В=АПВ	6. А\А = 0
2 .U\A=А	7. ((А \ В) \ С) = А \ (В U С)
3.A\U= 0	8. А \ (В \ С) = (А \ В) U (А П С)
4. А \ 0 = А	9. A U (В \ С) = (A U В) \ (С \ А)
5. 0 \А = 0	10. А П (В \ С) = (А П В) \ (А П С)

Доказательство каждого из перечисленных законов основано на опре­делении равенства множеств и определений операций над множествами. Напомним, что множество А равно множеству В, если они состоят из од­них и тех же элементов или оба пусты. Докажем один из законов для дополнений: A U В = А П В.

Пусть х G A U В. По определению операции дополнения это означает, что х 0 AUB, нод: G U. Следовательно, х 0 А и одновременно х 0 В. Таким образом, х G А и х G В. Из определения операции пересечения получаем, что х G А П В. Поэтому, учитывая произвольность элемента х G A U В, имеем АиБ С А П В.

Пусть теперь х € А П В. Это значит, что х G А и х € В. Таким образом, х $ А и х 0 В. Поэтому x^AUB. Следовательно, х G U \ (A U В) = (A U В). Поскольку х — произвольный элемент из АПВ, то окончательно получаем А П В С A U В".

Приходим к выводу, что А П В = A U В.

19. Третье практическое занятие по теме «Операции над множествами»

Задача 1. Для каких из следующих пар множеств имеет место одно из соотноше­ний: А с В] В С А; А = В:

1. А = {а, Ь, с, d}; В = {а, с, d}, 2) А = 0; В = 0,

3. А = 0; В = {а, Ъ, с}; В = {Ь, с, а}?

Задача 2. Даны множества А = {0,1,2,3,4, 5,6, 7}; В = {3,4, 5,6, 7,8,9}; С = {—3, —2, —1,0,1,2,3,4}; D = {2, 3,4, 5,6}. Задайте списками множества:

1. A U В U С U В; 2) АП ВП С Л В; 3) (А П В) U (С П В); 4) (A U В) П (С U В); 5) (А \ В) U (В \ А).

Задача 8. Изобразите с помощью диаграмм Эйлера-Венна множества:

1. А С В и В с С; 2) А С В; В с С и А \ В = 0; 3) А с В; В с С и С = A U В;

3. АсВ;ВсСиАпВ^0; 5) (А \ В) U (В \ А).

Решение. Изобразим с помощью диаграммы Эйлера- Венна множество

(А \ В) U (В \ А)

(см. рис. 2.7).

Это множество является объединением двух разностей, называется симме­трической разностью и обозначается А © В, т. е. (А \ В) U (В \ А) = А © В.

Задача 4. Опрос 100 студентов дал следующие результаты о количестве студен­тов, изучающих различные иностранные языки: испанский — 28; немецкий — 30; французский — 42; испанский и немецкий — 8; испанский и французский — Ю; немецкий и французский — 5; все три языка — 3.

а) Сколько студентов не изучает ни одного языка?

б) Сколько студентов изучает один французский язык?

в) Сколько студентов изучает немецкий язык в том и только в том случае, если они изучают французский язык?

Решение. Нарисовать диаграмму Эйлера-Венна в виде трех кругов, обозначаю­щих множество студентов, изучающих соответственно французский, немецкий и испанский языки. В каждую из восьми областей вписать данные, используя приведенные цифры. Начинать с конца списка и двигаться к началу.

Ответ: а) 20; б) 30; в) 38.

Задача 5. Следующий опрос 100 студентов (см. задачу 4) выявил следующие данные о числе студентов, изучающих различные иностранные языки: только немецкий — 18; немецкий, но не испанский — 23; немецкий и французский — 8; немецкий — 26; французский — 48; французский и испанский — 8; никакого языка — 24.

а) Сколько студентов изучают испанский язык?

б) Сколько студентов изучают немецкий и испанский языки?

в) Сколько студентов изучают французский язык, в том и только в том слу­чае, если они не изучают испанский?

Ответ: а) 18; б) ни одного; в) 50.

Задача 6. В отчете об опросе 100 студентов (см. задачу 4) сообщалось, что ко­личество студентов, изучающих различные языки, таково: все три языка — 5; немецкий и испанский — 10; французский и испанский — 8; немецкий и фран­цузский — 20; испанский — 30; немецкий — 23; французский — 50. Инспектор, представивший этот отчет, был уволен. Почему?

Задача 7. Докажите, пользуясь диаграммой Эйлера Венна, что высказывание X V (X V У) — логически истинно.

Решение. Этому высказыванию соответствует множество A l.J (A U В), отвечающая ему диаграмма изображена на рис. 2.8.

Множество А заштриховано вертикальными линиями, а множество A U В — горизонтальными. Вся заштрихованная область является их объединением и совпадает с множеством U, так что наше составное высказывание логически истинно.

Задача 8. Воспользовавшись диаграммой Эйлера Венна, определите, какие из следующих высказываний логически истинны:

а) X V X; б) X Л X; b)XV(XAY); г)Х-*ДУ->Х); д)ХЛ(УчХ). Ответ: (а) и (г) — логически истинны, (б), (д) — логически ложны.

Задача 9. Докажите, пользуясь диаграммой Эйлера Венна, что X V (Y Л Z) экви­валентно (X V Y) Л (X V Z).

Решение. Множество истинности высказывания X V (Y Л Z) совпадает со всей заштрихованной областью на диаграмме слева, а множество истинности выска­зывания (X V Y) Л (X V Z) совпадает с дважды заштрихованной областью на диаграмме справа (см. рис. 2.9).

Так как эти множества совпадают, то наши два высказывания эквива­лентны.

Задача 10. Покажите, пользуясь диаграммой Эйлера-Венна, что из Y следует X -)■ Y.

Решение. Множество истинности высказывания X ч Y совпадает с заштрихо­ванной областью на диаграмме (см. рис. 2.10).

Так как эта заштрихованная область включает в себя множество В, то мы видим, что из Y следует X —> Y.

Задача 11. Найдите множества истинности каждого высказывания и, восполь­зовавшись диаграммой Эйлера—Венна, определите, какие из выписанных ниже пар высказываний состоят из высказываний, одно из которых является след­ствием другого:

а) X; X AY; б )XAY;X->-Y в) XY; YX; г) X Л Y; X Л Y.

Задача 12. Три или более высказывания называются несовместимыми, если они не могут быть истинными все сразу. Что можно сказать о множествах истинности таких высказываний?

Задача 13. Для следующих трех составных высказываний:

а) введите буквенные обозначения для компонент;

б) дайте символическое выражение;

в) найдите множества истинности;

г) проверьте их совместимость.

Если этот курс интересен, то я буду упорно над ним работать. Если этот курс не интересен, то я получу по нему плохую отметку. Я не буду упорно работать, но получу по этому курсу хорошую отметку.

Ответ: Несовместимы.

Задача 14. Каждому множеству поставьте в соответствие высказывание, имею­щее это множество своим множеством истинности, и, воспользовавшись табли­цами истинности, определите, какие из следующих множеств пусты:

а) (АиВ)П(Аи В); б) (AnB)U(BU С); в)(АПВ)\А; г) (Ли С) П (A U В). Ответ: (б) И (в).

Задача 15. Каждому множеству поставьте в соответствие высказывание, имею­щее это множество своим множеством истинности, и, воспользовавшись табли­цами истинности, определите, являются ли попарно различными следующие множества:

а)АП (ВUС); б)(С\ В)U (BUС); в)(СиВ)П(СU В); г)(АП В)U(АпС);

д) (А П В П С) U (А П В П С) U (А П В П С) U (А П В П С).

Задача 16. Каждому множеству поставьте в соответствие высказывание, име­ющее это множество своим множеством истинности, и, воспользовавшись таб­лицами истинности, определите, в каких из следующих пар множеств одно из множеств является подмножеством другого:

а) А; АП В; б)АПВ;ВПА; в )А\В;В\А; г)АПВ;АиВ.

Задача 17. Докажите, как с помощью таблиц истинности, так и с помощью диа­граммы Эйлера-Венна, что высказывание X A (Y V Z) эквивалентно высказыва­нию (X Л Y)V (X A Z).

Задача 18. Проверьте все законы операций над множествами для объединения и пересечения с помощью диаграмм Эйлера-Венна. Переведите эти законы в зако­ны для составных высказываний. Проверьте их с помощью таблиц истинности.

Задача 19. Проверьте все законы операций над множествами для дополнений и для разностей с помощью диаграмм Эйлера-Венна, переведите их в законы для составных высказываний и проверьте их с помощью таблиц истинности.

Задача 20. Из законов булевой алгебры над множествами получите следующие результаты:

а)А = (АПВ)и(АПВ); б)АиВ = (AnB)U(AnB)U(AnB); в)АП(Ап£)=А;

г)Аи(АПВ)=АиВ.