Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 29
Текст из файла (страница 29)
Перед тем как продолнсить изложекке, сделаем несколько аамечакий о представлепил элементов злектрпческих схем с переключателями в виде диаграмм. Единствеяиый сегмент схемы, в котором будет отлпчие между рассматриваемымв примерами,— зто верхияя часть схемы, содержащая перекл1очателп; следовательно, можно ° ) Эти схемы зааыааитгя также атаками яа $уаквеояальпых азамевтов в ковтактныи» схамамя, соответственно,— У1ри.как, рад, 182 пе изобраягать остальной части схемы.
Внутри схемы некоторые переключатели могут быть взаимосвязаны (рпс. 5.11, а) и, возмо»кяо, могут работать так, что когда один переключатель включен, то другой должен быть выключен и наоборот (рис. 5.11, и). Основные методы 4 6 Рис, 5.11 расположения переключателей — это последовательпый (рпс. 5.11, с), что соответствует связке и (т. е.
А ДВ), и параллельный (рис. 5А1, И), что соответствует связке или (т. е. А Ч В). Отметим, наконец, что на диаграмме ость совершенно лишние переключатели, и их для удобства мои<по обозначать теми н«е «имеиамп» (рпс. 5.11,е), Таким образом, любую операцию в булевой алгебре можно представить при помощи схемы и иаооорот. Следовательно, для получения зквивалептных схем надо перейти от первоначальной схемы к соответствующему ей выражению в булевой алгебре, затем к «более простому» (или более желаемому) выражению и, наконец, к схеме, соответствующей этому выран«епию, 183 Пример 5.4.
Упростить схему, изображенную на рис. 5.12. Этой схеме соответствует следующее выражение: хуах'тц(т~,г))уч)ц~гр,худ)) = ХтХ ЛУЛ)Р')Ч(упгЛРР тгЛХуу)) (ХДХ'ДУУРУ(ХР,тр,гуМУ(Хр,гр,ХУР)- -(ХКтЛгд Н Я(ХЛгуР)-(ХПг)ттУЧЧК). Последнее выражение соответствует схеме, иаображенной на рис. 5,13, 2 — Х вЂ” Ф Ряс. 5.13 у — Х вЂ” 2 Рис. 5.13 Мы уже уделили достаточно внимания схемам с переключателями. Перейдем теперь к комбинационным схемам.
Основные компоненты таких схем — элементы. В наиболее общей форме элемент является устройством, имеющим и входов и и выходов (ж, я ж г)). На каждый вход может подаваться один ив двух бинарных сигналов; представим их как О и 1, однако любая другая система пэ двух рааличных аначепий также нам подходит. В реальной ситуации обычно мы имеем сигналы в окрестности О вольт (например, от О до 0,8 вольта), которые представляются нулем, и в другой окрестности — в районе 4 вольт (скажем, между 3 и 5 вольтами), которые представляются единицей.
Отсюда определяются выходные аначения (О и 1). Можно ожидать, что нам понадобится достаточно много рааличных элементов, чтобы представить все возможные функции (О, 1)" - (О, 1), однако, как мы увидим далее, ето не так. Схемам, не имеющим временпйх вадержек (в дальнейшем только такие схемы мы и будем рассматривать), соответствует един.
184 ственпый ткп элементов. Однако это не очевидно. Структура схем станет более ясной, если вначале мы рассмотрим три типа элементов, изображенных на рнс. 5.14. Самым а а — (а)--а ~- с Ь Ь Ю Ряс. ЬЛ4 простым является элемент не; его действие определяется тождеством с = ") а (с = не а), определяемым табл. 5.6. Таблица бЯ 1КРОТ(а) ООТРПТ(а) Аналогично элементы и и илн определяются табл.
5.7. Таблица 5.7 ОЦТРПТ8 (а) 1ЫРпте а Ь О О О О о 0 О ( т о $ Элементы и н нли могут также иметь несколько входов; в этом случае они определяются аналогично, т. е. выходной сигнал элемента и равен 1 тогда и только тогда, когда па всех входах сигнал равен $, и выходной сигнал элемента нлн равен $ тогда и только тогда, когда какой-либо иэ входных сигналов равен $. Алгебраиче ки выходной сигнал элемента не имеет вид: ) (входной сигнал), выходной сигнал элемента и имеет вид: (сигнал первого входа) /~ (сигнал второго входа) Д ...
и, наконец, выходной сигнал элемента или имеет вид: (сит нал первого входа) Ч (сигнал второго входа) У ... Что(бб бы представить более сложные 4ункции, злементы можно «соединять» равличпыми способами. Пример 5.5. Рассмотрим схему (более точно, часть схемы, которая нас интересует), изображенпую яа Рис. 5.15 рис. 5.15. Возвращаясь «назад» от выходов схемы, получаем х = ((а ~/(а Д Ь')) /1(у))', р = (ЬДс)'. Позтому х (((а1/а)/1(а~/Ь'))/~(ЬДс)')' = =((а~,(аЦЬ'))~,(Ь~,с)')' (а/1,(Ь~,с)')' (по закону поглощения). Таким образом, одно из возможных упрощений схемы изображено на рис.
5.16. // а Рве. 5.16 Следовательво, мы ммкем испольаовать булевы выражения для анализа и упрощения сложных схем, Рассмотренный пример показывает, как можяо осуществлять такие операции. Существуют также устройства, которые реализуют другие логические операции. Наиболее ван«ными являются злементы пе и и не или; опи изобрел епы на рис. 5.17.
Используя множество таких злементов, прп помощи булевых выражепий можно получить требуемую схему непосредственно по таблице истинности, 155 Пример 55 (продолжение). Не останавливаясь на формальностях, заметим. что каждое выражение в скобках в окончательной форме 1 (см. выше) представляет вход для последнего элемента на рис. 5.18 в может быть вычислено с помощью элементов предшествующего ряда «в и вв или Рвс. 5.17 (Части схемы, обведенные штриховыми линиями, практи"ески не требуются, поскольку для многих электрических элементов дополнение к выходу такнсе доступно из вспомогательного выхода.) Отметим, что полученная схема в общем случае не будет минимальной в смысле числа используемых элементов.
у В завершение рассмотрим два примера, которые показывают, как булеза алгебра может быть использована в задачах иного рода. г-- — -т х У у 7 Рвс. 8Л8 Пример 5.6, Предположим, что справедливы следующие утверждения: а) знание структур данных необходимо для совершенствования дисциплины ума; б) только опыт программирования может создать дис цнплинированный ум; 187 в) для того чтобы написать компилятор, кадо иметь воэможность анализировать задачи; г) недисциплинированный ум не может анализиро- вать задачи; д) всякий, кто писал структурные программы, может рассматриваться как опытный программист.
Можно ли ие этих предположений определять спра- ведливость нижеследующих утверждений: а') опыт написания структурных программ необхо- дим для того, чтобы быть в состоянии написать ком- пилятор; б') енанне структур данных является частью опыта программирования; в ) аналиа еадач невозможен теми, кто игпорврует структуры данных; г') опытный программист, который писал структур- ные программы, в состояний аналиеировать вадачи н имеет дисциплинированный ум, является программистом, который мог бы написать компилятор) Чтобы ответить на ети вопросы, мы могли бы иссле- довать логические следствия утверждений, однако для того, чтобы проиллюстрировать испольауемую технику в более сложных ситуациях, воспольауемся нашим внапг; ем булевой алгебры. Сначала необходимо аакодировать наши утверждения.
Пусть Ю' — множество всех программистов, У- те иа них, кто екает структуры данных, У-те ив них, кто имеет дисциплинированный ум, $У вЂ” те иа них, кто является опытнымп программи- стами, Х вЂ” те ие них, кто мог бы написать компилятор, У те из них, кто может анализировать еадачи, 2 те из них, кто может писать структурные про- граммы.
Тогда имеем а) Пвер;б) гржУ;в) ХиУ; г) УжУ;д) рржг; а') Я ы Х; б') У ле Й~; в') У ы У; г') Уг'й2 й Уй УжХ, Теперь видно, что а') непосредственно следует из в), г), б) и д) до транэитивности; аналогично в') следует из г) и а). Также ФрйЯй Уйр ррй Уй У Уй У УжХ Таким образом, г') также справедливо. Утверждение б') не может быть выведено из а) — д), поскольку мы только внаем, что 1»'>и Я, н цепочка на этом заканчивается. » Пример 5Л. Алиса сказала, что Барбара и Клара говорят правду, а Клара сказала, что Злспет и Фиона нли обе говорят правду, или обе лгут.
С другой стороны, Деби считает, что по крайней мере или Алиса, или Барбара говорят правду, тогда как Барбара утверждает, что только одна из двух — Алиса или Фиона — была правдивой. Злспет считает, что Аляса и Барбара всегда говорят правду, однако Фпона уверена, что Барбара и Клара обе ве могли сказать правду.
Кому мы должны верить3 Рассмотрим множество утверждений вида «Алиса (не) говорит правду», «Барбара (не) говорит правду», н пусть А содержит только те утверждения, в которых Алиса говорит правду. Пусть В, С, В, Е и Р определены аналогично, Тогда, если Я вЂ” непустое множество пересечений таких, что 8>к А ПВ'ПС, то Я включает утверждения, в которых «Алиса говорит правду», «Барбара лжет», «Клара говорит правду». 11з первого утверждения следует, что можно вывести следующий факт: если Алиса говорит правду, то то же самое делают Барбара и Клара.
Зто можно закодировать следующим образом: если лжА, то х»иВПС; следовательно, А жВПС. (Ц Аналогично другие утверждения могут быть записаны в виде С ж (Е П Р) 0 (Е' П Р'), (2) Вж 4>>В, (3) В>к(ЕЦР)~(ЕПР) (ЕПР')0(Е'ПР), (4) Е»иА ПВ, (б) Р>и(ВПС)' (6) «89 Иэ (2), (4) ц (1) следует, что В й С = О, и поэтому А — О; те~да пз (5) следует, что Е= Ы, Эти выводы мы смогли получить пепосредствеппо пз условий задачи. До сил пор наши рассуждения былп эффективны потому, что мы полъзовалпсь тем, что правдивый человек говорит правду. Однако пока мы не использовали ничего о справедливости того, что говорит ля;ец.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
