Тема 4 Логические основы ЭВМ (Все лекции Шамаевой в формате PDF), страница 2

4).Таблица 4.Диаграмма Вейча функции YПосле выделения конъюнкций (они отмечены звездочкой), видно, какиеконъюнкции могут образовывать пары для склеивания.В результате применения операций склеивания и поглощения можно получитьдругое аналитическое выражение:в котором отсутствуют возможности дальнейших склеиваний и поглощений. Однакопоследнее выражение является избыточным, так как отдельные конъюнкции могут быть“лишними”, т.е. их “составные части” могут включаться в другие конъюнкции. У даннойфункции существует пять безызбыточных дизъюнктивных форм, из которых только двеявляются минимальными:Из приведенных зависимостей видно, что только функции у1 и у4 являютсяминимальными формами функций, так как они содержат наименьшее число конъюнкцийи имеют минимальный ранг этих конъюнкций.Минимизация “вручную” возможна только для функций, зависящих от 4-5переменных, так как трудоемкость переборов растет в квадратичной зависимости от числапеременных.

Применение мощных ЭВМ для этих целей позволяет расширить границы доп= 12-15. Если при этом учесть, что функции могут быть частично определены (значенияфункций на некоторых наборах переменных можно определять произвольно), а также чтоиногда приходится решать задачи совместной минимизации систем ЛФ, то минимизацияЛФ становится сложной инженерной, практической и научной проблемой.4.Техническая интерпретация логических функцийПо логическим выражениям проектируются схемы ЭВМ.

При этом следуетпридерживаться следующей последовательности действий.1. Словесное описание работы схемы.2. Формализация словесного описания.3. Запись функций в дизъюнктивной (конъюнктивной) совершенной нормальнойформе по таблицам истинности.4. Минимизация логических зависимостей с целью их упрощения.5. Представление полученных выражений в выбранном логически полном базисеэлементарных функций.6.

Построение схемы устройства.7. Проверка работоспособности полученной схемы.Покажем взаимосвязь перечисленных этапов на примере.Пример 2. Спроектировать схему, фиксирующую появление “неправильной” тетрады вдвоично-десятичном представлении чисел.1. Каждая тетрада двоично-десятичного представления числа содержит десятичныецифры 0-9, что соответствует двоичным числам 0000-1001. Значения тетрады,соответствующие двоичным числам 1010-1111 (шестнадцатеричные цифры A-F), недолжны появляться при представлении десятичных чисел.2.

Составим таблицу истинности функции (табл. 5), которая принимает значения,равные единице, при появлении “неправильных” тетрад. Разряды тетрады обозначимпеременными х, у, z, u.Таблица 5Таблица истинности функции F3. Исходная совершенная дизъюнктивная нормальная форма записывается4. Эта форма функции допускает упрощение, что видно по диаграмме Вейча (табл.6). Этот же результат можно получить аналитически.Таблица6Диаграмма Вейча для функции F5. Минимальная форма функции F в логически полном базисе {&, v,  } будетиметь вид:Для представления этой же схемы в другом полном базисе, например {&}, воспользуемсяправилом де Моргана:6.

По полученным зависимостям можно построить схемы фиксации“неправильных” тетрад (рис.2).7. Проверить работоспособность построенных схем можно путем заданияразличных комбинаций переменных х, у, z, и и определения реакции на выходе схемы F.Рис. 2. Схема фиксации неправильных тетрад: а - схема в базисе (, &, V), б - схема вбазисе (&).Пример 3. Спроектировать схему устройства для обработки результатов решениястудентами задач №1 и №2.

При этом результатом считается решение одной из задач(минимальный результат) или решение двух задач.1. Обозначим функцию решения y=f(x1;x2) и представим структуру разрабатываемогоустройства:X1y=f(x1;x2)YX22. Составим таблицу истинности для поставленной задачи.X10011X20101Y01113. Запишем аналитическое выражение для функции Y в совершенной дизъюнктивнойнормальной форме (СДНФ) по условию задачи:Y= ⌐x1 x2 Vx1⌐x2 Vx1x24. Выполним минимизацию, используя закон склеивания для элементов 2 и 3.

Врезультате имеемY=x1x2Vx1На втором шаге минимизации используем закон свёртки. В результате имеемY=x2Vx1Полученная функция минимальна и реализуется в виде простой схемы «ИЛИ»(логического сложения).X1X2ИЛИY.