Cтраница 2
Аналогично представляются переключательные функции в СКНФ, где вместо операции дизъюнкции используется операция, конъюнкции, а вместо конституенты единицы вводится конститу-ента нуля. [16]
Импликантная таблица функции / может быть легко найдена с помощью теоремы 2.3: всякая импликанта, в обозначающем множестве которой содержится номер какой-либо конституенты единицы, обращается в единицу на наборе, соответствующем этой конституенте. [17]
Продолжая подобным образом, мы получим на выходах ( п - 1) - го каскада, построенного из 2я двухвходовых совпадений, все конституенты единицы от п переменных. [18]
Понятие включение в смысле алгебры релейных цепей означает, что если / - некоторая функция от п переменных, то функция ф содержит все конституенты единицы функции / и плюс еще какие-то конституенты единицы от тех же переменных. Другими словами, для всех комбинаций переменных, когда функция / равна единице, для этих комбинации переменных функция ф равна единице и существуют еще какие-то комбинации переменных, для которых функция ф равна единице, а функция / равна нулю. [19]
Понятие включение в смысле алгебры релейных цепей означает, что если / - некоторая функция от п переменных, то функция ф содержит все конституенты единицы функции / и плюс еще какие-то конституенты единицы от тех же переменных. Другими словами, для всех комбинаций переменных, когда функция / равна единице, для этих комбинации переменных функция ф равна единице и существуют еще какие-то комбинации переменных, для которых функция ф равна единице, а функция / равна нулю. [20]
Два элементарных произведения р и q тогда и только тогда склеиваются между собой, когда соответствующие им наборы, разностей одинаковы, а наименьшие номера типе обозначающих их множествах Р и Q являются номерами склеивающихся между собой конституент единицы. В результате склеивания получается элементарное произведение г, обозначаемое объединением множеств Р и Q. Набор разностей элементарного произведения г получается из набора разностей любого из произведений р или q добавлением к нему модуля разности номеров тип. [21]
Диаграммы Вейча булевой функции четырех переменных. [22] |
Минимизация булевых функций с использованием диаграмм Вейча основывается на отыскании склеивающихся конституент единицы. Для диаграммы Вейча склеивающиеся конституенты единицы располагаются в соседних, вертикально или горизонтально расположенных клетках. Для диаграммы трех переменных ( рис. 3.3, а) соседними клетками являются также клетки левого и правого столбцов для одноименных строк. [23]
Для всех ребер вершины на концах представляют собой комбинации значений переменных, которые отличаются значением только одной переменной. Поэтому если сложить конституенты единицы соседних вершин, то всегда будет исключаться одна переменная и полученное выражение будет функцией ребра, соединяющего эти, вершины. [24]
Другой, наиболее удобной формой записи условия работы дискретного автомата является запись в виде алгебраической формулы. Для этого вводят понятие конституента единицы. [25]
Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк - простые им-пликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. [26]
Полным дешифратором I рола называется логическая схема, имею-щая п входов и 2 выходов, такая, что на каждом наборе аргументов возбуждается один и только один выход дешифратора. Каждая выходная функция дешифратора представляет собой конституенту единицы и может быть реализована n - входовым логическим элементом И - НЕ типа ДТЛ или ТТЛ. [27]
Диаграммы Вейча булевой функции трех переменных. [28] |
Выбирается такая совокупность оставшихся простых импликант после выделения существенных импликант, которая обеспечивает покрытие всех оставшихся столбцов таблицы с минимальной ценой. При большом числе переменных для оставшихся простых импликант и конституент единицы строится новая импликантная таблица. [29]
Покажем, что выражения / и g равны между собой. Действительно, ни при каком наборе значений переменных две различные конституенты единицы не могут одновременно обратиться в единицу, поскольку i-я кон-ституента единицы обращается в единицу лишь на г-м наборе. Следовательно, при определении значений функций / и g нам придется определять значение дизъюнкции ( или соответственно суммы) членов, из которых только один может равняться единице, остальные же обязательно равны нулю. [30]