§ 5.3. Восстановление булевой функции по изображающему числу

Рассмотрим методы, позволяющие переходить от задания булевой функции в виде изображающего числа к явному выражению ее через элементы.

Дизъюнктивная нормальная форма (ДНФ). Пусть имеется множество, состоящее из элементов Произведение вида составленное из элементов или их отрицаний и содержащее сомножителей, называется элементарным произведением. Из элементов можно составить различных элементарных произведений. Изображающее число каждого элементарного произведения имеет только одну единицу в одном из разрядов. Выпишем, например, для трех высказываний все возможные элементарные произведения и их изображающие числа по отношению к

Совершенная дизъюнктивная нормальная форма (СДНФ) булевой функции — сумма элементарных произведений. Чтобы по данному изображающему числу восстановить булеву функцию в СДНФ, нужно суммировать элементарные произведения, изображающие числа которых имеют единицы в тех же разрядах, что и изображающее число булевой функции. Например, имеет единипы в разрядах 0, 3, 5, 6, поэтому

Конъюнктивная нормальная форма (КНФ). Элементарными суммами для элементов называются суммы вида составленные из элементов или отрицаний и содержание слагаемых. Из элементов можно составить элементарных сумм. Изображающие числа элементарных сумм содержат только один нуль в одном из разрядов. Например, для трех высказываний имеем

КНФ булевой функции представляет собой произведение элементарных сумм. Для того чтобы написать булеву функцию, соответствующую данному изображающему числу, в КНФ необходимо перемножить элементарные суммы, изображающие числа которых имеют те же нули, что и изображающее число булевой функции. Например, число имеет нули в разрядах поэтому

Представление в форме суммы первых импликант. Рассмотрим какую-либо булеву функцию Функция называется импликантой функции если Изображающее число импликанты функции имеет нули в тех разрядах, в каких имеет нули наличие же единицы в разряде влечет за собой наличие единицы в аналогичном разряде

Если представляют собой какие-либо произведения из элементов «ли из их отрицаний и то получается отбрасыванием некоторых сомножителей, например и т. д.

Функция называется первой импликантой функции если и не существует такой функции что и например

Элементарные произведения отвечающие единицам в разрядах по определению, — импликанты функции Так как

то, во-первых, импликанты функции во-вторых, поскольку ни один из элементов, не является импликантой то, следовательно, первые импликанты и, в-третьих, импликанта несущественная. Запишем столбцы базиса соответствующие единицам в в виде двоичных чисел и отметим, как и в разряды этих чисел буквами в порядке справа налево.

Объединению имлликант отвечающих столбцам 1 и 3 в базисе можно поставить в соответствие аналогичную операцию на числах отличающихся только содержимым второго разряда, причем результат объединения, т. е. выражается как где символ «X» во втором разряде указывает на то, что элемент В отсутствует в возникающей импликанте. Аналогично можно объединить (повернутые) столбцы 001 и 101, а также столбцы в результате получим числа отвечающие импликантам и соответственно. Заметим, что число выражает тот факт, что среди номеров единичных разрядов имеются числа 1 и 3 и, кроме того, что имеет единицы в разрядах 1 и 3. Аналогично, число показывает, что в есть два единичных разряда 1 и 5 и что имеет единицы в разрядах 1 и 5.

Так как в данном процессе попарно объединяться могут только столбцы, отличающиеся содержимым только одного разряда, то перед началом работы для удобства следует распределить все номера единичных разрядов на группы, объединяя в одну группу числа (номера столбцов), которые, будучи записаны в двоичном коде, имеют одинаковое число единиц, например, если то числа 1, 2 образуют одну группу, 3, 5 — другую.

Пример. Пусть задано Разобьем числа, представляющие номера единнчных разрядов по группам следующим образом:

Припишем справа столбец степенных разрядов, отмеченных элементами для представления в двоичном коде номера столбца базиса (или, что то же, повернутого столбца), соответствующего той исходной импликанте, которую будем пытаться упростить. Пусть 001 — представление в двоичном коде, проверяемой импликанты . Записываем в столбец степенных разрядов число 001 и отмечаем знаком против 1, что это число соответствует импликанте, изображающее число которой покрывает единицу в первом разряде

0000). Теперь проверим, имеются ли среди номеров единичных разрядов оба числа Так как имеется, а было исходным, то в столбце степенных разрядов записываем вместо 001, а против 3 ставим знак т. е. изображающее число импликанты, представленной как покрывает единицу в третьем разряде :

Если бы среди номеров единичных разрядов имелись все четыре числа XXI, т. е. то от числа можно было бы перейти к числу XXI. Аналогично, если бы в исходном наборе чисел (1, 2, 3, 5) имелись четыре числа т. е. то можно бы было перейти от Но так как числа 7 и 0 отсутствуют, то переходим к следующему номеру единичного разряда т. е. к и в соответствии с этим против 2 ставим а в столбец степенных разрядов записываем число

Проверим, имеются ли среди номеров единичных разрядов два числа т. е. Число 2 — исходное число, а 3 имеется в соседней группе номеров поэтому переходим от а против 3 ставим

Дальнейшее упрощение невозможно, так как числа отсутствуют. Неприкрытым остается только пятый разряд Запишем в столбец степенных разрядов число 101 и отметим знаком число 5. Поскольку число имеется в соседней группе, то переходим от 101 к и ставим знаку против 1:

Так как среди номеров единичных разрядов отсутствуют числа то нельзя перейти от ни к XXI, ни к . Импликанты и покрывают все единичные разряды Следовательнопроцесс построения первых импликант по закончен и

Рассмотрим еще один пример [14]. Пусть относительно задано

Разобьем номера единичных разрядов на группы по количеству единиц в соответствующих колонках базиса и разместим их в рабочей таблице:

Возьмем первую колонку базиса, отметим это знаком и запишем в столбце степенных разрядов число 0001. Так как среди чисел во второй группе имеем то 0001 заменим на , а против 3 поставим знак . Среди чисел второй группы имеется число отличающееся единицей в степенном разряде от первоначального числа а среди чисел третьей группы есть число т. е. среди номеров единичных разрядов есть все числа . Поэтому заменим на и поставим против чисел 5 и 7 знак

Далее убедимся в. том, что в соответствующих группах рабочей таблицы имеются числа и, следовательно, все чисел содержатся среди номеров единичных разрядов . В соответствии с этим заменим число на XXXI и отметим числа 9, 11, 13, 15 знаком Дальнейшее упрощение проверяемой импликанты невозможно, так как число отсутствует в исходном наборе чисел.

Число XXXI показывает, что одной из первых импликант функции Н является А и, как можно заметить из рабочей таблицы, не покрывает только -й единичные разряды

Продолжая вычисления, возьмем в качестве второй исходной импликанты и в соответствии с этим поставим против числа 4 в первой группе знак

Поскольку число отсутствует в исходном наборе номеров единичных разрядов то степенной разряд 8 числа нельзя изменить; числа также нет и поэтому степенной разряд 4 числа остается без изменения. Однако число содержится во второй группе исходного набора номеров и, следовательно, можно заменить число на и отметить это знаком V против числа 6 во второй группе. Так как числа имеются, то можно дополнительно упростить импликанту и перейти от представления к представлению отметив числа в рабочей таблице знаком Представлению импликанты соответствует булева функция причем имеет единицы в 4, 5, 6 и 7-м разрядах. Теперь неприкрытым остается только разряд Запишем в столбец степенных разрядов число 1110 и отметим число 1.4 знаком Числа имеются в исходном наборе, а числа отсутствуют, следовательно, можно заменить число 1110 на представление соответствующее первой импликанте , и поставить знак V против чисел 6, 7 и 15. Таким образом,