И инверсных логических функций

⇐ ПредыдущаяСтр 3 из 11Следующая ⇒

Частично (не полностью) определенными называют функции, значения которых заданы лишь для части множества возможных наборов их переменных. Такие функции достаточно часто встречаются в задачах проектирования КЦУ, где их происхождение обусловлено тем, что некоторые сочетания (комбинации) входных переменных при работе КЦУ не имеют места.

Наборы переменных, для которых функция не определена, называют избыточными или запрещенными. Например, избыточные наборы будут иметь место при реализации двоично-десятичного кода, т.е. при представлении десятичных цифр от 0 до 9 двоичным кодом. Действительно, для такого представления необходимо использовать четыре двоичные переменные (четыре двоичных разряда), и из общего числа 16 наборов этих переменных использовать только первые 10. Следовательно, 6 наборов оказываются избыточными.

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

Пример 4. Минимизировать логическую функцию, заданную своей таблицей истинности (рис. 5, а). Значения функции, соответствующие трем последним наборам входных переменных, не определены (что отмечено * в столбце y_исх). На карте Карно рассматриваемой функции (рис. 5, б) ячейки для избыточных наборов также отмечены звездочками. Доопределение функции единицами для всех избыточных наборов позволяет представить ее МДНФ в виде:

Для сравнения приведем выражение исходной функции:

которую без приема доопределения упростить невозможно.

В пределах определения (на допустимых наборах входных переменных) значения функций у_исх и у_доопр совпадают. Выяснение тождественности этих функций на запрещенных наборах не представляет интереса, так как при работе КЦУ они не будут иметь места.

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

х₁	х₂	х₃	у_исх	у_доопр
0			* * *

а)

		х₁

			*
х₃			*

	х₂

б)

Рис. 5. Таблица истинности (а) и карта Карно (б)

частично определенной функции

Пример 5. Упростить функцию, заданную таблицей истинности (рис. 6).

Решение. СДНФ требуемой (прямой) функции

х₁	х₂	х₃	y

Рис. 6. Таблица истинности функции

Поскольку столбец усодержит шесть единиц из восьми возможных, то столбец для содержит лишь две единицы, что и отражено в таблице (рис. 6).

Для СДНФ будет значительно проще:

Последнее выражение более обозримо, чем для у, и легко минимизируется:

, откуда .

1.7 Преобразование минимальных форм логических функций к виду, реализуемому ЛЭ заданного функционально полного набора

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

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

Набор логических функций инверсия (НЕ), дизъюнкция (ИЛИ) и конъюнкция (И) получил наименование основного (ОФПН).

Среди других наборов функций, образующих ФПН, особый интерес представляют так называемые монофункциональные наборы, содержащие всего одну булеву функцию. Таковыми, в частности, являются набор, состоящий только из функции «штрих Шеффера» (И-НЕ) и набор, состоящий только из функции «стрелка Пирса» (ИЛИ-НЕ).

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒