Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 10
Текст из файла (страница 10)
Таблицы истинности, логика, доказательстаа 1 1 1 1 2 1 1 О 3 1 О 1 4 1 О О 5 О 1 1 6 О 1 О 7 О О 1 8 О О О 1 О О 1 О 1 1 О РАЗДЕП 1.7. Коммутационные схемы 63 Таким образом, с)~ = рд+ рт+ дт = рд+ (р+ д)т, поэтому схема может быть приведена к виду, показанному на рис. 1.37. (Более подробно эта схема представлена на рис. 1.39, приведенном ниже.) Рис. 1.37 Поскольку полный сумматор складывает три числа, он будет обозначаться символом, показанным на рис. 1.38. г-р:ФГ+ +) Рис. 1.39 ° УПРАЖНЕНИЯ 1. Перепишите следующие высказывания в обозначениях булевой алгебры: а) (равд)Л(д Ч т); б) (д Ч т)Д( рЧт)Л(д Ч тЧз); в) -(р Л-д Дт) Ч (-д Л т) Ч (р Д-д Л-т); г) -(-р Ч (д Л -т)); д) (рлт) Ч(р Л д) Л(рЧт Ч 3).
64 ГПАВА Я Таблицы истинности, погика, доказательства 2. Перепишите следующие высказывания в обозначениях булевой алгебры; а) (рчцч т)л (тн д); б) (-илт) ~I-(рлт); в) ((рлт) и о); г) (р л с л т) ч (-р л о л -т) ч (-р л и л т) ч (-р л о л -т); д) (р л -и л -т л з) и (-р л д л т л з) ч (-р л о л -т л з). 3. Приведите булевы выражения, соответствующие коммутационным схемам: а) ГЛЯВЯ 1. Таблицы истинности, логика, докезеглельстее д) Постройте коммутационные схемы, соответствующие булевым выражениям: а) (р'+ д)(р+ (дт)); б) (рд') + Идт') + (р'т)); в) (д'т') + Ирд)'(д'т)); Г) (д1т + е))((р д ) + (дт )); д) (рд) + Ирд'т') + т)'.
6. Постройте коммутационные схемы, соответствующие булевым выражениям: а) (рд')'+ (дт)', б) Ир+ д)г)', в) ((р'(д + р'т)) + (рд' + т); г) (р'д+ (д'т))'+ рз', д) Ирд')' + (т'з))(р+ т'). 7. Муниципальный совет состоит из пяти членов. Каждый член совета имеет для голосования кнопку "за" и кнопку "против". Решение принимается, если за него проголосует большинство.
Постройте коммутационную схему устройства, сигнализирующего о том, что решение принято, путем высвечивания индикатора. Указание: при построении схем используйте последовательное и параллельное соединение переключателей, как показано в начале раздела. 8. Муниципальный совет состоит из пяти членов, включая председателя совета Каждый член совета имеет для голосования кнопку "за*' и кнопку "против". Решение принимается, если за него проголосует большинство. Председатель совета голосует только в том случае, если голоса "за" и "против" разделились поровну.
Постройте коммутационную схему для определения принятия или непринятия решения путем высвечивания индикатора. Указание: при построении схем используйте последовательное и параллельное соединение переключателей, как показано в начале раздела. 9. Муниципальный совет состоит из пяти членов, включая председателя сове- та. Каждый член совета имеет для голосования кнопку "за" и кнопку "против". Решение принимается, если за него проголосует большинство, исключая председателя, который имеет право вето. Постройте коммутационную схему для определения принятия или непринятия решения путем высвечивания индикатора. 10.
Электрическая схема содержит три двупозиционных переключателя. Скон- струируйте схему для включения и выключения любым переключателем. 68 ГЛАВА 2. Теория мномеоте сел, которые меньше или равны и. Очевидно, что перечисление элементов удобно только в том случае, когда множество элементов мало или произвольный элемент характеризуется свойством, которое легко описать. Используя этот метод, не так легко описать множество граждан Соединенных Штатов Америки и совершенно немыслимо описать множество действительных чисел. В общем случае множество задается путем указания характеристического свойства, т.е. свойства, которому удовлетворяют элементы данного множества, и только они.
Для задания обычно используются фигурные скобки, а внутри них приводится характеристическое свойство, описывающее множество. Таким образом, множество (х: х обладает свойством Р) предполагается содержащим только те объекты, которые имеют свойство Р. Например, (х: х — футболист, играющий за Юго-западный колледж) — множество, состоящее из всех футбольных игроков, выступающих за Юго-западный колледж. Запись (х: х — гражданин Англии) описывает множество всех граждан Англии. Способ задания множества должен быть адекватным, т.е, должен полностью определять множество. Это не представляет труда, если объекты множества перечислены.
Рассмотрим, однако, множество А = (х: х — высокий студент данной группы) или В = (х: х — хороший студент данной группы). Если различным студентам группы предложить определить множества А и В, они могут сделать это неоднозначно, выбирая в качестве элементов как множества А, так и множества В не одних и тех же людей. При рассмотрении множества С = (х: х — привлекательная (или красивая) студентка группы) выбрать элементы множества С не только трудно, но не стоит даже пытаться это сделать. Однако, если множество А = (х: х — студент данной группы, рост которого выше 180см) и В = (х: х — студент данной группы, средний балл которого не ниже 4), то можно сказать определенно, является ли данный студент элементом А или В, так что А и В действительно есть множества.
Таким образом, мы приходим к следующему формальному определению. ОПРЕДЕЛЕНИЕ 2А. Если а есть один из объектов множества А, мы говорим, что а есть элемент А, или а принадлежит А. Принадлежность элемента а множеству А записывается как а Е А. Если а не является элементом А, это записывается как а )е А.
Например, 3 Е (1,2,3,4), но 5 ф (1,2,3,4). Если Р есть множество (х: х был президентом Соединенных Штатов), то Авраам Линкольн е Р, а Патрик Гэнри ф Р. ОПРЕДЕЛЕНИЕ 2.2. Множество А есть подмножество множества В (обозначается А С В), если каждый элемент А есть элемент В; т.е, если х Е А, то х Е В. В частности, каждое множество есть подмножество самого себя. Если А не является подмножеством В, это записывается как А ~ В. Таким образом, А Я В, если существует элемент А, не принадлежащий В. РАЗДЕЛ 21. Понятие мноягастаа 69 Следовательно, (1,2,3) С (1,2,3,4), но (1,2,5) ~ (1,2,3,4). Если А = (х: х — футболист колледжа), В = (х: х — спортсмен колледжа), а С = (х; х— самый сильный математик колледжа), то А С В, но С ~ В. Множества равны, если они содержат одни и те же элементы. Если А есть множество (2,4,6), а В есть множество (х: х есть четное положительное целое число, которое меньше 7), тогда А и  — равные множества.
Таким образом, мы приходим к следующему определению. ОПРЕДЕЛЕНИЕ 2.3. Пусть А и  — некоторые множества. Говорят, что А равно В, и пишут А = В, если для любого х имеем; х е А тогда и только тогда, когда х Е В. Иначе говоря, А = В тогда и только тогда, когда А с В и В С А. Если А С В и А ф В, то это записывают А с В и говорят, что А есть собственное подмножество В. Таким образом, доказательство равенства множеств А и В состоит из двух этапов: 1) Доказать, что А есть подмножество В. 2) Доказать, что В есть подмножество А. Поскольку множество однозначно определяется только элементами, которые оно содержит, порядок их перечисления роли не играет. Например, (1,2,4,6) = (2,1,6,4).
Кроме того, любой элемент либо принадлежит данному множеству, либо нет. Каждый элемент может входить во множество не более одного раза. С этого момента вводится два новых множества: универсальное множество, или универсум, и пустое множество. В известном смысле они представляют собой противоположности, поскольку пустое множество не содержит элементов, а универсальное множество содержит "все" элементы. ОПРЕДЕЛЕНИЕ 2.4. Пустое множество, обозначаемое а или (), есть множество, которое не содержит элементов. универсальное множество сГ есть множество, обладающее таким свойством, что все рассматриваемые множества являются его подмножествами.
В теории чисел универсальное множество обычно совпадает со множеством всех целых или натуральных чисел. В математическом анализе универсальное множество может быть множеством всех действительных чисел или множеством всех точек п-мерного пространства. Следует отметить, что универсальное множество сГ, хотя и названо универсальным, однозначно не определено, если точно не указана область рассмотрения (предметная область). Конечно, любое множество, содержащее сl, может быть использовано как универсальное множество. По определению, каждое множество есть подмножество универсального множества.
Пустое множество есть подмножество любого данного множества А, поскольку каждый элемент пустого множества содержится в А. Можно сказать, что не существует элементов пустого множества, которые не принадлежали бы А. 70 ГЛЯВЯ 2. Теория множеств ° УПРАЖНЕНИЯ 1. Перечислите элементы множества (х; х — целое и хз < 100). 2.
Перечислите элементы множества (х: х — президент США после 1940 года). 3. Перечислите элементы множества (х:х — гласный звук). 4. Перечислите элементы множества (х : х — положительное четное целое число, меньшее чем 2Ц. б. Опишите множество (3,6,9,12, 15,18,21,24) при помощи характеристического свойства. 6.