Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 11
Текст из файла (страница 11)
Опишите множество (а,Ь,с,с1,е,г", д, Ь,г, 7) при помощи характеристического свойства. 7. Опишите множество (Огайо, Оклахома, Орегон) при помощи характеристического свойства. 8. Опишите множество (1,4,9, 16,25, 36,...) при помощи характеристического свойства. 9. Перечислите подмножества множества (а). 10. Перечислите подмножества множества (а, 6), 11.
Перечислите подмножества множества (а, Ь,с). 12. Перечислите подмножества множества (а, Ь, с, с1). 13. Перечислите подмножества множества о. 14. Используя результаты пяти предыдуших упражнений, определите число подмножеств для множества, состоящего из п элементов. 15. Установите истинность или ложность каждого из следующих утверждений: а) ОСИ; б) ОСЫ; в) ИЕЫ; г) О С А, где А — произвольное множество; д) 2~ Е А, где А — произвольное множество. 16.
Установите истинность или ложность каждого из следующих высказываний: а) (2) Е (1,2,3,4,5); б) (2) С (1,2,3,4,5); в) а=(а); г) (1,2,3) Е (1,2,3,(1,2,3Ц; д) (1,2,3) С (1,2,3,(1,2,3Ц. 17. Определите количество элементов в каждом множестве: а) (И, (ЯЦ; б) ((и, (я))); в) (1,2,3,(1,2,3Ц; г) (И, (О), а,6, (а, Ь), (а, Ь, (а,6)Ц; ) (2,(а),(2,(2 Ц) РКЗЛЕЛ 2.2. Операции над мноагестеами 71 2.2. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Рассмотренные ниже операции над множествами позволяют строить новые множества, используя уже существующие. ОПРЕДЕЛЕНИЕ 2.5. Пересечением множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и А, и В.
Пересечение множеств А и В обозначается АПВ. Это определение равносильно следующему: А О В = (х: х е А и х е В). Например, если А = (1,2,3,4,5) и В = (1,3,5,7,9), тогда АОВ = (1,3,5). Если С = (х: х имеет рост выше 180см) и Р = (х: х любит играть в шахматы), тогда С и Р = (х: х имеет рост выше 180см и любит играть в шахматы). Обратите внимание, что в описании пересечения множеств В О С использована связка "и". В дальнейшем мы убедимся, что символы О и Л, введенные в главе 1, связаны между собой и имеют схожие свойства. Определим пересечение трех и более множеств. Пусть Аы Аг и Аз — множества.
Их пересечение можно определить следующим образом: В = А1П(Аг ПАз). Далее будет показано, что А1 П (Аг й Аз) = (А, О Аг) П Аз, поэтому можно использовать запись В = А1 Г1 Аг П Аз . Очевидно, х е В тогда и только тогда, когда х е Аы х е Аг и х 6 Аз, иными словами, х е В тогда и только тогда, когда х принадлежит всем трем множествам Аы Аг и Аз. Пусть 7 = (1,2,3). В таком случае х 6 В тогда и только тогда, когда х Е Аг для всех 7' Е,7, что равносильно записи В=(х:хЕАу для всех7 е.г).
Пересечение множеств в общем случае определяется следующим образом. Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А или В. Объединение множеств А и В обозначается А н В. Сформулированное выше определение можно записать так: А 1з В = (х: х 6 А или х 6 В). ПРИМЕР 2.7. Например, если А = (1,2,6,7), а В = (2,3,5,6), тогда А сз В = (1,2,3,5,6,7). Объединение АсВ образовано из А и В путем соединения вместе элементов А и В. П 72 ГЛАВА 2. Теория множеств Если А = (х: х — политик), а В = (х: х — выпускник колледжа), то А О В = (х: х — политик или выпускник колледжа).
Обратите внимание, что в описании объединения А О В использована связка "или" так же, как в описании пересечения множеств использована связка "и". Объединение множеств Аы Аз и Аз определяется следующим образом: В = А1 О (Аз и Аз) . Далее будет показано, что А, О (Аз О Аз) = (Аг О Аз) О Аз, поэтому можно использовать запись В = А|О Аз О Аз. Очевидно, х е В тогда и только тогда, когда х е А1 или х е Аз или х е Аз, иными словами, х е В тогда и только тогда, когда х принадлежит хотя бы одному из трех множеств Аы Аз или Аз.
Таким образом, х е В тогда и только тогда, когда для некоторого з Е (1,2, 3), х е Азп что равносильно записи В = (х: х е А для некоторого з е (1,2,3)). Объединение множеств в общем случае определим следующим образом. ОПРЕДЕЛЕНИЕ 2.9. Пусть А и В множества. Разностью множеств А — В называется множество всех тех и только тех элементов А, которые не содержатся в В. Или, что то же самое, А — В = (х; х е А и х ф В).
Симметрическая разность множеств А и В, обозначаемая А Ь В, есть множество (А — В) О ( — А). Например, если А = (1,2,4,6,7), а В = (2,3,4,5,6), то А — В = (1,7), а АЬВ есть множество (1, 3, 5, 7). Симметричная разность множеств А и В состоит из тех элементов, которые принадлежат в точности одному из двух множеств А или В. Если А = (х: х играет в теннис), а В = (х: х играет в гольф), то А — В = (х: х играет в теннис, но не играет в гольф). Множество А Ь В = (х: х играет только в теннис или играет только в гольф).
Обратите внимание на сходство со связкой "исключающее или" из главы 1. РАЗДЕЛ 2.2. Операции над множествами 73 Если СУ вЂ” множество положительных целых чисел, а А = (2,4,6,8,...)— множество всех четных положительных чисел, то А' = (1,3,5,7,...) — множество всех нечетных положительных чисел. Если 73 — множество всех букв английского алфавита, а Ъ' = (сче,г,о,и), то Ъ" — множество всех букв, обозначающих в английском языке согласный звук. Если А = (х: х — любитель научной фантастики), тогда А' = (х: х не любит научную фантастику).
Обратите внимание, что дополнение множества связано с символом в логике. В соответствии с определением равенство двух множеств может быть установлено в два этапа. Докажите, что первое множество есть подмножество второго. Докажите, что второе множество есть подмножество первого. Этот способ используется, например, в доказательствах приведенных ниже теорем. Первый случай расписан более подробно. ТЕОРЕМА 2.11. Для произвольных множеств А и В справедливо равенство А — В=АйВ'. ДОКАЗАТЕЛЬСТВО. Для доказательства равенства двух множеств нужно показать, что каждое из множеств является подмножеством другого. Это можно осуществить, выбирая произвольный элемент одного множества и доказывая, что он принадлежит другому множеству.
Такое доказательство гораздо легче провести, следуя приведенным ниже рассуждениям, поскольку в них каждый шаг обратим. а Е А — В еь (а Е А) л(а ф В) се определение разности А — В еь (а е А) А (а е В') е=~ определение дополнения с-.» а Е (А О В'). определение пересечения Обратите внимание, что при доказательстве следующей теоремы один из законов логики — закон де Моргана — существенно используется для доказательства соответствующего закона де Моргана в теории множеств. ТЕОРЕМА 2.12. Для произвольных множеств А и В имеет место а) (АПВ)' = А'ОВ', б) (А О В)' = А' й В'.
ДОКАЗАТЕЛЬСТВО. Ниже приведено доказательство части (а). Доказательство части (б) предоставляется читателю. Как и в предыдущем доказательстве, мы покажем, что каждое из множеств, входящих в равенство, есть подмножество другого. а Е (А Г) В)' <=> а р (А Г1 В)' с=: определение дополнения (а Е (А О В)) се определение )е еь ((а е А) А (а е В)) с=~ определение пересечения 74 ГЛАВА 2. Теория множесгпв (аЕА)Н (аЕВ) Е» с=» (а ф А) и (а ф В) «» «» (а Е А') ~/ (а Е В') «» »» а Е (А' О В'). закон логики де Моргана определение ф определение дополнения определение объединения а Е А О (В О С) е» (а Е А) Л (а Е (В О С)) с=» с=» (а Е А) Л ((а Е В) ~l а Е С)»» Е» ((а Е А) Л (а Е В)) Ч ~/ ((а Е А) Л (а Е С)) ~ <=» (а Е (А П В)) ~/ (а Е (А Г1 С)) «» с=» а е ((А и В) О (А ОС)) е» С=» (а Е А') О (а Е В').
определение пересечения определение объединения определение пересечения закон логики де Моргана определение пересечения определение ф определение объединения Мы убедились, что свойства, доказанные в теории множеств, имеют свой аналог в логике. В разделе 2А при рассмотрении булевой алгебры будет дано обобщение как операций теории множеств, так и логических операций. ОПРЕДЕЛЕНИЕ 2.14.
Множество всех подмножеств множества А, или бу- леан множества А, обозначаемый Р(А), есть множество, состоящее из всех подмножеств множества А. Следовательно, булеан множества А = (1,2,3) есть множество Р(А) = (а, (Ц, (2), (3), (1,2), (2,3), (1,3), (1,2,3)). Когда А содержит 3 элемента, Р(А) состоит из 2з = 8 элементов или, что то же самое, А включает 2з = 8 подмножеств.
Это будет показано в главе 8. В общем случае, если А содержит и элементов, множество Р(А) включает 2" элементов, т.к. А имеет 2" подмножеств. По этой причине Р(А) часто обозначают через 2". Еще одной часто используемой операцией над множествами является декартово произведение, которое определяется следующим образом. Обратите внимание, что при доказательстве следующей теоремы логический закон дистрибутивности существенно используется для доказательства соответствующего закона дистрибутивности в теории множеств. ТЕОРЕМА 2.13. Для произвольных множеств А, В и С справедливы равенства а) АО(ВОС) = (АОВ) и(АйС); б) АО (ВГ1 С) = (А О В) Г1(АСС).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
