Функционально полный набор логических элементов

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

Закон функционирования логического элемента можно описать системой ПФ:

Таким образом, логический элемент рассматривается, по существу, как «черный ящик» с заданным законом функционирования, но с неизвестной внутренней структурой.

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

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

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

При составлении логических схем из элементов используют два приема:

1. последовательное соединение элементов и

2. перестановку входов.

Этим приемам соответствуют математические операции суперпозиции и подстановки аргументов.

Суперпозиция состоит в подстановке вместо аргументов булевой функции других булевых функций и в перенумерации (переименовании) аргументов. Указанная подстановка возможна, так как и аргументы и сами булевые функции могут принимать только два значения 0 и 1.

Рисунок 2.3 – Принцип суперпозиции

Перестановка входов:

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

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

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

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

К логическим элементам предъявляют ряд технических требований:

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

2. Схемы логических элементов должны быть максимально простыми – они должны содержать минимальное число радиодеталей.

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

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

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