Файл: Горелик, А. Л. Некоторые вопросы построения систем распознавания.pdf

Изображающее число конъюнкции двух элементов определяется как произведение изображающих чисел со­ множителей

причем перемножение выполняется поразрядно по тако­ му правилу:

0-0 = 0, 0 1 = 1-0 = 0, 1-1 = 1,

например, по отношению к Ь[А, В, С]

#(Л -С )=#0101 0101)-(0000 1111) = 0000 0101.

Наконец, изображающее число отрицания Ж получается из изображающего числа А заменой в каждом разряде

0 на 1 и 1 на 0, например,

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

Руководствуясь (5.2) — (5.4), можно найти изобра­ жающее число любой булевой функции. Например, по

1100 1100 1100) - (1111 0000 1111 0000)-(0000 0000 1111 1111) =0001 0001 0001 0001+0000 0000 1100 0000 = 0001

0001 1101 0001 и, следовательно, данная функция истин­ на только при таких комбинациях значений истинности элементов А, В, С, D, которые соответствуют столбцам

базиса с номерами 3, 7, 8, 9, 11 и 15. Укажем дополни­

ней мере в тех разрядах, в которых #2Г содержит еди­ ницы.

Используя изображающие числа, можно вывести лю­ бую из формул (1) — (20) булевой алгебры. Докажем,

112

булевой функции. Изображающее число левой части было вычислено в предыдущем примере: оно равно 0001 0001 1101 0001. Изображающее число правой части отличает­ ся от этого числа только на # Л • С -D= (0101 0101 0101

тельно, изображающие числа левой и правой частей рас­

1111 и убедиться, что в 3—7-м разрядах последнего чис­ ла стоят единицы.

5.4.ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ. ВОССТАНОВЛЕНИЕ БУЛЕВОЙ ФУНКЦИИ ПО ИЗОБРАЖАЮЩЕМУ ЧИСЛУ

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

Представление в совершенной дизъюнктивной нор­ мальной форме. Пусть имеется множество из п элемен­ тов А і> ..., Ап. Произведение вида Аі-Аг-- ■. -Лп- 1 ѵ4и, со­ ставленное из элементов Л* или их отрицаний Aj и со­ держащее п сомножителей, называется элементарным пронзвеОснием. Из п элементов можно составить 2п раз­

личных элементарных произведений. Легко видеть, что изображающее число каждого элементарного произведе­ ния имеет только одну единицу в одном из 2п разрядов. Выпишем, например, для трех высказываний А, В, С все

возможные элементарные произведения и их изобра­ жающие числа по отношению к Ь[А, В, С]:

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

1001 0110 = # ( Л - Л - С + Л - B - C + A - B - C + Ä - B - С).

Представление в конъюнктивной нормальной форме.

Элементарными суммами для_я элементов A lj_...,An на­ зываются суммы вида A i +A z+ ... + A n- i + Ä n, состав­ ленные из элементов А{ или их отрицаний Aj и содержажащие п слагаемых. Из п элементов можно составить 2п элементарных сумм. Изображающие числа элемен­ тарных сумм содержат только один нуль в одном из 2п разрядов. Для трех высказываний А, В, С, например,

имеем

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

Например, число 1001 ОНО имеет нули в 1, 2, 4 и 7-м разрядах, поэтому

1001 0110 = # [ ( H + ß + C) Д Л + Л + + С) • (Л+ ß + C) • ОА + В + С)].

Представление в виде суммы первых импликант. Рас­ смотрим какую-либо булеву функцию F(A, В, С,...). Функция f{A, В, С,...) называется импликантой функ­ ции F(A, В, С,...), если /(Л, В, C , . . . ) ^ F ( A , В, С,... ).

Изображающее число импликанты функции F имеет

нули во всех тех разрядах, в каких имеет нули 4j=ß, на-

114

личие же единицы в разряде ф / влечет наличие единицы в том же самом разряде # / \

Заметим, что если Рі и Р2 представляют собой какиелибо произведения из элементов А, В, С,... или из их отрицаний и Pr+Pz, то Р% получается из Р4 отбрасыва­ нием некоторых сомножителей. Например, А - В - С^~А • С,

А - В - С-+В -С, А- В-+А и т. д.

F= A> B’C + Ä - B - Ü + A - B - C + A - B ' C =

=(А • В • С+А • В - С) + (А • В • С+А • В • С) +

+(Ä-B -С+А- В- С) = А - С + А - В + В-С =

=А - В + В - С ,

то, во-первых, А-С, А-В, В-С все являются импликан­

тами функщш_/7,_во-вторых, поскольку ни один из эле­ ментов А, В, Д С н^ является импликантой F, то, сле­ довательно, А-С, А-В, Д С — первые импликанты F и, в-третьих, импликанта АС несущественная [см. правило (19)]. Запишем столбцы базиса Ь[А, В, С], соответствую­ щие единицам в ф F, в виде двоичных чисел и отметим, как и в Ь[А, В, С] разряды этих чисел буквами А, В, С

в обратном порядке (справа налево):

Объединению импликант А - В - С и А- В- С, отвечающих столбцам 1 и 3 в базисе Ь[АВС], можно поставить в со­

ответствие аналогичную операцию с числами 001 и 011, отличающимися только содержимым 2-го разряда, при­ чем результат последнего объединения, т. е. А • С, выра­

жается как 0x1, где символ X во 2-м разряде указыва­ ет, что элемент В в возникающей импликанте отсутст­

вует.

Аналогично можно объединить повернутые столбцы 001 и 101, а также 010 и 011; в результате получим чис­ ла Х01 и 01 X для импликант А - В и ß • С соответствен­

но. Заметим, что число 0X1 выражает тот факт, что сре­ ди номеров единичных разрядов

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

Поясним на примере способ нахождения таких первых импликант булевой функции по ее изображающему числу, через сумму которых данная функция выражается. Пусть по-прежнему задано изображающее число #А (Т , В, С) =0111 0100. Разобьем числа, представляющие номера единичных разрядов # А, по группам, как

показано в верхней строке таблицы:

116