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

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

Дизъюнктивная нормальная форма (ДНФ). Пусть имеется множество, состоящее из n элементов А₁..., А_n. Произведение вида доставленное из элементов A_i или их отрицаний A_j и содержащее n сомножителей, называется элементарным произведением. Из n элементов можно составить 2ⁿ различных элементарных произведений. Изображающее число каждого элементарного произведения имеет только одну единицу в одном из 2ⁿ разрядов. Например, выпишем для трех высказываний А, В, С все возможные элементарные произведения и их изображающие числа по отношению к b [А, В, С]:

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

Конъюнктивная нормальная форма (КНФ). Элементарными суммами для лnэлементов А₁..., А_n называются суммы вида составленные из элементов А_i или их отрицаний `A_j и содержание n слагаемых. Из n элементов можно составить 2ⁿ элементарных сумм. Изображающие числа элементарных сумм содержат только один 0 в одном из 2 ⁿ разрядов. Например, для трех высказываний А, В, С имеем

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

Представление в форме суммы первых имнликант. Рассмотрим булеву функцию F(A, В, С,...). Функция f(A, В, С,...) называется импликантой функции F(A, В, С,...), если f(А, В, С,...)®F(A, В, С,...). Изображающее число #f импликанты функции F имеет нули в тех разрядах, в каких имеет нули изображающее число #F наличие же единицы в разряде изображающего числа #f влечет за собой наличие единицы в аналогичном разряде изображающего числа #F.

Если P₁ и Р₂ представляют собой какие-либо произведения из элементов А, В, С,... или из их отрицаний и P₁®P₂, то Р₂ получается из P₁ отбрасыванием некоторых сомножителей, например и т. д.

Функция f(A, В, С,...) называется первой импликантой функции F(A, В, С,...), если f®F, и не существует такой функции f'(A, В, С,...), что f’®F и f®f', например

Элементарные произведения отвечающие единицам в разрядах 1, 2, 3 и 5 #F, по определению,— импликанты функции F. Так как то, во-первых, — импликанты функции F, во-вторых, так как ни один из элементов А, В, не является импликантой функции F, то, следовательно, — первые импликанты функции F, и, в-третьих, импликанта А×`С — несущественная. Запишем столбцы базиса b [А, В, С], соответствующие единицам в изображающем числе #F в виде двоичных чисел и отметим, как и в базисе b [А, В, С], разряды этих чисел буквами А, В, С в порядке справа налево.

Объединению импликант отвечающих столбцам 1 и 3 в базисе b [А, В, С], можно поставить в соответствие аналогичную операцию на числах 001 и 011, отличающихся только содержимым второго разряда, причем результат объединения, т.е. А×`С, выражается как 0´1, где символ «´» во втором разряде указывает на то, что элемент В отсутствует в возникающей импликанте. Аналогично можно объединить (повернутые) столбцы 001 и 101, а также столбцы 010 и 011, в результате получим числа ´ 01 и 01 ´, отвечающие импликантам А В и ВС, соответственно. Число 0´1 выражает тот факт, что среди номеров единичных разрядов изображающего числа #.F=0111 0100 имеются числа 1 и 3 и, кроме того, что изображающее число #А • С=0101 0000 имеет единицы в разрядах 1 и 3. Аналогично, число х01 показывает, что в ФР есть два единичных разряда 1 и 5 и что #А`×B=0100 0100 имеет единицы в разрядах 1 и 5.

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