Логические сети
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
минимальной ДНФ, получаем формулу эквивалентную формуле (1) и соответствующую схеме, состоящей из семи контактов (рисунок 4а).
Рисунок 4
Отметим, что схема, изображенная на рисунке 4а, допускает упрощение, соответствующее формуле которое приведено на рисунке 4б и является минимальной схемой. Сложность минимальной схемы равна 6: .
.2 Схемы из функциональных элементов
Ориентированная бесконтурная сеть, в которой полюса делятся на входные (входы) и выходные (выходы), называется схемой из функциональных элементов. Входные полюса помечаются символами переменных, а каждая вершина, отличная от входного полюса, некоторым функциональным символом. При этом должны выполняться следующие условия:
)если а входной полюс, то полустепень захода вершины а равна нулю: ;
)если вершина а не является полюсом и помечена n-местным функциональным символом то и дуги, входящие в а, перенумерованы от 1 до n.
Функциональным элементом называется всякий подмультиграф схемы, состоящий из невходного полюса а, помеченного соответствующим символом , и вершины, из которых исходят дуги в вершину а.
Пример 1. На рисунке 5а представлена схема из функциональных элементов. Здесь входные символы помечены символами переменных - одноместный функциональный символ, соответствующий операции отрицания; & - двухместный символ, соответствующий операции конъюнкции. - некоторый двухместный символ, - некоторые трехместные символы. Вершины, помеченные символами , являются выходными полюсами. Им соответствуют термы:
На рисунке 5б изображен функциональный элемент, определяемый вершиной, помеченной символом Ему соответствует устройство, показанное на рисунке 5в.
Рисунок 5
В примере 1 продемонстрировано, что каждый вывод схемы порождает некоторый терм.
Говорят, что функция реализуется схемой, если существует такой выход а схемы , что функция соответствующая терму выхода а, эквивалента функции .
Схемы из функциональных элементов с одним выходом, у которых входные полюса помечены символами а вершины, отличные от входных полюсов, - символами называются -функциональными схемами. Сложностью схемы из функциональных элементов называется число ее вершин, отличных от входных полюсов, -функциональная схема , реализующая функцию называется минимальной, если всякая другая -функциональная схема, реализующая имеет сложность, не меньшую, чем сложность схемы . Сложность минимальной схемы, реализующей функцию называется сложностью функции в классе схем из функциональных элементов и обозначается через
Пример 2. Сложность функции совпадает со сложностью -функциональной схемы, изображенной на рисунке 6, и равна 8: .
Рисунок 6
.3 Мультиплексоры
Мультиплексором каналов называется схема с входами и одним выходом в которой при выход принимает значение где:
На рисунке 7 показан мультиплексор.
Рисунок 7
Пример 3. Если то
С помощью мультиплексора , придавая переменным постоянные значения, можно реализовать любую булеву функцию
.4 Программируемые логические матрицы
Рассмотрим схему, состоящую из входов , и выходов (рисунок 8), в которой значения выходов определяются матрицей соединений по следующим правилам:
Рисунок 8
Таким образом, где а остальные равны 0. Полученная схема называется решеткой с входами и выходами элементов &, которая определяется матрицей соединений .
Программируемой логической матрицей (ПЛМ) называется изображенная на рисунке 9 схема, получающаяся соединением решетки А с 2n входами и k выходами, определяемой матрицей соединений , и решетки В с k входами и m выходами, определяемой матрицей соединений .
Опишем преобразования, которые происходят при прохождении через ПЛМ значений переменных Поскольку к каждому входу присоединен инвертор , на 2п входов решетки А подаются значения переменных После прохождения решетки A h-й выход принимает значение функции а последующей операции инвертирования соответствует функция:
Полученные k значений подаются на входы решетки В, после прохождения которой на выходе j образуется значение функции
В заключение после инвертирования по законам де Моргана на выходе j получаем значение функции:
Функции соответствует дизъюнкция конъюнктов (определяемых формулами
) таких, что
Рисунок 9
Таким образом, при соответствующем выборе матриц и можно одновременно реализовать m произвольных ДНФ, содержащих не более k различных конъюнктов переменных от
2. Практическая часть
I.Исследовать систему булевых функций на полноту. Является ли она базисом. .
k0k1kмkлkс+--+-+++---+++-
XY0000011110111101
Монотонность:
a..
Линейность:
. - по определению.
Самодвойственность:.
.
.
Система функций является полной. Система функций называется базисом, если она полная, а удаление любой функции из этой системы делает её неполной. Если удалить одну из имеющихся функций, то система функций станет неполной. Таким образом, данная система функций является базисом.
II.С помощью эквивалентных преобразований привести формулу к ДНФ, КНФ; привести к СДНФ, СКНФ с помощью аналитического и табличного способа. Провери?/p>