XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 5
Текст из файла (страница 5)
Предикат, задающий коллективизирующее свойство, может быть тождественно ложным. Множество, определенное таким образом, не будет иметь ни одного элемента. Его называют пусенмм множестпвом и обозначают Я. В противоположность этому тождественно истинный характеристический предикат задает универсальное множество. Обратим внимание на то, что не каждый предикат выражает какое-то коллективизирующее свойство (см. Д.1.1). 32 1.
МНОЖЕСТВА И ОТНОШЕНИЯ множествами, то в качестве универсального может фигурировать множество й всех действительных чисел. В каждом разделе математики рассматриваетсл относительно ограниченный набор множеств. Поэтому удобно полагать, что элементы каждого из этих множеств суть также и элементы некоторого „объемлющего" их универсального множества. Зафиксировав универсальное множество, мы тем самым фиксируем область значений всех фигурирующих в наших математических рассуждениях переменных и констант.
В этом случае как раз и можно не указывать в кванторах то множество, которое пробегает связываемое квантором переменное. В дальнейшем изложении мы встретимся с разными примерами конкретных универсальных множеств. Рассмотрим операции над множествами, которые позволяют иэ уже имеющихся множеств образовывать новые множе. ства [1]. Для любых двух множеств А и В определены новые множества, называемые объединением, пересечением, разностпью и симметпрической разностпью: АОВ = (х: х Е АЧх Е В), АПВ=(х: х 6АЛхеВ), А~В =1х: х ЕАЛхфВ), АЬВ = (А~В) 0(В~А), т.е.
объединение А и В есть множество всех таких х, что х является элементом хотя бы одного из множеств А, В; пересечение А и  — множество всех таких х, что х — одновременно элемент А и элемент В; разность А ~  — множество всех таких х, что х — элемент А, но не элемент В; симметрическая разность А Ь В вЂ” множество всех таких х, что х — элемент А, но не элемент В или х — элемент В, но не элемент А.
Кроме того, фиксируя универсальное множество У, мы можем определить дополнение А мнозхестпеа А следующим образом: А = У '1 А 11]. Итак, дополнение множества А— зто множество всех элементов универсального множества, не принадлежащих А. Полезно разобраться в том, как операции над множествами, введенные вьппе, соотносятся с логическими операциями. Пусть А = (ас Р(я)), В = (ас Я(х)), т.е. множество А задано посредством характеристического предиката Р, а множество  — посредством характеристического предиката Я. Легко показать, что АОВ = (х: Р(я)ЧЯ(я)), АПВ = (х: Р(х) ЛЯ(х)), А ~ В = ~я: Р(я) Л вЂ” Я(х) ) .
А = В сь ((А С В) л (В С А)). (1.2) Формула (1.2) является основой для построения доказательств о равенстве множеств. Ее применение состоит в следующем. Чтобы доказать равенство двух множеств Х и У, т.е. Следующие процедуры получения новых множеств связаны с понятием подмножества. Говорят, что В есть подмножество множества А, если всякий элемент В есть элемент А. Для обозначения используют запись: В С А.
Говорят также, что В содержится в А, В включено в А, А включает В (имеет место включение В С А). Считают, что пустое множество есть подмножество любого множества и, если фиксировано некоторое универсальное множество, каждое рассматриваемое множество есть его подмножество. Нетрудно проверить, что если А = 1я: Р(х)), В = 1х: Я(х)), то В С А тогда и только тогда, когда высказывание Я(х) =ь Р(х) тождественно истинно. Сопоставляя определение подмножества и определение равенства множеств, мы видим, что множество А равно множеству В тогда и только тогда, когда А есть подмножество В и наоборот, т.е.
34 1. МНОЖЕСТВА И ОТНОШЕНИЯ что Х = У, достаточно доказать два включения Х С У и У С Х, т.е. доказать, что из предположения х Е Х (для произвольного х) следует, что х Е У, и, наоборот, из предположения х Е У следует, что х Е Х. Такой метод доказательства теоретико- множественных равенств называют метподом двух включений. Примеры применения этого метода мы дадим позже. Замечание. Равенство множеств (х: Р(х)) и (хс Я(х)) означает, что предикаты Р(х) и Я(х) эквивалентны, т.е. предикат Р(х) с-.> Я(х) является тождественно истинным.
ф Если В С А, но В ф А, то пишут В С А и В называют стпрогнм подмножестпвом (или собстпвенным подмножеством) множества А, а символ с — символом стпрогого включекил. Для всякого множества А может быть образовано множество всех подмножеств множества А. Его называют булеаком множестпва А и обозначают 2А: 2А (Х. ХС А) Для булеана используют также обозначения Р(А), В(А) и ехр(А).
Пример. а. Булеан множества (а, Ь) состоит из четырех множеств И, (а), (6), (а, Ь), т.е. 2<од) = (ю', (а), (Ь), (а, ЬЦ. б. Булеан 2" состоит из всех возможных, конечных или бесконечных, подмножеств множества И. Так, И Е 2", (5) Е Е 2н, вообще для любого и множество (и) Е 2н, множество (1, ..., и) Е 2~, (и: п = 2й, Ь = 1,2,...) Е 2" и т.п. Для булеана 2А мы можем рассматривать произвольные его подмножества. Таким подмножеством, например, будет однозлементное множество (В), где  — произвольное подмножество А. Подчеркнем, что единственным элементом множества (В) является, в свою очередь, некоторое множество. Вообще же образование булеана открывает путь для построения множеств, элементами которых являются множества, элементами 35 1.1.
Множества которых, в свою очередь, являются некоторые множества, и эл ээ т.д. Так можно определить множества 2, 2 и т.д.' Введенные вьппе операции над множествами обладают следующими свойствами: 1) АцВ=В0А; 2) АПВ=ВПА; 3) Ац(вцс) =(Ацв) ЦС; 4) Ай(ВПС) =(АЙВ)йС; 5) АП(ВцС) =(АПВ)0(АПС); 6) А 0 (В П С) = (А 0 В) П (А 0 С); 7) АЦВ=АПВ; 8) АПВ=АЦВ; 9) АЦЗ= А; 10) Айя = И; 11) Апов=А; 12) АЦУ=У; 13) АЦА= У; 14) АпА= ы; 15) АЦА=А; 16) АПА=А; 17) А=А; 18) А~В=АПВ; 19) АЛВ = (АцВ) ~(АПВ); 20) (АЛВ) ЛС= АЛ(ВЛС); 21) АйВ=ВЬА; 22) Ай(ВЬС) =(АПВ)Ь(АПС).
'Примеюы теорюо множеств, часто выстраивают подобные „баюви" булеанов, начинал этот процесс с элементов, не рассматриваемых как множества. Такие элементы называют праэлементами. Далее в качестве праэлементов берутсл любые числа, а также такие объекты, как константы, переменные, буквы какого-нибудь алфавита и т.п. 36 1.
МНОЖЕСТВА И ОТНОШЕНИЯ Каждое из написанных вьппе равенств, верное для любых входящих в них множеств, часто называют теореепико множественным ьпождеством. Любое из них может быть доказано методом двух включений. Докажем этим методом тождество 19. Пусть х Е АЬВ. Тогда, согласно определению симметрической разности, х Е (А 1 В) 0 (В '1 А). Это означает, что х Е Е (А~В) или х Е (В~А). Если х Е (А~В), то х Е А и х ФВ, т.е. х Е А О В и при этом х к А О В. Если же х Е (В 1 А), то х Е В и х Ф А, откуда х Е АО В и х к А О В. Итак, в любом случае из х Е (А ~ В) 0(В ~ А) следует х Е А О В и х и А 0 В, т.е. х Е (АОВ) 1(АПВ). Таким образом, доказано, что АЬВ С (АОВ) 1(АОВ). Покажем обратное включение (А 0 В) ~ (АП В) С АЛВ.
Пусть х Е (АОВ) 1(АОВ). Тогда х Е АОВ и х фАПВ. Из х е А 0 В следует, что х Е А или х й В. Если х Е А, то с учетом х ф А П В имеем х ф В, и поэтому х Е А 1 В. Если же х Е В, то опять-таки в силу х к А й В получаем, что х к А и х Е В ~А. Итак, х Е А~В или х Е В ~А, т е. х Е (А~В) 0(В~А). Следовательно, (АОВ) ~(АОВ) С АЬВ. Оба включения имеют место, и тождество 19 доказано. Метод двух включений являетсл универсальным и наиболее часто применяемым методом доказательства теоретико- множественных тождеств. Помимо метода двух включений для доказательства теоретико-множественных тождеств могут быть использованы другие методы, например метиод хараки)еристпических функций (см. Д.1.2).
Кроме того, теоретико-множественные тождества можно доказывать, используя ранее доказанные тождества для преобразования левой части к правой или наоборот. Такой метод 37 1.2. Кортех. Деиартово произведение доказательства часто называют мепзодом эмеиваленпзмыэ фзреобраэовамий. Докажем этим методом тождество 22, пользуясь тождествами 1-19. Преобразуем левую часть к правой: (АПВ)Ь(АПС) =((АПВ)0(АПС)) П(АПВ)П(АПС) = = (А П (В 0 С) ) П ((А й В) 0 (А П С)) = = (Ай(ВОС)) П(АОВ) О(АОС) = = (А П (В О С)) й (А 0 (В 0 С)) = = ЦА П (В 0 С) ) П А) 0 ((А й (В 0 С) ) П (В 0 С) ) = = ИО((АП(В ОС)) П(АП (В ОС))) = = (А П (В 0 С)) й (А й (В П С) ) = =АП((ВОС)П(ВПС)) = =Ай((ВОС) 1(ВПС)) = Ай(ВсХС).
Тождество доказано. 1.2. Кортеж. Декартово произведение Пусть А и  — произвольные множества. Неуоорлдочеимав нара на множествах А и  — это любое множество (а, Ь), где а е А, Ь е В или а е В, Ь е А. Если А = В, то говорят о неупорядоченной паре на множестве А. Исходя из понятия равенства,иноэсесже, можно утверждать, что неупорядоченная пара (а, Ь) равна неупорядоченной паре (с, д) если и только если а = с и Ь = д или а = 4 и 6 = с. Заметим,что равенство элементов множества понимается здесь (и далее в аналогичных ситуациях) как равенство иидивидных константа.
В том случае, когда в неупорядоченной паре (а, 6) элементы а и Ь совпадают, получаем, что (а, Ь) = (а, а). Но такая запись, как мы условились вьппе, задает то же самое множество, что и (а). Таким образом, при а = Ь неупорядоченная пара (а, Ь) 38 1. МНОЖЕСТВА И ОТНОШЕНИЯ „вырождается" в одноэлементное множество (а). При а ф Ь неупорядоченная пара будет двухэлементным множеством. Упорлдоченнал пара на множествах А и В, обозначаемая записью (а, Ь), определяется не только самими элементами а е А и 6 Е В, но и порядком, в котором они записаны. И в этом состоит ее существенное отличие от неупорядоченной пары.
Если А = В, то говорят об упорядоченной паре на множестве А. Существенная роль порядка, в котором перечисляются элементы упорядоченной пары, фиксируется определением равенства упорядоченных пар. Определение 1.1. Две упорядоченные пары (а, 6) в (а', Ь') на множествах А и В называют равными, если а = а' и 6 = Ь'. Замечание 1.2. Упорядоченную пару (а, 6) не следует связывать с множеством (а, Ь), так как упорядоченная пара характеризуется не только составом, но и порядком элементов в ней. Более того, определение этого объекта вообще не позволяет рассматривать его как множество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
