Конституента - единица
Cтраница 3
Графом предиката f называется подграф графа Коп ( 2, 3), порожденный множеством вершин, соответствующих конституентам единицы предиката. [31]
Переключательная функция представлена в дизъюнктивной совершенной нормальной форме ( ДСНФ), если все ее составляющие элементарные конъюкции являются конституентами единицы для данного множества переключательных аргументов. [32]
Дизъюнктивная ( соответственно конъюнктивная) нормальная форма называется совершенной, если все составляющие ее элементарные произведения ( соответственно элементарные дизъюнкции) являются конституентами единицы ( соответственно конституентами нуля) для одного и того же множества М переменных. [33]
Независимо от того, описывается ли заданная функция алгебраически в форме суммы конституент единицы или набором их номеров ( десятичных эквивалентов), каждая конституента единицы должна быть представлена своим двоичным изображением. [34]
Диаграмма Вейча представляет собой несколько необычную таблицу булевой функции. Каждая клетка такой таблицы соответствует определенной конституенте единицы. [35]
Каждый выход дешифратора принимает значение, равное единице ( возбуждение), только при одном определенном наборе входных переменных xi-xz. Переключательные функции каждого выхода выражаются конституентой единицы. Так, если на вход дешифратора подан код xlQ, х20, х30, то на выходе сигнал появится на шине yu-xixzxz - Если длина дешифрируемого двоичного слова больше возможного числа входов элементов И, входящих в комплекс, используют многоступенчатое ( каскадное) построение дешифратора. На рис. 6.13 показан двухступенчатый дешифратор, у которого каждый выход образован каскадным включением двух двухвходовых элементов И. [36]
Нетрудно убедиться в том, что для любой конституенты единицы К существует один и только один набор а значений переменных, входящих в К, на котором эта конституента обращается в единицу. Построенный таким образом набор а и конституента единицы К, которая на этом наборе об ращается в единицу, называются соответствующими друг другу. [37]
С ( X), равная единице только на одном наборе значений аргументов. Из этого определения следует, что число различных конституент единицы равно числу наборов. Удобно каждую конститу-енту пронумеровать, присвоив ей номер набора, на котором эта конституента равна единице. Набор Ха и конституента Ki при а / называются соответствующими друг другу. [38]
 |
Диаграмма Вейча для функций двух, трех и четырех переменных.| Примеры минимизации функций трех переменных. [39] |
Каждая клетка диаграммы Вейча соответствует определенному набору переменных и в нее вписывается значение ф-ции ( 0 или 1), которое она принимает на данном наборе. В то же время каждой клетке диаграммы соответствует конституента единицы с номером, совпадающим с номером набора. Специальная разметка столбцов и строк диаграммы и, следовательно, нумерация клеток производится таким образом, что конституенты, соответствующие двум соседним клеткам, обязательно склеиваются по одной из переменных. Важно отметить, что в диаграмме для ф-ции от трех переменных соседними следует считать также крайние клетки каждой строки, а в диаграмме для ф-ции от четырех переменных соседними являются крайние клетки каждой строки и столбца. [40]
Каждому контуру соответствует логическое произведение, входящее в ДНФ. Изолированной единице ( контуру, состоящему из одной клетки) соответствует произведение п переменных, а именно конституента единицы, номер которой совпадает с номером клетки. Контуру из двух клеток соответствует произведение п - 1 переменных, причем исключается та переменная, которая входит в данный контур как с инверсией, так и без нее. Если контур состоит из четырех единиц, то в ДНФ ему будет соответствовать произведение п - 2 переменных. В общем случае наличие единиц в 2 соседних клетках позволяет исключить из соответствующего произведения т переменных. Следовательно, при образовании контуров надо стремиться к тому, чтобы количество контуров было возможно меньшим. При этом одни и те же клетки, заполненные единицами, могут входить в несколько контуров. [41]
Переключательная функция п аргументов, которая принимает значение, равное единице, только на одном наборе аргументов, называется конституентой единицы. Конституенты единицы определяются логическим произведением всех аргументов, причем при равенстве одного из аргументов нулю, последний вписывается в произведение с инверсией. [42]
Представляет интерес использование мультиплексора для реализации произвольной булевой функции. Для реализации СДНФ исходной булевой функции п переменных на мультиплексоре с 2 информационными входами необходимо на п входов селекции подать входные переменные, на информационные входы, соответствующие входящим в функцию конституентам единицы, - 1, а на остальные информационные входы - О. На выходе мультиплексора при этом окажется сформирована требуемая функция. [43]
Найденное выражение достаточно громоздко. Сейчас, однако, мы не будем заниматься его упрощением, а укажем лишь один более простой метод задания совершенных дизъюнктивных нормальных форм, часто применяющийся на практике. Суть этого метода заключается в том, что вместо явного выписывания конституент единицы, составляющих дизъюнктивную нормальную форму, выписываются лишь номера этих конституент, то есть номера тех наборов, на которых данные консти-туенты обращаются в единицу. При этом, разумеется, необходимо фиксировать некоторый определенный порядок следования переменных, от которых зависят функции возбуждения. [44]
Страницы: 1 2 3