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

Обновлено: 05.07.2024

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

В связи с этим, возникает задача минимизации логических функций в некотором классе формул. В частности, в классах ДНФ и КНФ.

Минимальная ДНФ Такая ДНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ. Минимальная КНФ Такая КНФ, которая содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей КНФ.

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

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

\[ \;\overline\;x_2x_3x_4 \vee \;\overline\;x_2\;\overline\;x_4 = \;\overline\;x_2x_4 (x_3 \vee\;\overline\;) = \;\overline\;x_2x_4 \mathbin1 = \;\overline\;x_2x_4. \]

Аналогично для КНФ:

\[ (\;\overline\;\vee x_2\vee x_3\vee x_4) (\;\overline\;\vee x_2\vee\;\overline\;\vee x_4) = \;\overline\;\vee x_2\vee x_4\vee x_3\;\overline\; = \;\overline\;\vee x_2\vee x_4\vee 0 = \;\overline\;\vee x_2\vee x_4. \]

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

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

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

Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

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

Булевы функции $N$ переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе $2^N$ различных элементарных членов.

Элементарные члены СДНФ или СКНФ образуют структуру, топологически эквивалентную $N$ -мерному кубу. Действительно, если рассматривать набор значений функции $x_1,\,\ldots,\,x_N$ как $N$ -мерный вектор $\$ , мы получим набор точек, лежащих на ортах $N$ -мерной системы координат, и удаленных друг от друга на $1$ . Другими словами, мы получим $N$ -мерный гиперкуб с ребром $1$ .

Аннотация: Цель лекции: познакомить студента с основными методами минимизации логических функций: методом Квайна – Мак-Класки, методом минимизирующих карт. Ключевые слова: импликанта, простая импликанта, сокращенная нормальная форма, тупиковая нормальная форма.

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

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

Понятие "упрощение" требует определенных договоренностей, что под этим будет пониматься. Упрощение можно рассматривать с точки зрения числа переменных в получаемоq эквивалентной функции, уменьшения количества отрицаний в результирующем выражении, более простой схемотехнической реализации при переводе получающейся ФАЛ на уровень интегральных микросхем и так далее.

Мы будем считать, что дизъюнктивная или конъюнктивная нормальная форма являются минимальными, если они содержат наименьшее суммарное число переменных среди всех ДНФ или КНФ, эквивалентных ей. При этом количество отрицаний над переменными учитывать не будем.

Методы минимизации можно разделить на несколько типов:

Метод непосредственных преобразований логических функций.
Метод неопределенных коэффициентов.

Аналитические методы (метод Квайна1 1 Квайн, Уиллард Ван Орман — американский философ, логик и математик , метод Квайна – Мак-Класки).

Рассмотрим их более подробно. Рассмотрение будем проводить на основе дизъюнктивных нормальных форм. Для КНФ теоретические рассуждения будут аналогичными.

В то же время, иллюстрировать соответствующие положения будем как на примерах дизъюнктивны, так и конъюнктивных форм.

Если некоторая логическая функция равна нулю на тех же наборах, на которых равняется нулю другая функция f, то говорят, что функция входит в функцию f. Другими словами, функция входит в функцию f тогда, когда она накрывает нулями все нули функции f, а единицы функции f могут быть накрыты как нулями, так и единицами функции .

Очевидно, что ФАЛ "Константа ноль" входит во все функции, а в ФАЛ "Константу единица" входят все функции.

$\phi$

Функцию , входящую в данную функцию f, называют ее импликантой.

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

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

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

Существует несколько методов минимизации логических функций:

-метод непосредственных преобразований;

-метод Квайна и Мак-Класки.

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

Метод непосредственных преобразований не всегда удобен при практическом выполнении минимизации. Метод Квайна и Мак-Класки состоит в применении для минимизации логической функции ЭВМ. Его использование целесообразно, когда число входных переменных превышает 6 – 7. При незначительном числе аргументов минимизацию логической функции чаще всего выполняют методом Карно-Вейча. Рассмотрим его сущность.

Диаграмма Вейча (карта Карно) является упрощенной формой записи таблицы истинности логической функции. Основное отличие между диаграммой Вейча и картой Карно состоит в нумерации строк и столбцов таблицы. Рассмотрим методику минимизации логической функции с помощью диаграммы Вейча.

Рисунок 5.6 – Примеры диаграмм Вейча

Цифры, записанные в клетки диаграмм Вейча на рисунке 5.6, представляют собой номера наборов переменных в таблице истинности.

При склеивании переменных нужно руководствоваться следующими правилами:

а) все клетки, содержащие единицы (при записи функции в дизъюнктивной форме) или нули (при записи в конъюнктивной форме), должны быть замкнутыми в прямоугольные контуры. Единичные контуры могут объединять несколько единиц, но не должны содержать внутри себя нулей. Нулевые контуры могут объединять несколько нулей, но не должны содержать внутри себя единиц. Одна и та же единица (или ноль) может одновременно входить в несколько единичных (нулевых) контуров. Число клеток в контуре равняется 2 i , где i = 0, 1, 2, 3, 4, . ;

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

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

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

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

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

Для получения по диаграмме Вейча минимального выражения логической функции следует руководствоваться правилом: единицы и нули должны объединяться минимальным числом наибольших контуров.

Рассмотрим пример минимизации логической функции трех переменных у = f(x₁, x₂, x₃), заданной таблицей истинности (рисунок 5.5), воспользовавшись методом Карно-Вейча. Для начала воспользуемся представлением функции в дизъюнктивной нормальной форме. В этом случае диаграмма Вейча должна быть заполнена, как показано на рисунке 5.7.

Рисунок 5.7 – Минимизация функции к виду ДНФ

Рисунок 5.8 – Минимизация функции к виду КНФ

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

Выражения (5.3) и (5.4) описывают структуру логического устройства, алгоритм функционирования которого задан функцией у (рисунок 5.5). Несмотря на то, что полученные выражения разные по виду, а, следовательно, и схема логического устройства в каждом случае будет выполнена по разному, сигналы на выходах этих схем на одних и тех же номерах разрешенных наборов входных переменных будут одинаковы.

Существует несколько методов минимизации логических функций:

-метод непосредственных преобразований;

-метод Квайна и Мак-Класки.

Рисунок 5.6 – Примеры диаграмм Вейча

При склеивании переменных нужно руководствоваться следующими правилами:

Рисунок 5.7 – Минимизация функции к виду ДНФ

Рисунок 5.8 – Минимизация функции к виду КНФ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 5
Х₁	X₂	У_ИЛИ-НЕ

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

Таблица 4
Х₁	X₂	У_И-НЕ

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

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

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

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

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

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

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

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

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

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

Рассмотрим принцип построения логических схем на примере выражения (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, x₀=0или ;х₁=0, x₀= 1.

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

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

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

Читайте также: