Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 12
Текст из файла (страница 12)
ДОКАЗАТЕЛЬСТВО. Ниже приведено доказательство части (а). Доказательство части (б) предоставляется читателю. Опять покажем,что каждое из множеств, входящих в равенство, есть подмножество другого. РКЭУ2ЕЛ 2.2. Оперении над иножестваии 75 ОПРЕДЕЛЕНИЕ 2.15. Декартово лроиэведение множеств А и В, обозначае- мое А х В, есть множество ((а, Ь): а я А и Ь е В).
Объект (а,6) называется упорядоченной ларой с первой компонентой а и второй компонентой Ь. А х В = ((1, г), (1, в), (2, т), (2, в), (3, г), (3, в)). Если каждое из множеств А и В представляет собой множество действительных чисел, то А х В представляет собой декартову плоскость, на которой упорядоченные пары чисел используются для графического изображения функций. Если А содержит п элементов, а В содержит гп элементов, тогда Ах В содержит и гл элементов. В частности, если А пусто или В пусто, то, по определению, А х В пусто.
° УПРАЖНЕНИЯ 1. Пусть А = (1,2,3,4,5,6,7), В = (4,5,6,7,8,9,10), С = (2,4,6,8,10), а ьУ = (1,2,3,4,5,6,7,8,9,10). Определите следующие множества: а) АСС; б) АОВ; в) Аг1(В ОС); г) (АОВ) ОС; д) (А П В)', е) А'ОВ', ж) АЬВ; з) А — В. 2. Пусть А = (1,2,3,4,5,6,7), В = (4,5,6,7,8,9,10), С = (2,4,6,8,10), а У = (1,2,3,4,5,6,7,8,9,10). Определите следующие множества: а) А — С; б) (А — В) О ( — А); в) Аг1(ВпС'); г) (А О С) — В', д) (А — И) О (А — А); е) ВЬС; ж) С вЂ” А. 3. Пусть А = (1, 2,3), а В = (а, 6). Определите а) АхВ; б) ВхВ; в) Аха. 4. Пусть А = (1,2,3), а В = (а, 6). Определите а) АхА; б) ВхА; 5. Определите Р(А), если А = о.
6. Определите Р(А), если А = (о, (о)). 7. Определите Р(Р(А)), если А = ы. 8. Определите, какие из следующих утверждений истинны, а какие ложны: а) АС1О=А; б) АЬА= о; в) если А С В, то А С1 В = А; г) если АОВ =А, то В с А; д) А — А=А; е) (А х В)' = А' х В'. в) АЬВ Множество А х В состоит из всех упорядоченных пар, имеющих в качестве первой компоненты элемент из А, а в качестве второй компоненты — элемент из В. По существу, это та же упорядоченная пара, которую мы обычно используем в алгебре. Порядок компонент в паре существенен! Например, рисуя график функции, мы знаем, что точка (1, 2) не совпадает с точкой (2, 1).
Пусть А = (1,2,3), а В = (г,в). Тогда 76 ГЛАВА 2. Теория множеств 9. Определите, какие из приведенных утверждений истинны, а какие ложны: а) АХИ=А; б) АЛО=А; в) если АСВ, то АОВ=А; г) если А О В = А, то В С А; д) А — Я=А. 10. Докажите, что А О (В О С) = (А О В) й (А О С) 11. Докажите, что (А О В)' = А' ПВ'.
12. Определим (а, Ь) как множество (а, (а, Ь)). Покажите, что при таком опреде ленин мы вправе называть компоненты "первой" и "второй", т.к. (а, Ь) = (с, й) тогда и только тогда, когда а = с и Ь = й. Таким образом, это определение позволяет ввести понятие порядка через понятие множества, в котором порядок следования элементов не играет никакой роли. 13. Наследником множества А называется множество А О (А). Определите наследников следуюших множеств: а) И; б) (я); в) (а,(а)). 14. Пусть 1 — некоторое множество и пусть для каждого 1 е 1 А, — множество обозначенное этим 1, тогда П А, = (х: х е А, для всех 1 е 1). 1ег Множество П А; называется обобщенным пересечением совокупности ~е! множеств (А,: 1 е 1) и обозначается иногда в сокращенном виде как (А ). Множество 1 называется индексным множеством, а совокупность (А,) называется индексированной множеством 1.
а) Пусть Дг = (1, 2, 3,...), а 1 = (П, 1з, О). Пусть Ад = (х:х = 2Й, где 1. — некоторое целое число); А... = (х:х = Зй, где /с — некоторое целое число); АО = (х:х = 5й, где й — некоторое целое число). Найдите такое С, что С = ИА, = (х:хе А; для всех)е(П,сз,о). ~ег б) Пусть 1 = Х = (1, 2, 3,...), а А; = (х: х Е 1т' и х > 1) = (г, г + 1, г + 2,...). Определите П,. г А,. 15. Если 1 — множество, а А, — множество для каждого 1 е 1, тогда Д А, = (х; сугцествует 1 Е 1 такое, что х е А ). сег Множество Д А; называется обобщенным объединением совокупности мно$ег жеств (А,: 1 е 1).
Пусть 1 = М = (1, 2, 3,...), а А, = (х: х Е Ю и х > 1) = (г,г+ 1,1+ 2,...). Определите Це, А,. РАЗДЕЛ 2.3 Доаераммы Ванна 77 2.3. ДИАГРАММЫ ВЕННА РАЗДЕЛ 2.3. анаграммы Ванне 79 РАЗДЕП 2.3. Диаграммы Ванна 81 Свойства множеств, сформулированные в приведенных ниже теоремах, могут быть проверены путем формальных доказательств или на диаграммах Венна. Обратите внимание, что они дублируют соответствуюпгие свойства в исчислении высказываний (см. теорему 1.3).
ТЕОРЕМА 2.18. Пусть А, В и С вЂ” подмножества универсального множества У. Тогда справедливы а) Законы идемпотентности АОА=А; АОА= А. б) Двойное дополнение 1А')' = А. в) Законы де Моргана (А О В)' = А' Г1 В'; 1АГ~В) =А ОВ. г) Свойства коммутативности АГ1В=ВПА; АОВ=ВОА. д) Свойства ассоциативности АГ1 (ВП С) = (Ап В) П С; АО(ВОС) = (АиВ) ОС.
е) Свойства дистрибутивности АП1ВиС) = (АЛВ) О(АПС); АО(ВПС) = 1АОВ) П(АОС). ж) Свойства тождества Аиа=А; А О У = А. з) Свойства дополнения АгиА'= У; А О А' = а. РЯЗдЕЛ 2.3. йваараммы Венна ВЗ РАЗВЕЛ 2.4, Булевы алгебры 85 предполагаются известными элементарные свойства целых чисел, хотя формально их изучению будет посвящена следующая глава. ОПРЕДЕЛЕНИЕ 2.19. Операция, заданная на некотором множестве, называется бинарной, если она действует на два элемента этого множества и ее результатом является элемент этого же множества. ОПРЕДЕЛЕНИЕ 2.20. Операция, заданная на множестве, называется унарной, если она действует на один элемент множества и ее результатом является элемент этого же множества.
Обозначения, использованные ниже, были введены в главе 1. ОПРЕДЕЛЕНИЕ 2.21. Булева алгебра есть множество В, содержащее специальные элементы 1 н О, на котором заданы бинарные операции + и и унарная операция '. Для всех х, у и 2 из В должны выполняться следующие аксиомы: а) Законы коммутативности х у=у х; Х + У = У + Х. б) Законы ассоциативности х (У.2) =(х У).2; х + (У+ 2) = (х+ У) + 2. в) Законы дистрибутивности Х (У+2) = (Х У)+(Х.2); х+(у 2) =(х+у) (х+2). г) Законы тождества х+О=х; х 1=х.
д) Законы дополнения х+х =1; х х'=О. Элемент 1 называется единичным элементом, или единицей; элемент О называется нулевым элементом, или нулем; а х' называется дополнением х. Знак бинарной операции часто опускается, и х у записывается просто как ху. 86 ГЛЯ8Я 2 Теория множеств Используя приведенные выше аксиомы, легко доказать ряд теорем о булевых алгебрах, в частности, справедливы приведенные ниже теоремы. ТЕОРЕМА 2.22.
Для всех элементов х и у булевой алгебры выполняются такие соотношения: а) Законы идемпотентности б) Свойства констант х+1=1; х 0=0. в) Законьс поглощения х + (х у) = х; х (х + у) = х. ДОКАЗАТЕЛЬСТВО. В каждом случае доказано только первое из утверждений теоремы. Доказательство второго утверждения предоставляется читателю.
а) х+х= (х+х) 1= свойство констант = (х+ х) (х+ х') = закон дополнения =х+(х х) = закон дистрибутивности = х+ 0 = закон дополнения б) х+1= х+х' = закон дополнения закон тождества закон дистрибутивности закон коммутативности свойство констант закон тождества ТЕОРЕМА 2.23.
(Закон единственности дополнения) Дополнение произволь- ного элемента х булевой алгебры единственным образом определяется его свой- ствами: если х+ х' = 1, х х' = О, х+ х' = 1, а х х' = О, то х' = х'. х; (х+1) .1 = (х + 1) (х + х ) х+(1 х) = х+ (х' 1) = =1; в) х+ (х у) = (х 1) + (х. у) = х (1+у) = =х (у+1) = закон тождества закон тождества закон дополнения закон дистрибутивности закон коммутативности закон тождества РЛЗДЕП 24.
Булавы алгебры 87 ДОКАЗАТЕЛЬСТВО. Если х + х' = 1 и х + х' = 1, тогда х~ =х'.1 = х (х+х*) = х х+х х*= х =х' 1= =х' х*, так что х* = х'х* = х'. ТЕОРЕМА 2.24. Для всех элементов х и у булевой алгебры имеют место такие соотношения: а) Закон инволюции (х')' = х. б) Дополнение законов тождества О' = 1; 1' = О. в) Законы де Моргана (х + у) = х . у; (х. р)' = *'+ р'. ДОКАЗАТЕЛЬСТВО. Для доказательства пункта (а) заметим, что х + х = х+ х = закон коммутативности =1; закон дополнения / Р х х = х х = закон коммутативности = О. закон дополнения х.х +х .х*= О+х х х' ° х*+ О = х' х* = х*. (х+х ) = =х' х+х* х = = х . х' + х х* = =О+х' х' = =х' х'+О= закон тождества задано закон дистрибутивности закон дополнения задано закон коммутативности закон тождества закон тождества задано закон днстрибутивности закон коммутативности задано закон коммутатнвности закон тождества 88 ГПЯВА 2.
Теория мномесгпв Следовательно, х есть дополнение х' и в соответствии с законом единственности дополнения (х) =х. Доказательство пункта (б) оставляем читателю. Доказательство пункта (в) приведено ниже. Обратите внимание, что каждая аксиома булевой алгебры состоит из пары равенств, которые являются двойственными в том смысле, что если в одном равенстве заменить + на, на +, 0 на 1 и 1 на О, получим второе равенство. В результате каждая теорема обладает двойственностью в том смысле, что если в любой теореме булевой алгебры заменить + на, на +, 0 на 1, а 1 на О, снова получим теорему (хотя она может и не отличаться от исходной).
Это соответствие имеет место, поскольку каждый шаг в доказательстве двойственной теоремы является двойственным соответствующему шагу в доказательстве исходной теоремы. Для примера рассмотрим приведенные ниже доказательства первого нз законов де Моргана (х+у) =х у и двойственное к нему соотношение (х у)'=х +у . Сначала докажем, что (х+у)' = х' у'. Для этого покажем, что (х+у)+х'.у' = 1 и (х+у) (х' у') = О. После этого, используя закон единственности дополнения, приходим к тому, что (х+ у)' = х' у'. закон тождества Теперь докажем, что (х у)' = х'+у'.
Сначала покажем, что (х у) (х'+у') = 0 и (х . у) + (х' + у') = 1. После этого, на основании закона единственности дополнения, получаем, что (х у)' = х'+ у'. (х+у)+х'.у' = ((х+у)+х').((х+у)+у') = ((у + х) + х') ((х + у) + у') = (у+(х+х')) (х+(у+у')) = (у+1) (х+1) = 1 1= 1; (х+ у) (х' у') = (х'. у') (х+ у) = ((х' у') х) + ((х' у') у) (х (х' у')) + ((х' у') у) ((х х') у') + (х' (у' у)) ((х х') у') + (х' (у у')) (О у ) + (х' 0) = (у' 0) + (х'. 0) = 0 + 0 = О.
закон дистрибутивности закон коммутативности закон ассоциативности закон дополнения свойство констант закон тождества закон коммутативности закон дистрибутивности закон коммутативности закон ассоциативности закон коммутативности закон дополнения закон коммутативности свойство констант РАЭДЕЛ 2.4. Булееы алгебры 89 закон дистрибутивности закон коммутативности закон ассоциативности закон дополнения свойство констант закон тождества 0; у) = Их'+у')+у) = ((х' + у') + у) = (х' + (у' + у)) = (х' + (у + у') ) = 1) = 1) = закон тождества Обратите внимание, что каждая строка второго доказательства двойственна соответствующей строке первого доказательства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
