АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ

Читайте также:
  1. I. Решение логических задач средствами алгебры логики
  2. II. Решение логических задач табличным способом
  3. III. Решение логических задач с помощью рассуждений
  4. IV. Список мифологических имен,
  5. Ms Excel: мастер функций. Логические функции.
  6. RS-триггеры на логических элементах
  7. А 55. ЗАКОНОМІРНОСТІ ДІЇ КОЛОГИЧЕСКИХ ФАКТОРІВ НА ЖИВІ ОРГАНІЗМИ
  8. А) ПЕРЕВОД ИДИОМ (ФРАЗЕОЛОГИЧЕСКИХ СРАЩЕНИЙ)
  9. Автоматизация функций в социальной работе
  10. Актуальность исследования геронтопсихологических проблем
  11. Алгоритм построения графиков функций вида
  12. Анализ пожарной опасности технологических процессов

Полученные по формуле СДНФ (12) выражение может быть преобразовано (не всегда) к виду, имеющему меньшее число переменных и операций по сравнению с исходным. Такое преобразование называется минимизацией.

Рассмотрим пример. Имеется три двоичных датчика xi. Необходимо реализовать ЛФ Yмажор принимающую значение 1, когда равны 1 значения двух и более датчиков. Такая функция называется мажоритарной. Ее таблица истинности имеет вид:

По формуле (12): Yмажор = ~x2*x1*x0 + x2*~x1*x0 + x2*x1*~x0 + x2*x1*x0. (3,5,6,7 - строчки таблицы). Полученному выражению соответствует схема на рис.6.

Схема содержит 4 трехвходовых элемента "И" и 1 четырехвходовый элемент "ИЛИ". Нахождение минимальной формы ЛФ производится методом алгебраических преобразова- ний, с помощью таблиц Карно или машинными методами для больших проектов.

 

ТАБЛИЦА КАРНО

Таблица Карно (ТК) это видоизмененная запись таблицы истинности. Для функции мажоритарности из последнего примера (ТК) выглядит следующим образом:

Правила построения ТК следующие: 1)Количество клеток ТК равно количеству строк таблицы истинности. 2)Слева и сверху располагаются значения аргументов. Порядок размещения аргументов таков, что в двух соседних по горизонтали и вертикали клетках отличается значение только одного аргумента (поэтому соседними считаются и клетки, находящиеся на противоположных краях таблицы). 3)В клетки заносятся соответствующие значения ЛФ. 4)Единичные клетки объединяются в прямоугольники (импликанты) по 2^i клеток. 5)Для каждого прямоугольника записывается произведение тех аргументов, которые в соседних клетках не изменяют своего значения. 6)Переменные входят в произведение в прямом виде, если их значение в соседних клетках равно 1, в противном случае в инверсном. 7)Полученные произведения складываются по ИЛИ в искомую ЛФ.

В примере имеется 3 прямоугольника - A,B,C, причем Ya = x2*x0 (x1 в соседних клетках меняет свое значение, поэтому в конъюнкцию не входит). Yb = x1*x0 и Yс = x2*x1.

Yмажор = Ya + Yb + Yc = x2*x0 + x1*x0 + x2*x1. (13)

Соответствующая схема (рис.7.) проще, чем на рис.6.

 

1.12 ПРЕОБРАЗОВАНИЕ ЛФ К БАЗИСУ "И-НЕ" И "И-ИЛИ-НЕ"

Применяя к выражению (13) аксиому двойного отрицания (9) получим:

Yмажор =~(~(x2*x0 + x1*x0 + x2*x1)) (14)

Формуле (14) соответствует схема (рис.8,слева) в базисе И-ИЛИ-НЕ.

Применяя к выражению (14) соотношение двойственности (11) получим ~(~(x2*x0) * ~(x1*x0) * ~(x2*x1)). Последнему выражению соответствует схема в базисе И-НЕ (рис.8, справа).

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)