86371 (Булевы функции), страница 6

Что касается первого этапа — поиска всех простых имплицент, то практически все методы минимизации ДНФ имеют свои аналоги для КНФ. Расссмотрим это подробнее.

Соотношение склеивания по Квайну:

(A v x) (A v ) =(A v x) (A v )A =A

Метод Квайна для конъюнктивных форм:

1. Выполняются все неполные склеивания в СКНФ.

2. Выполняются все поглощения.

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

4. После получения сокращенной КНФ строится имплицентная матрица, по которой находятся “лишние” имплиценты.

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

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

	х1
	0	1		1	1
	1	1		1	0

б)

В реальных задачах очень часто бывает так, что значение булевой функции на некоторых наборах не определено и может доопределяться произвольно. Выходные сигналы на этих наборах могут принимать любые значения - 0 или 1. Входные наборы, которые дают неопределенное значение функции называются запрещенными. При синтезе схем, реализующих неполностью определенные функции выходным сигналам, соответствующим запрещенным наборам, придают такие значения, при которых можно построить наиболее простую схему. В этом случае доопределение функции целесообразно производить таким образом, чтобы ее минимальная нормальная форма имела наименьшее число букв из всех возможных вариантов доопределения. Рассмотрим простой пример (рис.5,6.).

Рисунок 5

	х1
	0	-		-	1
	1	1		-	0

Рисунок 6

	х1
	0	0		1	1
	1	1		0	0

б)	х1
	0	0		0	1
	1	1		0	0

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

1. Найти любым известным способом сокращенную ДНФ функции, получающейся доопределением единицами исходной функции f на всех неопределенных наборах.

2. Выбрать минимальную ДНФ по импликантной матрице, где в столбцах выписаны лишь те конституенты единицы функции f, которые соответствуют полностью определенным единичным наборам.

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

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

1. 11.Mинимизация систем булевых функций

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

Задача минимизации систем булевых функций хорошо исследована в классе функционально полных систем: «дизъюнкция», «конъюнкция», «отрицание». Рассмотрим один из наиболее распространенных методов минимизации.

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

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

2. Произвести минимизацию СДНФ функции L, конституентами единицы которой являются все элементы множества A. При выполнении склеивания двух конституент единицы каждой вновь образуемой элементарной конъюнкции присвоить признак, состоящий из номеров функций, общих для двух склеиваемых конституент единицы. Последнее справедливо и для двух склеиваемых элементарных конъюнкций с признаками. Если признаки склеиваемых конституент единицы не содержат общих номеров, то склеивание не производится. Поглощение производится только для элементарных конъюнкций с одинаковыми признаками. Полученные в результате склеивания и поглощения конъюнкции называются простыми импликантами системы функций.

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

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

Здесь уместно сказать о типах и классах булевых функций в определении Шеннона. Выше уже упоминалось о взаимно однозначном соответствии между схемами и формами представления булевых функций. В то же время, очевидно, что одна и та же схема может реализовать несколько различных булевых функций, если какие-то входные переменные поменять местами. В этом случае функции принадлежат к одному классу. Если же переменные переставлять, допуская их отрицания, то функции принадлежат к одному типу. Если найти абсолютно минимальную форму представления хотя бы одной функции каждого класса и построить соответствующие таблицы, то задачу синтеза переключательных схем можно было бы свести к поиску нужного класса в таблице. Такие таблицы для функций 4-х переменных были составлены (при реализации функций контактными схемами), практического распространения этот подход не получил. Одной из причин является тот факт, что число классов очень быстро растет с ростом n.

Выводы

Известна более простая задача — задача факторизации, заключающаяся в упрощении дизъюнктивно-конъюнктивных форм, допуская отрицания лишь над переменными. Часто она называется задачей скобочной минимизации, и в настоящее время известно достаточно много методов такого упрощения. В общем виде задача факторизации не решена, но для булевого базиса, в ряде случаев, используя операцию вынесения за скобки общих членов, можно получить скобочную форму, значительно более простую, чем минимальная ДНФ булевой функции.

Литература

1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа” 1987.

2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.

3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.

4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.

5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. - Минск. “Вышэйшая школа”. 1980.