Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 9
Текст из файла (страница 9)
3. Используйте блоки, максимальные по величине, не меняя числа блоков. 4. Оцените блоки с соответствующими высказываниями, которые описывают их, и объедините эти высказывания символом ч. Проиллюстрируем этот процесс путем построения карты Карно для четырех высказываний р, д, т и в, изображенной на рис. 1.12, где во внутренных прямоугольниках представлены элементарные конъюнкции, составленные из тех высказываний, расположенных на краях, которые принадлежат строке и столбцу соответствующих прямоугольников. Например, крайние высказывания, соответствующие второй строке и третьему столбцу, есть р, 4, -т и -в, что порождает элементарную конъюнкцию р Л о Л т Л в.
Рассмотрим выражение (рЛдЛтдв)Ч (рдд Л тдв)Ч(рЛддт Л ч(р д д А -т А -в) м (-р А 4 д т А -в) м (-р л 4 л -т л -в) ч ~(-р д д д т д в) ~ (-р д 4 А -т А в) ~ (р Д -4 д -т А в|~ Ч(р А-длт Лв)Ч (р Л-абдт Л-в). Рис, /.12 Размещая соответствующие значки в карте Карно, получаем карту, изображенную на рис. 1.!3, которую можно покрыть восьмикратным, четырехкратным и двукратным блоками.
Восьмикратный блок можно описать, используя только одну из компонент р, о, т или в. В данном случае восьмикратный блок описывает о. Четырехкратный блок можно описать, используя только два простых высказывания. В данном случае этот блок можно описать, используя р л в. Двукратный блок можно описать, используя три простых высказывания. В данном случае это р Л опт. Следовательно, исходное высказывание можно упростить и привести к виду дч(рдв)ч(р А абдт). поскольку т находится на обоих концах строки, а в находится на обоих концах столбца, "скручивание" карты Карно объединяет эти 64 ГПАВА и Таблицы истинности, логика, доказательства Рис.
1.И случаи, так что верхний край можно считать прилегающим к нижнему, а левый— прилегающим к правому. Например, четырехкратный блок на карте Карно на рис. 1.14 можно описать посредством г л а. Рис. 1.!4 ° УПРАЖНЕНИЯ 1. Упростите высказывания, выраженные следующими картами Карно: а) о ц РАЗДЕЛ 1.6. Карты Карно 55 в) 2. Упростите высказывания, выраженные следующими картами Карно: а) гг Я -г 56 ГЛЛВА 1. Таблицы истинности, логика, доказательства 3. Используйте карты Карно для упрощения следующих выражений: а) (р л 4 л г) ч (-р л 4 л т) ч (-р л 4 л -г)ч ч( рл дл ) ч(рлйл т); б) (р Л 4 Л -т Л в) Ч (р Л -4 Л -т Л в)Ч (р Л 4 Л -т Л -в)Ч ч(р л-4 л л-в)ч (-рл4 л- л-в)ч Ч(-Р Л 4 Л -т Л в) Ч (-Р Л -4 Л -т Л в) Ч ( Р Л 4 Л т Л -в) Ч Ч( РЛ 4Лт Л в); в) (рЛ4ЛтЛв)Ч( рЛдЛтЛв)Ч (р Л д Л т Л в)Ч ч(р л -4 л т л -в) ч (- р л - 4 л - т л - в) ч ч(-р л-4лт л-в).
4. Используйте карты Карно для упрощения следующих выражений: а) (рЛ4Лг) Ч( рЛд Л г) Ч( рЛ4Лт)Ч ч(р л-д л-т) ч(-рл-4лт); б) (рЛ4 Л тЛв)Ч(р Л 4 Л тЛв)Ч( рЛ4ЛтЛв)Ч Ч(-Р Л 4 Л - Л в) Ч ( Р Л -4 Л - Л в) Ч (-Р Л -4 Л т Л в); в) (рЛ4ЛтЛв) Ч(рЛ4Лг Л в) Ч( рЛ4Л тЛ в)Ч Ч(р Л 4ЛтЛв)Ч (р Л дЛт Л в)Ч ( р Л 4Лг Л в). 1.7.
КОММУТАЦИОННЫЕ СХЕМЫ Высказывания, соответствующие коммутационным (релейно-контактным) схемам, принято выражать в системе обозначений булевой алгебры, которая будет введена в разделе 2.4. Поэтому, прежде чем перейти к изучению коммутационных схем, мы перейдем от обозначений, принятых в логике, к булевой записи. Символы Л, Ч и заменяются, соответственно, на, + и '. Таким образом, (р Л 4) Ч т превращается в (р 4) + т', а (рлбл )ч(рл балт)ч( рлйл г) принимает вид (р 4 т ) + (р д г) + (р д т ) .
Как и в обычной алгебре, знак произведения, как правило, опускается, и предполагается, что произведение выполняется перед сложением, поэтому приведенное выше выражение можно переписать в виде рдт + рд г+ р 4т . В таблицах истинности Т заменяется на 1, а г на О, так что таблица истин- ности РЛЗЛЕЛ 1.7.
Коммутационные схемы 57 Случай р 9 т р ч (( су) л т) 1 Т Т Т 2 Т Т Г 3 Т Г Т 4 Т с Г 5 Е т Т 6 Е Т Е 7 Е с Т 8 Г Г Г преобразуется в таблицу Случай р 9 ч. Р + (9' ° т) Рис. 1.15 В !938 г. Клод Шеннон заметил связь между таблицами истинности и электрическими цепями. Рассмотрим схему переключения на рис.
1.!5, которая состоит из источника питания (рис. 1.16) и электрической лампочки (рис. !.17). Рис, 1.15 Рис. 1.17 Присвоим значение 1 переключателям Р и д, если они замкнуты (т.е. электрический ток проходит через них). В противоположной ситуации присвоим им 1 2 3 4 5 6 7 8 1 1 1 1 1 О 1 О 1 1 О О О 1 1 О 1 О О О 1 О О О Т Т Г Т Г Т Т Т Р Т Г Г Т Т Т Е Т Т Т Т Т Г с с Е Е Г Т Р Т Р Р Г Т Г Е Г Т Т Е Т Т Е Е Т Е Е Г 1 1 О О 1 1 1 О О О 1 1 1 1 1 1 1 1 О О О О О О 1 О О О О О О 1 1 1 1 О О 1 О О 58 ГЛАВА 1.
Таблицы истинности, логика, доказательства значение О. Присвоим значение 1 схеме, когда лампочка светится (т.е. электрический ток через нее проходит). Заметим, что при последовательном соединении элементов цепи р и о, как это имеет место на приведенной выше схеме, лампочка загорается, и значение схемы становится равным 1 только в случае, когда оба переключателя замкнуты, т.е, и р, и д имеют значение 1. Таким образом, схема соответствует высказыванию р д. Такое расположение переключателей называется логическим элементом р и д, или схемой логического умножения.
Этот логический элемент обозначается символом, изображенным на рис. !.18. Р ри 9 Ц Рис. 1.18 Теперь рассмотрим схему переключения, показанную на рис. !.19, где переключатели р и о соединены параллельно. Рис. 1.19 Р Я Р , !гб Р— ~; нер Рис. 1.21 Предположим, имеется схема (мы не будем пытаться ее изобразить), с одним переключателем р, который обладает таким свойством, что лампочка загорается тогда и только тогда, когда р разомкнут.
Следовательно, схема имеет значение 1, когда р имеет значение О, и имеет значение О, когда р имеет значение 1. Эта схема соответствует р', а соответствующий логический элемент называется логическим элементом не, или инвертором. Логический элемент не обозначается символом, изображенным на рис. 1.21. Отметим, что теперь лампочка загорается, и значение схемы становится равным 1, когда один из двух переключателей р или 9 замкнут, т.е.
либо значение р = 1, либо д = 1 (либо оба они равны 1). Эта схема соответствует высказыванию р + д. Такое расположение выключателей называется логическим элементом р или д, или схемой логического сложения. Этот логический элемент обозначается символом, изображенным на рис. !.20. РдЗДЕЛ 1.7.
Коммутационные схемы 99 ПРИМЕР 1.7. Схема на рис. 1.22 содержит логический элемент р и д, за которым следует инвертор, так что схема соответствует выражению (р о)'. Заметим, что инвертор отрицает всю предшествуюгцую ему схему. Рис. Д22 ПРИМЕР 1.8. Схема на рис. 1.23 содержит соединение логического элемента р или д с логическим элементом не т посредством логической схемы умножения. Следовательно, она соответствует выражению 1р+ о) Рис. Д23 ПРИМЕР 1.9. Булево выражение, соответствующее схеме на рис.
1.24, имеет вид (р'. д) + (р т')'. Рис. 1.24 ПРИМЕР 1.10. Коммутационная схема, соответствующая выражению (р' о) + т, показана на рис. 1.25. Рис. /.2о ПРИМЕР 1.11. Коммутационная схема, соответствующая выражению Ир+ д)' (р+ т)) + т', показана на рис. 1.26.
Р Я Рис. Д26 60 ГЛАВА я Таблицы истинносгли, логика, доказательстаа ПРИМЕР 1.12. Построим схему трехклавишного переключателя, при помоши которого свет включается тремя различными двупозиционными переключателями. Рассмотрим сначала соответствуюшее булево выражение. Свет должен включаться, когда все три переключателя замкнуты, т.е. необходимо иметь рдг. Если один из переключателей разомкнут, то свет должен быть выключен. Однако, если разомкнуть другой переключатель, то свет должен включиться. Следовательно, искомое выражение имеет вид рдг+рд'г'+р'д'г+р'дг'. Для простоты, вместо схемы, представленной на рис.
1.27, для выражения рдг мы будем использовать схему, изображенную на рис. 1.28. Р д г Рис. 1.27 А для выражения р+ д + г вместо схемы на рис. 1.29 мы будем использовать схему, показанную на рис.!.30. Р д —;=3:З— Рц . 1.ЗО Рис. 1.29 Тогда искомая схема будет такой, как показано на рис. 1.ЗЗ. Ранее было отмечено, что штрих Шеффера, обозначаемый через (, имеет ту же таблицу истинности, что и (рд)' (в булевой записи), поэтому мы и упоминали его как логическую связку не-и. В свою очередь, стрелка Пирса, обозначенная 1, имеет ту же самую таблицу истинности, что и (р + д)', поэтому она упоминалась как связка не-или. Логические элементы не-и и не-или обозначаются символами, показанными на рис.
1.31 и 1.32. Рис. 1.31 Выражению (р!д) ! (р(г) соответствует схема, изображенная на рис. !.34. Р д Рис. 1.34 РЛЗИЕЛ 7.7. Коммутационные схемы 61 Рис. й33 ПРИМЕР 1.13. Полусумматор находит сумму двух двоичных чисел 1 и 0 со- гласно таблице сложения: 0 1 0 1 1 10 Свое название полусумматор получил в связи с тем, что при сложении двоичных чисел с более чем одним разрядом (что станет предметом обсуждения в последующей главе) суммируются только низшие разряды, поскольку нет возможности учесть в сумме число, которое "переносится". Для удобства суммирования одноразрядных двоичных чисел таблица, приведенная выше, преобразована к ви- ду 0 1 0 1 00 01 01 10 Пусть р и д обозначают числа, которые требуется сложить, а ды до — первый и второй разряды суммы, тогда приходим к следующим таблицам истинности: Случай р о Но Случай р д 1 1 1 0 2 1 0 1 3 0 1 1 4 0 0 0 1 1 1 2 1 0 3 0 1 4 0 0 1 0 0 0 Следовательно, Ио = рд'+р'д, что эквивалентно (р+д) (рд)'.
Это можно показать, используя таблицы истинности или правило эквивалентности (см. упражнения). Также г(г = рд. Коммутационная схема для полусумматора приведена на рис. 1.35. с1, Рис. 1,35 Поскольку полусумматор дает сумму двух чисел, он обозначается символом, изображенным на рис. 1.36. Р с!„ и Рис.
13б ПРИМЕР 1.14. Полный сумматор складывает три одноразрядных двоичных числа. Следовательно, он может сложить два двоичных числа с тем числом, которое "переносится". Пока необходимо рассматривать это как сложение трех одноразрядных двоичных чисел. Если предположить, что р, д и т обозначают числа, которые необходимо сложить, а Н~,с(~~ — первый и второй разряды их суммы, получаем следующие таблицы истинности: ,1№ Случай р у г с1о действительно есть результат сложения Но с г, где йо — второй разряд суммы Р и д, Следовательно, его схему легко описать, Значение т~ проще получить, используя приведенную выше таблицу истинности г( =ро +рдг +рог+рог. Воспользовавшись картой Карно для выражения д~, получаем следующую карту: 62 ГЛАВА 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
