Что такое функционально полная система логических элементов

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

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

И (155ЛИ…), ИЛИ (155ЛЛ…), НЕ (155ЛН…). Этот набор является функционально полным, потому что любая переключательная функция может быть представлена в совершенной дизъюнктивной или конъюнктивной нормальной форме, а для её реализации требуются только эти логические элементы.
И-НЕ (155ЛА…). Можно показать с помощью формул де Моргана, что на этом элементе можно реализовать логические функции И, ИЛИ, НЕ, а следовательно и любую переключательную функцию.
ИЛИ-НЕ (155ЛЕ…). Всё вышесказанное относится и к элементу ИЛИ-НЕ.

Элемент и – не Элемент или – не

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

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

Предположим, что нам надо реализовать переключательную функцию, заданную в таблице 1.2 на логических элементах типа И-НЕ. Минимальная форма для неё найдена с помощью диаграммы Вейча в таблице 1.3. Представим теперь функцию в виде, удобном для реализации на элементах типа И-НЕ. Для этого возьмём двойную инверсию от левой и правой части выражения, а затем раскроем внутреннюю инверсию в правой части. Правая часть последнего выражения полностью соответствует структуре элемента И-НЕ. Нарисуем теперь принципиальную схему устройства, реализующего эту функцию. Рис.1.2 Реализация переключательной функцииF(ABC). Логические схемы, у которых выходной сигнал однозначно определяется комбинацией сигналов на входе, называются комбинационными. Дальнейшая реализация логических функций может быть осуществлена аппаратно и программно. В обоих случаях в работе должны быть использованы средства автоматизации работы над проектами. В случае аппаратной реализации по полученным чертежам принципиальной схемы изготавливаются печатные платы, из которых, после установки на них микросхем и электронных элементов, собирается опытный образец изделия. В этом процессе используются различные программы автоматизирования изготовления изделий электроники, например PCAD, ORCAD. После изготовления опытного образца, его необходимо подвергнуть различным испытаниям и прежде всего – на правильность функционирования. Такие же испытания можно проводить и на изделиях, вышедших из строя в процессе работы, для определения причины неисправности. Однако испытания можно провести и до изготовления реального опытного образца. При создании современного управляющего устройства широко применяются математические расчёты, моделирование условий работы объекта и системы управления, макетирование отдельных устройств и опытная отработка всего процесса управления. Во время эксперимента проводятся необходимые измерения, подтверждающие правильность функционирования объекта. Современный компьютер позволяет соединить эти действия в одном творческом процессе, который существенно сокращает время и материальные затраты на разработку, но требуют и более высокой квалификации проектировщика. Это может быть сделано в среде графического программирования LabVIEW.

Большая Энциклопедия Нефти и Газа

Функционально полная система логических элементов — это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. Поскольку любая логическая функция представляет собой комбинацию простейших функций — дизъюнкции, конъюнкции и инверсии, то набор из элементов трех типов, реализующих соответственно функции И, ИЛИ и НЕ, естественно, является функционально полным. Например, функцию ab — — ab можно реализовать с помощью двух ячеек НЕ ( они нужны, чтобы получить инверсии а и Ь), двух ячеек И, необходимых для того, чтобы получить логические произведения аЪ и ab, и ячейки ИЛИ, суммирующей эти произведения. [1]

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

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

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

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

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

Анализ и синтез электронных узлов ЭВМ и ВС на основе выбранного базиса функционально полной системы логических элементов . Исходными данными для этого этапа служат характеристики устройств ЭВМ и ВС, определенные во время синтеза логической структуры. [9]

Анализ и синтез электронных узлов и операционных блоков ЦВМ и ВС на основе выбранного базиса функционально полной системы логических элементов . Исходными данными для этого этапа разработки служат характеристики устройств ЦВМ и ВС, определенные во время синтеза их логических структур, а также информация о доступной электронно-технологической базе их производства. [10]

Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-нибудь функционально полную систему логических элементов ( элементарных автоматов без памяти), является структурно полной системой. Существует общий конструктивный прием ( канонический метод структурного синтеза) позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных конечных автоматов к задаче структурного синтеза комбинационных схем. [11]

Так как любая сложная логическая функция может быть выражена с помощью логических — функций ( И, ИЛИ, НЕ), то система-функций ( И, ИЛИ, НЕ) называется функционально полной системой логических элементов . Количество типов вспомогательных элементов выбирается с учетом особенностей логических элементов, используемых в ЭЦВМ. Например, в управляющих ЭЦВМ в систему элементов входит некоторое число аналоговых элементов. Это связано с передачей и обработкой информации представленной в непрерывной форме. [13]

Схемы диодной логики строят на полупроводниковых диодах, обычно в комбинации с резисторами. Для получения функционально полной системы логических элементов в дополнение к ним в состав устройства — включают транзисторные каскады, выполняющие операцию инверсии. Только в совокупности с этими инвертирующими каскадами система элементов становится функционально полной. Кроме выполнения операции инверсии транзисторные каскады осуществляют и операцию нормирования уровней выходных сигналов. Дело в том, что при передаче сигналов через диодные цепи амплитуда сигнала падает и при прохождении сигнала через несколько последовательно включенных диодных логических схем становится недопустимо малой. Включение промежуточных транзисторных каскадов позволяет устранить это снижение амплитуды перепадов напряжения. Одновременно транзисторный каскад повышает и нагрузочную способность логической схемы. [14]

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

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

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

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

Система логических элементов содержит:

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

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

Основными типами интегральных элементов являются ТТЛ, потенциальные элементы транзисторной логики с эммитерными связями, МОП-транзисторы

1.3. Функционально полные системы логических функций (базис)

Одни логические функции можно выражать через другие логические функции. Это может быть выполнено методом суперпозиции или перестановки входов.

Базис — это полная система логических функций, с помощью которой можно описать сколь угодно сложный закон функционирования. К базису относится система функций И, ИЛИ, НЕ (базис 1), свойства которого были изучены Булем. Базисами являются также системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (базис 3), состояние из функций Шеффера И — НЕ (Базис 4) и функции Пирса ИЛИ — НЕ (базис 5). Это перечисление показывает, что базисы могут быть избыточными (базис 1) и минимальными (базисы 4,5).

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

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

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

Например, функция f (X₁,X₂, . Xn) = X₁ + X₂ является минимальной формой, и наоборот, функция X₁ + ₁X₂ может быть упрощена, если к этому выражению применить второй распределительный закон, т.е. ₁ + X₁X₂ = (₁ + X₁)(X₁ + X₂) = X₁ + X₂.

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

1.4. Основные законы и эквивалентности для логических операций

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

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

В алгебре логики определено отношение эквивалентности (=), которое удовлетворяет следующим свойствам:

Х = Х — рефлексивность; если X = Y, то Y = X — симметричность; если X = Y, Y = Z, то X = Z — транзитивность. Из отношения эквивалентности следует принцип подстановки: если X = Y, то в любой формуле, содержащей X, вместо X можно подставить Y и будет получена эквивалентная формула.

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

Используя основные положения алгебры логики, нетрудно убедиться в справедливости следующих аксиом. Пусть Х — некоторая логическая переменная X = (0,1). Тогда:

1. X = , что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной.

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

3. Из таблицы истинности для логического сложения (+,), логического умножения (∙,) и логического отрицания () можно получить следующие аксиомы: