Cтраница 4
При работе ППЗУ в качестве комбинационного цифрового устройства сигналы аргументов подаются на адресные входы; сигналы логических функций снимаются с выходов. При программировании ППЗУ требуемый функционал необходимо представить в виде таблицы истинности, соответствующей совершенной дизъюнктивной нормальной форме. Функционал, заданный в другой форме, следует предварительно преобразовать в СДНФ, для чего удобно использовать ЭВМ, сопряженную с программатором ППЗУ. [46]
Аналогичным образом определяется совершенная конъюнктивная нормальная форма. Это определение проводится в терминах, двойственных тем, которые мы употребляли при определении совершенной дизъюнктивной нормальной формы. [47]
Можно доказать, что каждая не тождественно истинная формула имеет единственную, с точностью до порядка расположения множителей и слагаемых, совершенную конъюнктивную нормальную форму. Правила приведения произвольной формулы к совершенной конъюнктивной нормальной форме аналогичны тем, которые мы описали для нахождения совершенной дизъюнктивной нормальной формы, и выражаются в двойственных терминах. [48]
Если функция не представлена в форме суммы произве: дений, начинают с соответствующего преобразования, чтобы привести ее к этому виду. Если некоторые члены содержат меньше переменных, чем их содержит функция, приводят, кроме того, выражение к совершенной дизъюнктивной нормальной форме. [49]
Совершенные нормальные формы играют большую роль в математической логике. При их помощи решаются многие задачи как в самой математической логике, так и при применении ее для синтеза и анализа релейно-контактных и электронных схем. Часто совершенная дизъюнктивная нормальная форма записывается сокращенно - СДНФ, а совершенная конъюнктивная нормальная форма - СКНФ. [50]
Пусть задана дизъюнктивная нормальная форма аЬ ас Ъс. Требуется найти совершенную дизъюнктивную нормальную форму. [51]
Эти выражения называются дизъюнктивными нормальными формами. Возможность приведения к совершенной дизъюнктивной нормальной форме лежит в основе алгоритма, устанавливающего равенство или неравенство двух заданных формул. [52]
Найденное выражение достаточно громоздко. Сейчас, однако, мы не будем заниматься его упрощением, а укажем лишь один более простой метод задания совершенных дизъюнктивных нормальных форм, часто применяющийся на практике. Суть этого метода заключается в том, что вместо явного выписывания конституент единицы, составляющих дизъюнктивную нормальную форму, выписываются лишь номера этих конституент, то есть номера тех наборов, на которых данные консти-туенты обращаются в единицу. При этом, разумеется, необходимо фиксировать некоторый определенный порядок следования переменных, от которых зависят функции возбуждения. [53]