1.3. Функционально полные системы логических функций (базис)
Одни логические функции можно выражать через другие логические функции. Это может быть выполнено методом суперпозиции или перестановки входов.
Базис — это полная система логических функций, с помощью которой можно описать сколь угодно сложный закон функционирования. К базису относится система функций И, ИЛИ, НЕ (базис 1), свойства которого были изучены Булем. Базисами являются также системы, содержащие функции И, НЕ (базис 2), ИЛИ, НЕ (базис 3), состояние из функций Шеффера И — НЕ (Базис 4) и функции Пирса ИЛИ — НЕ (базис 5). Это перечисление показывает, что базисы могут быть избыточными (базис 1) и минимальными (базисы 4,5).
Базис минимальный, если удаление хотя бы одной функции превращает систему функций алгебры логики в неполную. Проблема простейшего представления логических функций сводится к выбору не только базиса, но и формы наиболее экономного представления этих функций.
Базис И, ИЛИ, НЕ является избыточной системой, так как возможно удаление из него некоторых функций. Например, используя законы де Моргана, можно удалить либо функцию И, заменив ее на функции ИЛИ и НЕ, либо функцию ИЛИ, заменив ее на функции И и НЕ. Если сравнить, в смысле минимальности различные формы представления функций алгебры логики, то очевидно, что нормальные формы экономичнее совершенных нормальных форм. Но с другой стороны, нормальные формы не дают однозначного представления.
Минимальная форма представления функций алгебры логики — форма представления системы функций, которая содержит минимальное количество термов и переменных в термах, т.е. минимальная форма не допускает никаких изменений.
Например, функция f (X1,X2, . Xn) = X1 + X2 является минимальной формой, и наоборот, функция X1 + 1X2 может быть упрощена, если к этому выражению применить второй распределительный закон, т.е.
1 + X1X2 = (
1 + X1)(X1 + X2) = X1 + X2.
Следовательно, упрощение сложных логических выражений может быть осуществлено на основе использования основных законов и аксиом, изложенным выше. При структурном синтезе элементы рассматриваются как идеальные, имеющие бесспорно большую мощность, не искажающие и не задерживающие сигналы, проходящие через них. Однако, реальные элементы такими свойствами не обладают. Поэтому при составлении логических схем приходится использовать не только логические элементы, входящие в функционально полные наборы, но и различные согласующие элементы такие, как делители, формирователи, элементы задержки. Наборы элементов, обладающие функциональной полнотой и дополненные необходимыми согласующими элементами, будем называть функционально полной системой логических элементов или технически полными наборами элементов.
1.4. Основные законы и эквивалентности для логических операций
Основные свойства алгебры логики позволяют осуществлять эквивалентные преобразования логических формул для их упрощения или приведения к требуемому виду, а также для доказательства логических правил и теорем.
Процесс упрощения сводится к последовательному применению тех или иных общих свойств с тем, чтобы уменьшить общее количество вхождений в формулу переменных и символов логических операций. Между тем не всегда очевидно, какое из свойств наиболее целесообразно использовать на каждом шаге, поэтому работа с формулами на интуитивном уровне подобна блужданию в лабиринте. Этому процессу можно придать целенаправленный характер, если воспользоваться основными законами и тождествами алгебры логики.
В алгебре логики определено отношение эквивалентности (=), которое удовлетворяет следующим свойствам:
Х = Х — рефлексивность; если X = Y, то Y = X — симметричность; если X = Y, Y = Z, то X = Z — транзитивность. Из отношения эквивалентности следует принцип подстановки: если X = Y, то в любой формуле, содержащей X, вместо X можно подставить Y и будет получена эквивалентная формула.
Все тождественные преобразования исходных логических функций осуществляются в соответствии с основными законами алгебры логики. Правильность любого из тождеств алгебры логики проверяется непосредственной подстановкой всех возможных значений переменных, входящих в тождества.
Используя основные положения алгебры логики, нетрудно убедиться в справедливости следующих аксиом. Пусть Х — некоторая логическая переменная X = (0,1). Тогда:
1. X = , что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной.
2
правила идемпотентности или повторения, которые позволяют сокращать длину логических выражений.
3. Из таблицы истинности для логического сложения (+,), логического умножения (∙,) и логического отрицания () можно получить следующие аксиомы:
Большая Энциклопедия Нефти и Газа
Функционально полная система логических элементов — это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. Поскольку любая логическая функция представляет собой комбинацию простейших функций — дизъюнкции, конъюнкции и инверсии, то набор из элементов трех типов, реализующих соответственно функции И, ИЛИ и НЕ, естественно, является функционально полным. Например, функцию ab — — ab можно реализовать с помощью двух ячеек НЕ ( они нужны, чтобы получить инверсии а и Ь), двух ячеек И, необходимых для того, чтобы получить логические произведения аЪ и ab, и ячейки ИЛИ, суммирующей эти произведения. [1]
Функционально полная система логических элементов — это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. Ввиду того, что 1 любая логическая функция представляет собой комбинацию простейших функций — дизъюнкции, конъюнкции и инверсии, набор из элементов ИЛИ, И, НЕ является функционально полным. [3]
Для получения функционально полной системы логических элементов в дополнение к этим элементам в состав устройства включают транзисторные каскады, выполняющие операцию инверсии. Только в совокупности с этими инвертирующими каскадами система элементов становится функционально полной. Кроме выполнения операции инверсии транзисторные каскады выполняют и операцию нормирования уровней выходных сигналов. Дело в том, что при передаче сигналов через диодные цепи амплитуда сигнала падает и при прохождении сигнала через несколько последовательно включенных диодных логических схем становится недопустимо малой. Включение промежуточных транзисторных каскадов позволяет устранить это снижение амплитуды перепадов напряжения. Одновременно транзисторный каскад повышает и нагрузочную способность логической схемы. [4]
При построении функционально полных систем логических элементов мы будем связывать с этими элементами понятия, относящиеся к реализуемым этими элементами булевым функциям. Например, нелинейными логическими элементами будем называть логические элементы, реализующие нелинейные булевы функции. [5]
Построенная таблица позволяет находить также всевозможные другие функционально полные системы логических элементов . Признаком функциональной полноты системы элементов является, очевидно, наличие плюса в каждом столбце таблицы хотя бы для одного из составляющих систему элементов. [6]
Система элементов, обладающая таким свойством, называется функционально полной системой логических элементов . [8]
Анализ и синтез электронных узлов ЭВМ и ВС на основе выбранного базиса функционально полной системы логических элементов . Исходными данными для этого этапа служат характеристики устройств ЭВМ и ВС, определенные во время синтеза логической структуры. [9]
Анализ и синтез электронных узлов и операционных блоков ЦВМ и ВС на основе выбранного базиса функционально полной системы логических элементов . Исходными данными для этого этапа разработки служат характеристики устройств ЦВМ и ВС, определенные во время синтеза их логических структур, а также информация о доступной электронно-технологической базе их производства. [10]
Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-нибудь функционально полную систему логических элементов ( элементарных автоматов без памяти), является структурно полной системой. Существует общий конструктивный прием ( канонический метод структурного синтеза) позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных конечных автоматов к задаче структурного синтеза комбинационных схем. [11]
Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-нибудь функционально полную систему логических элементов , является структурно полной системой. [12]
Так как любая сложная логическая функция может быть выражена с помощью логических — функций ( И, ИЛИ, НЕ), то система-функций ( И, ИЛИ, НЕ) называется функционально полной системой логических элементов . Количество типов вспомогательных элементов выбирается с учетом особенностей логических элементов, используемых в ЭЦВМ. Например, в управляющих ЭЦВМ в систему элементов входит некоторое число аналоговых элементов. Это связано с передачей и обработкой информации представленной в непрерывной форме. [13]
Схемы диодной логики строят на полупроводниковых диодах, обычно в комбинации с резисторами. Для получения функционально полной системы логических элементов в дополнение к ним в состав устройства — включают транзисторные каскады, выполняющие операцию инверсии. Только в совокупности с этими инвертирующими каскадами система элементов становится функционально полной. Кроме выполнения операции инверсии транзисторные каскады осуществляют и операцию нормирования уровней выходных сигналов. Дело в том, что при передаче сигналов через диодные цепи амплитуда сигнала падает и при прохождении сигнала через несколько последовательно включенных диодных логических схем становится недопустимо малой. Включение промежуточных транзисторных каскадов позволяет устранить это снижение амплитуды перепадов напряжения. Одновременно транзисторный каскад повышает и нагрузочную способность логической схемы. [14]
Функционально полная система логических элементов
Функционально полная система логических элементов — это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. Поскольку любая логическая функция представляет собой комбинацию простейших функций — дизъюнкции, конъюнкции и инверсии, то набор из элементов трех типов, реализующих соответственно функции И, ИЛИ и НЕ, естественно, является функционально полным.
В ряде случаев в качестве типовых используются более сложные элементы, реализующие логические связи И-НЕ, ИЛИ-НЕ, ИЛИ — ИЛИ и др., позволяющие строить различные комбинационные схемы для выполнения сложных функций алгебры логики.
Что такое функционально полная система логических элементов
Алгебра логики при анализе и синтезе логических схем
Анализ и синтез цифровых и логических цепей производится на основе математического аппарата алгебры логики (или Булевой алгебры). Логические переменные (т.е. входные и выходные сигналы логических схем) могут принимать два значения: 0 и 1. Принято говорить: нулевой логический уровень и единичный логический уровень (или: низкий логический уровень и высокий логический уровень).
Над логическими переменными могут производиться три основных действия: логическое отрицание (функция «НЕ»), логическое сложение (функция «ИЛИ»), логическое умножение (функция «И»). Все остальные более сложные логические функции могут быть реализованы как комбинация трех основных функций.
Таблица 2.2 — Основные законы алгебры логии
Законы алгебры логики
(правило де Моргана)
Приведем еще один вид записи Закона отрицания (правила де Моргана):
Закон отрицания справедлив для любого числа переменных:
________ _ _ _ _
a b c . z = a + b + c + . + z
Функционально полная система логических элементов
Функционально полная система логических элементов — это такой набор логических элементов, используя который можно реализовать любую (сколь угодно сложную) логическую функцию.
Поскольку любая логическая функция есть комбинация основных простейших функций («НЕ», «ИЛИ», «И»), то набор логических элементов, реализующих эти функции, является функционально полным.
Обозначение этих логических элементов на функциональных схемах приведено на рис. 2.7. Входы элементов располагаются — слева, а выходы — справа. Кружочек возле вывода элемента обозначает операцию отрицания (инверсию).
Рис. 2.7 — Обозначение логических элементов
Например, логическую функцию:
можно реализовать с помощью двух ячеек «НЕ» (они нужны для того, чтобы получить инверсии входных переменных), двух логических схем «И» (схем коньюнкции) и схемы «ИЛИ» (рис. 2.8)
Рис. 2.8 — Реализация логической функции
Функционально полные системы могут состоять и из набора элементов, реализующих функции, отличные от простейших. В частности, функционально полные системы могут состоять из элементов только одного типа, например, реализующих функцию «И-НЕ» либо функцию «ИЛИ-НЕ».
Функция «И-НЕ» (штрих Шеффера) означает следующее преобразование:
может составить функционально полную систему.
Операция инвертирование («НЕ») реализуется при подаче входного сигнала на один из входов элемента Шеффера, а остальные входы могут быть постоянно соединены с высоким логическим уровнем (или объединены все вместе с входным сигналом). Функция «И» реализуется последовательным соединением элемента Шеффера («И-НЕ») и инвертора («НЕ»). Операция «ИЛИ» реализуется в соответствии с правилом де Моргана (см. рис. 2.10).
Правило де Моргана (последняя строка таблицы 2.2) может быть проиллюстрировано элементами логических схем (см. рис. 2.9).
Рис. 2.9 — Правило де Моргана
Альтернативная запись правила де Моргана (2.8) поясняется на рис. 2.10.
Рис. 2.10 — Вариант реализации правила де Моргана
Логическая функция (2.9) также может быть реализована только на элементах Шеффера «И-НЕ» (см. рис. 2.11)
Рис 2.11 — Реализация логической функции на элементах Шеффера
Функция «ИЛИ-НЕ» (стрелка Пирса) тоже может составить функционально полную систему.
Для получения инверсии одной переменной достаточно подать сигнал этой переменной на один из входов, а остальные входы соединить с логическим нулем. Функция «ИЛИ» может быть получена инвертированием выходного сигнала элемента Пирса. Операция «И» реализуется в соответствии с правилом де Моргана (см. рис 2.10).
Возможность реализации простейших логических функций свидетельствует о функциональной полноте логических элементов Шеффера или Пирса.