Принцип суперпозиции. Функциональная полнота системы логических функций

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

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

f ₁(x)=x₁x₂;

f ₂(x)=x₃Åx₄,

можно, пользуясь принципом суперпозиции, получить следующие функции:

f ₃(x)=x₁(x₃Åx₄);

f ₄(x)= (x₁x₂)Åx₄.

Функция f ₃(x) получена путем подстановки в функцию f ₁(x) вместо переменной х₂ функции f ₂(x). Функция f ₄(x) получена из функции f ₂(x) путем подстановки вместо переменной х₃ логической функции f ₁(x).

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

Рассмотрим связи между некоторыми элементарными функциями.

Из таблицы 2.5 следует, что функция f ₁(x) на всех наборах принимает значения, противоположные функции f ₁₄(x).

Используя принцип суперпозиции, запишем

= = .

Приведем без пояснения некоторые широко применяемые соотношения, связывающие элементарные функции:

= ;

= ;

= ;

= ;

= ;

= ;

= ;

= ;

;

= .

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

Система логических функций f ₁(x), f ₂(x),..., f _s(x) называется функционально полной, если любая логическая функция может быть представлена суперпозицией этих функций, взятых в любом конечном числе экземпляров.

Функционально полная система логических функций f ₁(x), f ₂(x),..., f _s(x) называется минимальной, если удаление из нее хотя бы одной функции превращает систему в неполную. При рассмотрении совокупности логических функций f ₁(x), f ₂(x),..., f _s(x) возникает вопрос, как установить, является ли данная совокупность функций полной. Ответ на этот вопрос дает теорема о функциональной полноте (теорема Поста-Яблонского), которая устанавливает необходимые и достаточные условия функциональной полноты произвольной совокупности логических функций [1].

Анализ функций двух переменных по указанным в теореме свойствам показывает, что существует большое число различных функционально полных систем элементарных логических функций. Перечислим некоторые из них:

- функция Шеффера (И-НЕ);

- функция Пирса (ИЛИ-НЕ);

- функция И и НЕ;

- функция ИЛИ и НЕ;

- функция импликации и константы 0 и т.д.

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

Особый интерес, с практической точки зрения, представляют функционально полные системы, содержащие функции константы 0 и 1, так как эти функции просто реализуются в цифровых устройствах. К таким системам логических функций относятся следующие совокупности функций:

- равнозначность и дизъюнкция;

- импликация;

- сумма по модулю два и дизъюнкция.

Указанные совокупности функций при наличии констант 0 и 1 позволяют реализовать произвольную логическую функцию любого конечного числа переменных. Логические функции описывают условия функционирования цифровых устройств, т.е. устройств, входные и выходные сигналы которых можно отождествлять с нулевыми и единичными значениями логических переменных или функций. Для построения цифровых устройств, реализующих произвольные логические функции, необходимо располагать совокупностью элементов, которые реализовали бы все функции, входящие в одну из функционально полных систем логических функций. Условимся в дальнейшем элементы, реализующие логические функции, называть логическими элементами. Логическому элементу будем приписывать название логической функции. Например, для краткости вместо “логический элемент, реализующий функцию ИЛИ-НЕ”, будем говорить “логический элемент ИЛИ-НЕ”.

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

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

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

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

С другой стороны, увеличение числа различных логических функций, реализуемых элементами, приводит к увеличению стоимости выпускаемых систем логических элементов. Отсюда следует, что существует оптимальное количество различных элементов, входящих в систему, позволяющее получить цифровые устройства минимальной стоимости. В настоящее время состав функционально полных систем логических элементов, выпускаемых промышленностью, определяется из опыта проектирования цифровых устройств, так как точных методов определения оптимальных совокупностей логических элементов не найдено. При начертании схем цифровых устройств используются условные графические обозначения логических элементов, которые установлены ГОСТом ЕСКД 2.743-82. На рис. 2.1 приведены условные графические обозначения наиболее распространенных логических элементов. Размеры

Рис. 2.1

 

логических элементов на схеме определяются ГОСТ и варьируются в зависимости от числа входов, выходов элементов и формата чертежа.

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