4.8. Минимизация пф в универсальных базисах и-не, или-не

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

Базисы Пирса и Шеффера связаны с каноническим базисом формулами де Моргана, которые в общем виде записываются следующим образом:

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

Пусть подлежащая минимизации ПФ задана в СДНФ или СКНФ. Рассмотрим универсальный метод перехода к базисам И-НЕ, ИЛИ-НЕ.

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

Тогда СДНФ и СКНФ в общем виде можно записать как

Воспользовавшись законом де Моргана, получим

В приведенных выражениях инверсии и могут быть выражены через операции «стрелка Пирса» и «штрих Шеффера»:

откуда

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

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

Рассмотрим пример.

Осуществим переход от КНФ к базису ИЛИ-НЕ (стрелка Пирса).

Осуществим переход от ДНФ к базису И-НЕ (штрих Шеффера).

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

т.е. в качестве инвертора выступает элемент И-НЕ (ИЛИ-НЕ), все входы которого объединены в один.

При синтезе КС в универсальных базисах может возникнуть необходимость в переходе от представления функции в ДНФ к представлению в базисе ИЛИ-НЕ или в переходе от представления функции в КНФ к представлению в базисе И-НЕ. В такой ситуации можно пользоваться следующими формулами:

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

Для перехода к базису 2И-НЕ:

Для перехода к базису 2ИЛИ-НЕ:

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

Таблица 4.25

	x2
x1	0	1	1	1
	0	0	0	1	x3
	0	0	0	1
	0	1	0	1
		x4

Минимальные ДНФ и КНФ для этой функции можно записать в виде

Поскольку минимальная КНФ содержит меньшее число букв, используем ее для получения формы представления, близкой к минимальной, в базисе ИЛИ-НЕ.

Преобразуем полученную форму переключательной функции к представлению в базисе 2ИЛИ-НЕ.

.

На рис. 4.3 изображена КС, соответствующая полученной в результате минимизации ПФ, представленной в базисе 2ИЛИ-НЕ. В качестве инверторов также используются логические элементы 2ИЛИ-НЕ.