Минимизация функций алгебры логики. Схемы из функциональных элементов

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

Рис. 1. Два способа изобразить композицию

Такое представление отнюдь не является чисто теоретическим. В течение нескольких десятков лет электронная промышленность выпускает микросхемы, которые выполняют логические операции. Такая микросхема имеет электрические контакты, напряжение на которых кодирует логические значения И и Л. Конкретное напряжение зависит от типа схемы, но обычно это единицы вольт, и высокий потенциал (относительно заземления) считается единицей, а низкий- нулем.

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

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

Поэтому вопрос о том, сколько элементов нужно для реализации той или иной функции, представляет большой интерес - как практический, так и философский. (Одна из центральных проблем математики и информатики, так называемая "проблема перебора", может быть сформулирована в этих терминах.)

Минимизация функций алгебры логики

Постановка задачи минимизации функций алгебры логики. Этапы минимизации. Методы минимизации. Расчетный метод. Карты Карно. Геометрический метод. Примеры минимизации. Метод Квайна.

Основные понятия

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

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

 Таблица 1 – Табличное задание ФАЛ

№ наб.	x2	x1	x0	y
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	0

 

Пример 1 ФАЛ, заданную таблицей истинности (табл. 1), можно представить следующими выражениями

(1)

(2)

(3)

(4)

 В выражении (1), записанном в СДНФ, пять слагаемых по три буквы в каждом, а всего 15 букв и три инвертора, в то время как в выражении (2) три слагаемых по две буквы в каждом, а всего 6 букв и три инвертора. Выражение (2) является минимальной дизъюнктивной формой для данной ФАЛ.

В выражении (3), записанном в СКНФ, три сомножителя по три буквы в каждом, а всего 9 букв и три инвертора, в то время как в выражении (4) два сомножителя по две и три буквы, а всего 5 букв и три инвертора. Выражение (4) является минимальной конъюнктивной формой для данной ФАЛ.

Применяя скобочные формы и формы с групповыми инверсиями, выражения (2) и (4) можно еще упростить:

(5)

где 5 букв и два инвертора.

(6)

где 5 букв и один инвертор.

  Методы минимизации

К настоящему времени широкое применение получили:

1. Расчетный метод (метод непосредственных преобразований).

2. Расчетно-табличный метод (метод Квайна-МакКласки).

3. Метод Петрика (развитие метода Квайна-МакКласки).

4. Табличный метод (карты Карно).

5. Геометрический метод.

6. Метод факторизации.

7. Метод функциональной декомпозиции и др.

Первый метод применяется при числе переменных n <= 3 и основан на использовании операций склеивания, поглощения и развертывания. Ниже он будет рассмотрен подробно.

Второй и третий методы используются при n ≤ 16 в профессиональных разработках и ориентированы на использование САПР с применением ЭВМ. Здесь они рассматриваться не будут. Четвертый метод является самым распространенным инженерным методом минимизации ФАЛ для n ≤ 6 и будет подробно рассмотрен.

Шестой метод не имеет каких-либо существенных достижений при решении общих задач, более простых, чем метод перебора всех формул ФАЛ даже для n = 3. Практически он используется для уменьшения сложности минимальных ДНФ и КНФ, полученных с использованием первого или четвертого методов. Он основан на использовании скобочных форм и форм с групповыми инверсиями.

Седьмой метод основан на представлении ФАЛ, зависящей от n переменных, в виде суперпозиций функций, зависящих от меньшего числа переменных, для которых можно применить выше перечисленные методы и здесь не рассматривается.

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

При выполнении процедур канонической минимизации большую роль играют понятия импликанты и простой импликанты ФАЛ.

Определение 1. Булева функция называется импликантой булевой функции , если на любом наборе значений переменных , на котором значение функции ‘Z’ равно 1, значение функции ‘Y’ также равно 1.

Определение 2. Простой импликантой функции ‘y’ называется всякое элементарное произведение , являющееся импликантой функции ‘Y’ и такое, что никакая его собственная часть (то есть произведение, полученное из произведения ‘Z’ выбрасыванием одного или нескольких сомножителей ) уже не является импликантой функции ‘y’.

Так как в дальнейшем будут использоваться только простые импликанты, опустим слово “простые”, то есть если в тексте встречается понятие “импликанта”, то надо помнить, что имеется в виду “простая импликанта”.