книги из ГПНТБ / Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие

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

Система функций, которая в сумме накрывает значками «-}-» все пять колонок (табл. 4-15), является функционально полной. Несо­

стемы, состоящие из определенного количества элементарных буле­

Анализ таблицы 4-15 показывает, что несократимые полные системы элементарных функций могут состоять не более чем из трех функ­ ций.

К числу несократимых не относится система (Д , V>—), а так-

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

Система (Д , \J , —) и максимальная являются функционально полными. Из системы (Д , \J , —) может быть исключена без нару­ шения полноты одна из операций: «—», «Д» или «!/»•

Из максимальной системы могут быть образованы все несокра­ тимые системы.

Вопросы и задачи для самопроверки

1.Какие функции называются переключательными?

2.Как зависит число различных переключательных функций от числа ар­ гументов? Подсчитайте число различных функций от двух, трех и четы­ рех аргументов.

3.Составьте таблицы значений функций:

/1 (Х1 >х2<хз) = *1 V х2х3 >

/ 2 (xlt х2, х3) = (х, V х2) -> (хх V х3).

101

Глава пятая

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

§ 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

мых конституентами единицы. Например, для функции / (х1, х 2, х 3, х4) конституентами единицы являются элементарные конъюнк­

ции ХуХ2х^>с4, ХуХ2х3х4. Для функции п переменных конституенты еди­

ницы имеют вид х хх 2 . . . хп.

Конституента единицы принимает единичное значение тогда и только тогда, когда все буквы принимают единичные значения. Смысл термина «конституента единицы» поясним на следующем примере. Предположим, что задана постоянно истинная четырех­ местная функция. Выразим эту функцию в виде формулы:

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

Если считать единицу функцией п аргументов, то ее можно раз­

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

наборов значений п равно 2 " .

О п р е д е л е н и е . Совершенной дизъюнктивной нормальной формой [СД Н Ф ] переключательной функции называется дизъюнк­ ция тех конституент единицы, которые обращаются в единицу на тех же наборах значений аргументов, что и данная функция.

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

Сокращенная запись СДНФ имеет вид:

/ = V $ при i = 0, 1, . . . , (5.8)

здесь п — ранг конъюнкции; i — номер набора, на котором функ­ ция принимает значения 1.

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

Пример 3. Разложим на конституенты единицу. Для этого пред­ ставим 1 = х V х, или 1 — (хг V ^iM*» V х 2). Использовав рас­

108

пределительный закон умножения относительного сложения, по­ лучим: 1 --x Lx 2 V x ix 2 V х 1 х з V х хх2•Аналогично

1= (Х1 V *i)( * 2 V Ч) {хз V Ха) = (*i*aV x~i*2 V \/-П■^'2 V -И^2)‘(-'-3V *з)=~X|XoX;j\УXiXgXg \/ Х2Хо\/

У-И^2 -^3V xlx2Х3 V Х1 Х2 Х3 V Х1 Х2 Х3 V И Х2 Х3.

Вобщем случае:

Слагаемые (5.9) называются конституентами разложения еди­ ницы «1». Конституенты «1» обладают следующими свойствами:

1 )произведение двух каких-либо конституентов «1 »равно нулю, так как любые два конституента обязательно содержат хотя бы одну одинаковую переменную в различных степенях (переменную и ее обращение)-,

2 )сумма всех конституентов единицы равна единице.

Указанные свойства запишем в виде формул

kr kj = 0 при i Ф j (i, / = 0, 1, 2, . . . 2'1-1);

2«—1_

1= V к

1-0

Любой конституент разложения «1» в соответствии с принятыми обозначениями можно записать,

— п °k ki = Д xk . ft=i

В алгебре релейных схем «1» представляет модуль умножения. Выше отмечалось, что любая булева функция имеет несколько ДНФ и одну СДНФ. Любая ДНФ получается в результате миними­ зации СДНФ. Переход от ДНФ к СДНФ называется развертыва­ нием. Развертывание можно выполнить с помощью законов (1—10).

Рассмотрим пример перехода от ДНФ к СДНФ.

*1 * 2 V % V *0*1 * 2 V *3 = *1 * 2 (хо V х) (х3 V *з) V *0*2 •

• (*i V *1 ) (*з V *з) V х о x i Х2 (*з V *з) V *з (*о V х 0) (хг V *1)•

• (х2 V х2) = Х 0Х гХ 2Х 3 V *0*1*2*3 V х0*1*2*3 V х0 Хх х2х3V Х 0ХхХ2Х3 V

109

V *0*1*2 *S V *0 *1 *2 *3 V *0 *1*2 *3= *0 *1 *2 *3 V*0 *1 *2 *3 V

V Х0*1*2*з\/ *0*1*2 *3 V *0 *1*2*3 V *0*1*2*3 V *0*1*2*3 V *0*1*2*3 V

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

Формула (5.11) представляет конъюнкцию 16, то есть всех воз­ можных различных элементарных дизъюнкций максимальной длины.

В данной формуле нулевое значение аргумента обозначается его буквой без знака инверсии, а единичное — буквой со знаком инверсии. На каждом наборе обращается в нуль лишь одна из дизъюнкций формулы (5.11), чего, однако, достаточно, согласно закону (5) для обращения всего выражения в нуль. Таким образом, можно сказать что формулой (5.11) представлено разложение нуля на его конституенты (составляющие), являющиеся элементарными дизъюнкциями 4-го ранга.

Теорема 3. Любую функцию алгебры логики (теорема де Мор­ гана) f (*х, *2, . . . , хп) (л!> 1) можно представить в форме:

110