Cтраница 3
Конституента единицы - это такая функция, которая принимает значение единицы только для одной комбинации значений переменных, а для остальных комбинаций значений переменных она равна нулю. Из определения следует, что для одной переменной имеются две конституенты единицы. [31]
Гиперкуб из 2 вершин, где каждая вершина является соседней с i вершинами, называют подкубом i - ro порядка л-мерного гиперкуба. Основным свойством подкуба 1-го порядка является то, что сумма 2 конституент единицы, соответствующая вершинам, позволяет исключить t переменных, а функция гиперкуба зависит от остальных ( п - i) переменных. [32]
Другой полной системой импликант функции / является, очевидно, система всех конституент единицы, представляющих собою им-пликанты данной функции. Эти две системы различим для функций, таблицы значений которых насчитывают более одной единицы. [33]
Хорошо известным и широко распространенным ПЛУ является программируемое ПЗУ ( ППЗУ), применяемое для реализации БФ, заданных таблицей истинности или СДНФ. Первая из них реализует ( хранит соответствующие слова) все 2 г конституент единицы БФ, а вторая - их дизъюнкции. [34]
Выделяются все существенные ( или обязательные) импликанты. Она обязательно входит в минимальное покрытие, так как не используя ее, невозможно покрыть все конституенты единицы. [35]
Предположим, что переменными, от которых зависит функция /, будут переменные х, у, г, и, так что первая импликанта /, ( конституента с номером 15) будет иметь вид: /, хуги. Для нахождения в явном виде остальных импликант воспользуемся следующим очевидным приемом: 1) выписываем для каждой простбй импликанты Р какую-нибудь конституенту единицы К, номер которой входит в обозначающее множество импликанты Р; 2) по разностям, соответствующим импликанте Р, определяем переменные, которые отсутствуют в представляющем ее элементарном произведении, и вычеркиваем эти переменные из конституенты К. [36]
Матричный дешифратор представляет собою частный случай, описанный в предыдущем параграфе канонической двухступенчатой схемы. Вследствие того, что каждая из выходных функций имеет в этом случае единственную простую импликанту, вторая ступень в схеме отсутствует, а сама схема представляет собою простое объединение не связанных между собою схем, каждая из которых имеет в качестве своей выходной функции какую-либо конституенту единицы. [37]
Переключательная функция п аргументов, которая принимает значение, равное единице, только на одном наборе аргументов, называется конституентой единицы. Конституенты единицы определяются логическим произведением всех аргументов, причем при равенстве одного из аргументов нулю, последний вписывается в произведение с инверсией. [38]
Отметим один частный случай, при котором система всех простых импликант булевой функции является приведенной системой. Импликанта р накрывает конституенту единицы Kpxlxt... Таким образом, система всех простых импликант оказывается приведенной системой. [39]
Для функций, содержащих большое число переменных, преобразования могут быть продолжены, если в результате получатся произведения, содержащие одинаковые переменные и равное число букв. СДНФ не меняет саму функцию. Если член, записанный в графе импликант, поглощает конституенту единицы, то на пересечении строки и соответствующего столбца ставится звездочка. Такая таблица называется импликантной матрицей. [40]
С этой целью составляем следующую таблицу. В первую строку записываем переменные, а под ними их веса. Затем в следующие строки записываем двоичные изображения первых элементов ( конституенты единицы) неотмеченных объединенных членов. В двоичном изображении этих элементов вычеркиваем те цифры, которые соответствуют исключенным переменным. [41]
Предположим теперь, что зафиксирован какой-либо набор логических элементов. Задача построения из такого набора комбинационной схемы, реализующей некоторую переключательную ф-цию, сводится прежде всего к ее представлению в виде выражения алгебры логики. При составлении выражений, описывающих произвольную переключательную ф-цию, важное значение имеют две простейшие переключательные ф-ции: конституенты единицы и нуля. [42]
Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк - простые им-пликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. [43]
Как непосредственно вытекает из закона раскрытия скобок, в каждое элементарное произведение, составляющее дизъюнктивное представление, обязательно входит символ простой импликанты, накрывающей конституенту единицы, соответствующую любому наперед заданному столбцу импликантной таблицы. [44]