Цифровая электроника

11

§ 1.3 Булевыфункции.

СпособызаданияБулевыхфункций

Вселогическиесхемы,используемыевцифровойэлектронике

,являютсяпрямой

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

устройство,егонеобходимоматематичскиопис.Это ьопиматическоев егдаание

начинается построБулфуе,твых.не.длякцийияопределеннойкомбинациидвоичных

переменныхзадаетсязначениеБулевыхфункций.

ЗадатьБулевуфункцию

–

это указать,

прикакихкомби

нацияхпеременныхона

равна0

,априкакихравна

1.

F = F(A,B,C,…где),

A,B,C,… - аргументыфункцииϵ{0,1};

F – результатилисамафункцияϵ{0,1}.

Каждуюкомбиаргументовназываютцию

набором. Каждомунабор

присваиваномер.Общномернаборапринятосчитатьравнымчислу, тображаемому

вскобкахдвоичнымипеременными.

Пример:набора

вен5 ( n=5)

Описываемфункцию

F длянабора:

F=F(1,0,1); (A,C = 1, B = 0).

Еслифункциязаданавовсехнаб,ттакофрахунюазываюткцию

полностью

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

недоопределенной (илифакультативной).

Факультативными называютусл,кодлягдавиянеопрнаборовееделенных

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

преобразованияопираютсянаосновныетеоремыБулалгебры.вой

Порядвыплолнениягически

хоперацийвконечномвыраженииполностью

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

а)Еслиинверсиятольконадпеременной,тоонавсегдавыполняетсяпервой;

б)Еслиинверсияалгебраическимдвыражением,то

онавыполняетсярамках

данногоприлпосл.жениядней

Приэтомзнраквенствауказыватолькона,чтеиправыетчастиотнего

тождественны.

СуществуютследующиеспособызаданияБулевыхфункций:

1. Словесный (опи)сательныйпособ

– функция задаетсяввидетекста.

Пример:

F(A,B,C)=1,еслиаргумевданнабореимомтыютчетноеколичединицство

(илиесдвалиюбыхаргументафункцииравны0).

2. Табличный способзаданияБулевойфункции

– стротаблицастинностится,в

которойуказываютсяно

меранаб,соответствующееровсостояаргументовиз ачение

самойфункции.

Например:задт бличнымдимспособомБулевуфункциюизтрехаргументов,

котораяпризначечетномимаетединпр значениицынулейаргументов:

№

A

B

C

F

набора

0

0

0

0

0

1

0

0

1

1

2

0

1

0

1

3

0

1

1

0

4

1

0

0

1

5

1

0

1

0

6

1

1

0

0

7

1

1

1

1

Пример:посттаблспособомчнымиБулевыфункцииуправления

семисегмениндикаторомдлятрехвходныхным

аргументов.При

этомпримемво

внимание,что

если логической единице – сегоримент,прилогическомнуле

– погашен.

a

g

f

b

e

c

d

ТаблицаБулевыхфункцийуправлесемисегмениндикаторомия: ным

№ набора

Переменные

Булевыфункции

x1

x2

x3

a

b

c

d

e

f

g

0

0

0

0

1

1

1

1

1

0

1

1

0

0

1

0

1

1

0

0

0

0

2

0

1

0

1

1

0

1

1

1

0

3

0

1

1

1

1

1

1

0

1

0

4

1

0

0

0

1

1

0

0

1

1

5

1

0

1

1

0

1

1

0

1

1

6

1

1

0

1

0

1

1

1

1

1

7

1

1

1

1

1

1

0

0

0

0

Такимобразом,

заданосразусемьБ функцийлевых,которыезависятобщихтрех

элементов.

АлгебрспособзаБулевыхданияическийфункций

ИсходнымдлятакогоспособаявляетсятабличзадаБулевыхфункцийиое.

Аналформанеобходимагичнаядляпереходакструктурнойсхеме

,дляминимизации

Булевойфункциисцельюпоследуюразмецифровщустреегонкриияаой.гостваалле

Существуютдвариантазадания

функцииалгебраическимспособом

:

1. Нормальнаядизъюн

ктивнформаилиз даниеБулевыхяфункцийпоединицам.

Алгоритмзаданияс

ледующ:изтаблвыбираютсяноцый

меранаборов,гдефункция

14

переменнаяравнато0,

наберетсяинверсиэлементарное( й

произведение -

произвевспеременныхдданногляение

онабора).

Зададимфункцию

fe и f g :

2. Нормальнаяконъюнктивнаяформаили(задание

Булевыхфункций

понулям).

Изтабл ицыв бираютсянаборы,гдефункцияравна

0истроитьсяпроизведение

элементарныхсуммдля

этихнаборов.Еслипеременная

авна

1,тоонаберется

с

инверсией. (

Элементсуммарная

– суммавсех

переменныхдляда абораного).

Например, зададим

fa и

fd :

fa = ( Х + Х +

) (

+ Х + Х )

Х

Х

$!!#!!" $!!#!!"

1

2

3

1

2

3

1а

4а

fd = ( Х + Х +

) (

+ Х + Х ) (

+

+

) = f (

+

+

)

Х

Х

Х

Х

Х

Х

Х

Х

$!!#!!" $!!#!!" $!!#!!"

a 1

2

3

1

2

3

1

2

3

1

2

3

1d

4d

7d

Какизфотдатьйрмпредпочтение

– определяетсяэффективностьюминимизации

Булевойфункции

. Обеформыабсолютнотождественны.

ЧислспзаданияосБулевыхфункцийоб

Являетсянаиболеекомпдляз дактнымия

Булевыхфункций

,нокрайне

неудобен

дляихминимизации.

Также существуетд ухариантахпо(ед поицамуля

).

1По.единицам:

f g =Σ(0,4,5,6).

2. Понулям:

подзнакпроизвмскобкахпедренчисляются

номеранаборов,гдефункция

равнанулю

:

fa =П(1,4)

fd =П(1,4,7).

§ 1.4 Переходоталгебраическойформы

кструктурнойсхеме,и

наоборот.

Функциональнополн

ыесистемылогическихэлементов

Дляпрактическойреализации

Булевойфункции

надооталгебраическогоспособаее

представленияперейтикструктурнойсхеме.

ихвходамивыходамисвязями.

Структусхемавсегдапредставлянаяграфич. ескится

x1

&

F = x x ... x

xn

1

2

n

Элемент ИЛИ:

x1

1

F = x + x

2

+ ... + x

n

xn

1

Элемент НЕ:

x

1

F = x

(толькоодна

переменная )

x1

=1

F = x1 x2 =

(толькодвеп ременные

)

x2

= x1 x2 + x1 x2

Супомодулюма2

– этоисключающееИЛИ

надмногимипеременнымипроверка(

Вкачествеприм ра

перейдемоталгебраическихформ

ранеерассмотренных

Х1

1

X1

1

X1

&

X2

1

X2

&

1 Fe

X3

1

X3

&

X1

&

X 2

1

1

X 3

Fx

&

X 2

X 3

1

X2 X3 +X1 X2

1

X1

&

X2

X1

X2

1

1

F

X3

&

X2 X3

F = x1 x2 + x2 x3 + x2

(т.е.идемнаоборот,справа

– налево).

Прииспользовинтегральныхтехнолоказываетсянииболеегийнологичным,

есливструктурнойсхемеиспользоваколичествоменьшеефу кционально

-разных

логическихэлементов.

Оптимявляетсяа,льнымрикогзаднтаействольккакойван

-тоодин

функциональныйэлемент,всвязиэтбылоразработаномфункци5

нально

-полных

системлогическихэлементов.

Под функционально-полнойсистемой

понимаюттакойнаборлогическихэлементов,

спомкотможнощьюреарыхлюбуюизовать

Булевуфункцию

:

1Набор.

: И, ИЛИ,НЕ

.

Недостаеттолько

XOR:

НЕ

И

&

X1

1

ИЛИ

1 F

X 2

1

&

Реализуемимеющихсяэлемоперациюнтов

ИЛИ:

Используемтеорему

Де-Моргана:

x1 x2 = x1 + x2 ; x1 + x2 = x1 x2

ИЛИ:

F = x1 + x2 = x1 x2

X1

НЕ

X1

1

И

НЕ

&

1

X2

1

X2

3Набор. :ИЛИ,НЕ.

Недостает:И,

XOR.

4. Набор:

И – НЕ.

Недостает:И,НЕ,ИЛИ.

Составтаблистинностидляцуэлемента

2И – НЕ:

Х1

Х 2

Y

0

0

1

0

1

1

1

0

1

1

1

0

0

0

1

0

1

0

X

1 Y =X

1

0

0

1

1

0

§ 1.5 МинимизацияБулевых

функций. Карты Карно

Под

минимизацией Булевыхфункций

понимаютупрощениеисходного

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

минимальногоколичестваполупрструктур. водниковых

Исходдляминявляетсяымиалгебраическаяизациифоп маедставления

Булевых

функций. Процедураминимизацииопираетприменениесновныхятеорем

Булевой

алгебры.

Критеруспешнойминимизацииемявляесоотсяношен

иемеждуисходным

количествомполу

проводниковыхструктур, ихколичествомокончательномварианте.

Количествополу

проводникструктуропределяетсяследующимвыхправилам:

• Однивыходлогическогоэлемента

ИилиИЛИэквивалентенодному

полупроводниковому диоду.

• ОперацияНЕэквивалентнаоднполуму

проводтранзист. иковоруму

Например:

здесь: 4

– диода, 1

– транзистор.

Рассмотримтех

нологию минимнапримзации

ерахизпредыдущего( параграфа),