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

Алгоритм образования СКНФ по таблице истинности

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

2. Для каждого выбранного набора записать элементарные дизъюнкции, содержащие без инверсии переменные, принимающие в соответствующем наборе значение 0 и с инверсией — переменные, принимающие значение 1.

3. Соединить элементарные дизъюнкции знаком конъюнкции.

Пример 4. Пусть логическая функция F задана таблицей истинности:

X	Y	Z	F	СДНФ	СКНФ
				–	ÚÚ
				–	ÚÚ
				–	ÚÚ
					–
				–	ÚÚ
					–
					–
					–

В соответствии с приведенными выше алгоритмами логическую функцию F(X, Y, Z), заданную таблицей истинности, можно представить аналитически:

Обратите внимание на тот факт, что СДНФ и СКНФ являются инверсными по отношению друг к другу, т. е. если одна из них в некотором наборе равна 1, то другая на этом же наборе равна 0.

Пример 5. Покажем, как для логической функции, заданной аналитически, можно построить таблицу истинности по СДНФ.

F(X, Y, Z) = (X & Y & Z)v(X & Y & Z)Ú(X & Y & Z).

По определению СДНФ только на наборах 011, 010, 111 логическая функция F (X, Y, Z) принимает значение 1; во всех остальных случаях — значение 0.

X	Y	Z	F

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

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

Пример. Пусть некоторая логическая функция представлена в СДНФ.

ÚÚÚ

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

Первая и вторая, а также третья и четвертая конъюнкции — соседние. В результате их склеивания получим:

ÚÚÚÚÚ

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

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

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

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

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

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

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

Дата добавления: 2014-01-06