Минимизация логических функции.

Минимизацией называют процедуру упрощения выражения логической функции, с тем, чтобы она содержала минимальное количество членов при минимальном числе переменных. Чем проще логические выражения, описывающие функции, тем проще и дешевле реализующая их схема.

В некоторых простых случаях минимизацию можно осуществить непосредственно используя основные законы булевой алгебры. В качестве примера упростим выражение (1.1), используя закон склеивания:

(1.3)

Полученное выражение равносильно исходному, но значительно проще его.

Следует отметить, что такие элементарные приемы минимизации удается использовать не часто — при малом количестве членов функции и небольшом числе переменных. В других случаях применяются графические методы минимизации, облегчающие поиск склеивающихся членов. К ним относится метод минимизации с помощью карт Карно.

Карта Карно – это таблица, построенная так, что в ее соседние клетки попадают смежные наборы переменных функции — наборы, отличающиеся значением одной переменной: в один набор эта переменная входит в прямой форме, а в другой — в инверсной. Благодаря этому возникает наглядное представление о различных вариантах склеивания смежных наборов.

Карта Карно имеет столько клеток, сколько комбинаций (наборов) можно составить из прямых и инверсных значений n переменных по n членов в каждой –2ⁿ. Так, при n =2 карта содержит четыре клетки (рис. 1.5, а), при n=3 - восемь клеток (рис. 1.5, б), при n =4 — шестнадцать клеток (рис. 1.5, в) и при n=5 – тридцать две клетки (рис. 1.5, г).

Каждые строка и столбец имеют строго определенную комбинацию значений переменных. Каждая клетка карты соответствует определенной комбинации значений переменных и могут быть обозначены номерами строк таблицы истинности – j.

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

Минимизация функции заключается в объединении клеток карты с единицами (или нулями) контурами. Объединение каждой пары минтермов (макстермов) контуром уменьшает число входящих в них переменных на единицу.

Общие правила склеивания членов, занесенных в карту Карно, следующие:

1) охватывать контуром можно только соседние клетки;

2) контур должен быть только прямоугольным или квадратным и возможно большей площади;

3) количество клеток в контуре должно быть равно 2ⁱ, т. е. 2, 4, 8, 16 клеток;

4) контуры могут частично накладываться друг на друга;

5) крайние клетки строки, а также крайние клетки столбца карты считаются смежными; их можно таковыми представить, если мысленно свернуть карту в горизонтальный или вертикальный цилиндр;

6) количество охватывающих контуров должно быть минимальным.

Функция, минимизированная по единицам с помощью карты Карно, состоит из суммы простых конъюнкций. Каждая из них получается в результате склеивания членов, которым соответствует охваченные контуром единицы. В такую конъюнкцию войдут только те переменные, значения которых в пределах контура не меняются.

Порядок минимизации логической функции следующий:

1) построить карту Карно требуемого размера;

2) внести в карту единицы, соответствующие отдельным минтермам СДНФ функции;

3) охватить клетки карты возможно меньшим числом контуров. Чем больше клеток охвачено контуром, тем проще будет искомое выражение.

4) составить выражение для каждого контура;

5) записать минимизированное выражение функции.

Существует жёсткая однозначная связь между таблицей истинности, аналитическим выражением для функции и картой Карно.

Пусть логическая функция задана таблицей истинности (табл.5) или в СДНФ (1.1):

.

Непосредственно из таблицы истинности в клетки карты Карно (рис. 1.6) заносятся соответствующие значения функции у. Или в карту Карно можно занести только единичные значения для всех минтермов СДНФ функции.

В результате объединения клеток карты с единичными значениями получены три контура (черного цвета) по две клетки в каждом. Составив выражения для каждого контура, получим общую аналитическую запись функции:

(1.4)

Такая форма функции называется минимальной дизъюнктивной нормальной формой (МДНФ).

При объединении клеток карты с нулевыми значениями также получены три контура (голубого цвета) по две клетки в каждом. Составив выражения для каждого такого контура, получим общую аналитическую запись функции:

(1.5)

Полученная форма функции называется минимальной конъюнктивной нормальной формой (МКНФ).

Минимизация с помощью карт Карно не приводит к однозначной форме и для получения наиболее простой формы необходимо рассматривать всевозможные варианты склеивания.

При числе аргументов, большем пяти, используют обычно другие методы минимизации — применение карт Карно становится трудоемким.

Встречается необходимость минимизировать функцию, значения которой при некоторых комбинациях переменных не определены. Такой случай может иметь место, если значение функции при этих комбинациях безразлично или если определенные комбинации переменных невозможны по условиям задачи. На таких избыточных (запрещенных, факультативных) комбинациях можно придать функции любое значение — 0 или 1.

Пусть, например, функция представлена в виде карты Карно, изображенной на рис. 1.7. Здесь в клетках J=0 и J=1 функция у не определена и отмечена звездочкой (*). При объединении контурами единичных значений функции целесообразно клетке J=1 придать значение «1», а J=0 – значение «0». Тогда можно объединить в один контур 4 клетки. В результате аналитическая запись функции в форме МДНФ будет иметь следующий вид:

Рациональное доопределение функции может оказаться весьма эффективным для ее минимизации и, следовательно, для упрощения устройства, реализованного в соответствии с ней.

Базисные логические элементы

Известно, что совокупность элементарных логических функций ИЛИ, И, НЕ представляет функционально полную систему (базис), т. е. с помощью этих функций может быть записана логическая функция любой сложности.

Такие операции реализуются (выполняются) логическими элементами (ЛЭ) в соответствии с аксиомами алгебры логики.

Логические элементы могут быть представлены идеализированными моделями, т. е. условными графическими обозначениями (УГО), выполненные в соответствии с ГОСТ УГО ЛЭ изображаются прямоугольниками, в которых ставится символ выполняемой операции, а на линиях входных и выходных переменных могут изображаться окружности (индикаторы инверсии), если эти переменные имеют в выражении инверсные значения (рис.1.8).

Логические элементы физически могут быть реализованы в виде электрических ключевых схем или электронных схем с применением диодов и транзисторов.

Логические элементы И—НЕ, ИЛИ—НЕ

Значительный интерес представляют следующие функции двух переменных:

функция И—НЕ ;

функция ИЛИ—НЕ. .

Таблицы истинности этих функций приведены в табл. 4 и табл. 5 соответственно.

Функционально элемент И—НЕ представляет собой совокупность конъюнктора и инвертора (рис. 1.12, а), а элемент ИЛИ—НЕ — совокупность дизъюнктора и инвертора (рис. 1.12, в).Условное изображение элемента И—НЕ показано на рис. 1.12, б,а элемента ИЛИ—НЕ — на рис. 1.12, г.

Можно показать, что набором однотипных элементов И—НЕ (ИЛИ—НЕ) можно реализовать функции И, ИЛИ, НЕ. Этим доказано, что каждый такой набор является базисом, так как базисом является совокупность элементов И, ИЛИ, НЕ.

Функцию И—НЕ называют функцией Шеффера (штрихом Шеффера), обозначая ее в виде у=x₁|x₂, а функцию ИЛИ — НЕ — функцией Пирса (стрелкой Пирса), обозначая ее в виде у=х₁↑x₂. Базис И—НЕ называют базисом Шеффера, а базис ИЛИ—НЕ — базисом Пирса.

Логическое устройство, реализованное в базисе И—НЕ (ИЛИ—НЕ), имеет преимущества по сравнению с устройством, реализованным в базисе И, ИЛИ, НЕ. Оно состоит в уменьшении номенклатуры элементов до одного типа, что упрощает компоновку устройства и его ремонт; другое связано с наличием в каждом элементе инвертора (усилителя), который компенсирует затухание потенциалов при передаче их через конъюнктор или дизъюнктор элемента. Благодаря этому не накапливается затухание сигнала при прохождении его через ряд последовательно включенных элементов, что могло бы вызвать снижение уровня U¹ (логической 1) до уровня U⁰ (логического 0). Кроме того, инвертор увеличивает нагрузочную способность элемента: подключение допустимого числа других элементов к его выходу не вызывает заметного уменьшения на нем уровней потенциалов (что особенно важно для U¹), а наличие емкости на выходе не вызывает длительного переходного процесса при смене потенциалов.

Построение логических схем по аналитическим выражениям функций

Логической схемой (ЛС) называется схема, составленная из ЛЭ путем соединения выходов одних ЛЭ со входами других.

Построение логических схем по аналитическим выражениям функций другими словами называется реализацией логических функций.

Существует ряд базисов, из числа которых были рассмотрены И, ИЛИ, НЕ; И—НЕ и ИЛИ—НЕ. В каждом базисе могут быть реализованы любые логические функции.

Схема, которая получается на основании логического выражения, носит название комбинационной схемой.

При переходе от логического выражения к логической схеме элементы, выполняющие в выражении те или иные операции, располагаются в схеме, начиная от входов.

Рассмотрим принцип построения логических схем на примере выражения (1.1) для мажоритарной функции в СДНФ, полученной ранее:

.

На логической схеме сначала изображаются 3 инвертора, для отрицания входных переменных, затем 3 элемента И на три входа каждый и наконец 1 элемент ИЛИ на четыре входа. После размещения элементов изо
бражаются электрические связи (проводники), соединяющие входные переменных и выходные сигналы одних элементов со входами других согласно логическому выражению.

Построение ЛС основано на следующих правилах:

1. Выход ЛЭ можно подсоединять ко входам нескольких ЛЭ;

2. На входы ЛЭ можно подавать сигналы, представляющие собой константы 0 и 1.

3. Выходы ЛЭ нельзя соединять вместе;

4. Выходы ЛЭ нельзя подключать к собственным входам.

Логическая схема для рассматриваемой функции в СДНФ реализована в базисе И, ИЛИ, НЕ и изображена на рис. 1.13.

Аналогично строится логическая схема для этой же функции после её минимизации по аналитической записи в МДНФ (1.4):

Такая логическая схема в булевом базисе приведена на рис.1.14. Сравнив две построенные схемы можно видеть что последняя схема содержит в два раза меньшее количество ЛЭ, которые имеют меньшее число входов.

Можно построить логическую схему в булевом базисе для этой же функции после её минимизации по аналитической записи в МКНФ (1.5),

,

которая представлена на рис. 1.15.

Часто необходимо построить схему из однотипных ЛЭ. Для этого требуется реализовать схему в базисе И–НЕ или в базисе ИЛИ–НЕ. Переход к другому базису осуществляется путем выполнения тождественных преобразований исходных выражений в формах СДНФ, МДНФ или СКНФ, МКНФ.

Для построения схемы в базисе И–НЕ можно преобразовать аналитическую запись функции в МДНФ (1.4) путем её двойного инвертирования и применения закона Де Моргана:

.

Логическая схема в базисе И–НЕ приведена на рис.1.16.

Для построения схемы в базисе ИЛИ–НЕ можно преобразовать аналитическую запись функции в МКНФ (1.5) также путем её двойного инвертирования и применения закона Де Моргана:

Логическая схема в базисе ИЛИ–НЕ приведена на рис.1.17.

Далее рассматривается несколько простых логических функций, реализуемых элементами рассмотренных базисов.

Элемент «Сравнение». На выходе такого элемента должна быть логическая 1, если на входах одновременно присутствуют одинаковые логические переменные (единицы или нули).

Легко установить, что при равнозначности переменных х₁ и х₀ конъюнкции их прямых или инверсных значений равны единице, т. е. функция рассматриваемого элемента выразится в базисе как

Используя теорему де Моргана, представим эту функцию в базисе И—НЕ:

На рис. 1.17, а, б приведены логические схемы элемента «Сравнение» на ЛЭ базисов И, ИЛИ, НЕ и И—НЕ соответственно. Условное графическое изображение элемента дано на рис. 1.18, в.

Элемент «Исключающее ИЛИ». На выходе такого элемента должна быть логическая 1, если на входах присутствуют неравнозначные логические переменные:

у=1, если х₁=1, x₀=0или ;х₁=0, x₀= 1.

Исходя из самого определения, легко записать логическую функцию: конъюнкции неравнозначных переменных должны быть равны единице, т. е.

.

Применяя теорему де Моргана, запишем эту функцию в базисе И—НЕ:

,

где правая часть выражения дополнительно дважды инвертирована.

Функциональные схемы рассматриваемого элемента в соответствии с выражениями приведены на рис. 1.18, а, б. Условное обозначение элемента «Неравнозначность» дано на рис. 1.18,в.

Элемент «исключающее ИЛИ» иначе называют сумматором по модулю два: сумма двоичных цифр дает в результате 1; если одна из них 1, а другая — 0; эта сумма равна 0, если обе цифры одинаковы – 0 или 1.