Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

Глава пятая

П РЕД С ТАВЛЕН И Е Ф УНКЦИЙ БУЛЕВОЙ АЛГЕБРЫ ] НО РМ АЛЬНЫ М И ФОРМАМИ

§ 1. НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

Основной целью настоящего параграфа является установление некоторых специальных форм выражений в булевой алгебре.

В § 2 главы четвертой было указано, что произвольная булева функция может быть задана с помощью формулы. Пусть булева функция / (х 0, x lt х 2, х3) задана, например, в виде формулы:

Используя систему операций (V> Л> —)> приведем данную фор­ мулу к виду:

= Х 1Х 2 + Х 0Х.2 + Х 0Х уХ 2 + х3,

где

11 “ Х \ —> Х 3 — X 1 -{- X q.

Полученное выражение состоит из дизъюнкции элементарных конъюнкций различной длины. Здесь х3 рассматривается как эле­

ментарная конъюнкция (х3Д1).

О п р е д е л е н и е . Логическое произведение любого количества

представляет собой произведение функции (ХхУх0) и независимой переменной х3, а не конъюнкцию независимых переменных, во вто­ рое — дважды входит х г, а в третьем знак инверсии стоит над всем числом.

103

О п р е д е л е н и е . Булева функция задана своей дизъюнктив­ ной нормальной формой (ДНФ), если она состоит из дизъюнкции элементарных конъюнкций.

Одна и та же булева функция может иметь несколько равно­ сильных дизъюнктивных нормальных форм. Представим формулу (5.1) в виде конъюнкции элементарных дизъюнкций, используем закон булевой алгебры и введем для этого обозначения:

[(хх -» х0) ~ х2] V (х3 Л 1) = [ах2 У а х2] V (х3 V 1) =■■

= а х2 V а х2 \/ х3 = (b V х2) (b V а) = (а х2 V х3 V

V *2)(ах2 V х3 V а) = (а х2 V с)(а*2 V ^)= (сV *2)(cV a)-

■(d V x2)(d\J а) = (с V*2) • (с V * Л ) • (d V х2) ■(d V *1 *0) =

= (сv ^)-(сV *оМсV *i)-(dV *2M dV *iMd V x0)=

Полученное выражение является конъюнктивной нормальной формой и состоит из конъюнкции элементарных дизъюнкций.

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

104

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

§2. СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

бу л е в о й ФУНКЦИИ (СДНФ)

Если какая-либо дизъюнкция задана одной из своих дизъюнк­ тивных (конъюнктивных) нормальных форм, то для ее минимиза­ ции с помощью некоторых из описываемых ниже методов необхо­ димо предварительно перейти к совершенной дизъюнктивной (конъюнктивной) нормальной форме.

О п р е д е л е н и е . Если элементарная дизъюнкция (конъюнк­ ция) дизъюнктивной (конъюнктивной) нормальной формы от п аргументов содержит все п аргументов, то форма называется со­ вершенной.

это представление называется разложением функции по (k пере­ менным).

Д о к а з а т е л ь с т в о . В случае, если: х х — ах, х2 ----- о2, . . . ,

в1 °2 °k

xk = ak\ хх -х2 . . . . xk — 1, то во всех остальных случаях конъюнк­ ция равна нулю.

бы в одном из членов конъюнкции хп Ф сг„, то этот член превра­

f (ох, О2, ■• . ) <Т£) Xh+ l , • • • I хп)"

105

В правой части (5.3) в силу равенства х;- = сг;- получаем:

Таким образом, равенство (5.3) справедливо для любых значений Gj, что и требовалось доказать. Из доказанной теоремы следует другая 'теорема.

Теорема 2. Любую функцию алгебры логики можно представить

ввиде формулы через конъюнкции, дизъюнкции и отрицание.

До к а з а т е л ь с т в о . Поскольку х-х = 0 и я + * — '1, теорему достаточно доказать для функции

Поскольку функция f (alt с 2, . . . , оп) равна 1 или 0, то конъюнк­ ции, входящие в дизъюнкцию (5.4), либо будут равны нулю, либо не будут тождественно равны нулю. В силу свойств дизъюнкции члены, равные нулю, можно опустить, тогда

этого необходимо отобрать все наборы аргументов, на которых табличная функция равна единице «1», и для них составить конъюнк-

лично (табл. 5-2).

106

Функция равна 1 на четырех наборах (0, 1, 1), (1, 0, 0), (1, 1, 0), (1,1, 1), поэтому она запишется согласно (5.4):

f (*1 .*8. *з) = * 1 х\ х\ V х\ Х°2 Х °3 V JCl xl Хз V х\ х\ xl =

X jХ.<Х■' \ J ХуХ2 Х ‘>V ХуХ2Х3 \ / X jA'.ay.

Для задания п местных функций при 3 < « < 1 0 используют прямоугольные таблицы, которые позволяют получить более ком­ пактную запись. Зададим булеву функцию от четырех аргументов / (х0, x lt х 2> х3) при помощи прямоугольной таблицы 5-3.

Из таблицы следует, что заданная функция обращается в еди­ ницу на 12 из 16 наборов значений аргументов. Функцию, которая представлена в виде прямоугольной таблицы 5-3, возможно пред­ ставить ее дизъюнктивной нормальной формой, содержащей 12 чле­ нов. Членами данной дизъюнкции являются элементарные конъюнк­ ции всех аргументов. В данной дизъюнкции, только один из членов равен 1, так как, если поставить в соответствие набору 0111 элемен­

тарную конъюнкцию х 0х 1х 2х3, то очевидно, что только данная конъ­ юнкция обращается в единицу на этом наборе. Так, например:

ХдХуХ2Х3 = 0111= 1.

Получим из таблицы 5-3 СДНФ. Для этого поставим в соответст­ вие каждому набору (табл. 5-3), на котором функция равна 1, эле­ ментарную конъюнкцию максимальной длины и соединим их зна­ ком дизъюнкции, тогда СДНФ будет иметь вид:

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

107