Diskretka

Diskretka.doc20.02.2014

91

ордеревомскорн

ем v (этоордеревоназываетсяподдеревомузла

v);

6еслив. свободномдеревелюбуювершинуназначитькорнем,тополучитсяордерево.

Доказательство

Рис. 9Ориентированные.6. деревьясузлами4

1Кажд. дугая

входиткакой

-тоузел.Изп.определ2 9име.2:.1ениям

v V \ { r } d+(r) = 1,где

r — корень.Следовательно,

q =р

- 1.

2Пусть.

G — ордерево,граф

G' получениз

G забываниориентациирёб, м

r —

корень. Тогда v1,

v2 V (v1,

r) G' & (r, v2) G', следовательно,

v1, v2

(v1,

v2) играф

G' связен.Такимобразом,учип. т4еоремыывая. 9.1.2,

G'-дерево.

3Следует. изпункта2.

G существовалидвапутииз

и в v, тов

G' имелсябыцикл.

4От.противного.Еслибы

5Пусть.

Gv — правильныйподг,оп афеделямножузлов,достиемыйством

жимыхз

v. Тогда

dGv+(v) = 0,иначеузел

v былдостижимизкакого

-тоузла

v' Gv,и,таким

образом,в

Gv, азначит,в

G имелсябыконтур,чтопротиворпункту3Далее.имеем: чит

v' Gv\ {v} d+(v') = 1,таккак

Gv G. Всеузлы

Gv

достижимыиз

v построению.По

опреде9по.2.л,что1ениюучаем

Gv — ордерево.

6Пусть. вершина

r назначенакорнемидугипоследоваориенот«тированыельно

корня»обходомвглубину.

Тогда d+(r) = 0 построению;

v V - d+(v) = 1,таккаквходящаядугапоявляетсяприпервомпосещузла;всении

узлыдостижимыизкорня,таккакобходвглубинупосещаетвсершисвязграфа.ныого

Такимобраз

ом,поопреде9по.2.лордерево1ениюучаем.

Следствие. Алгпоискавритмглубинустроитордекорнемвначаевоуз. льноме

р ориентированныхдеревьев.Таким

Кажсвобдеревпределяетое неболее

образом,общеечислоразличныхордеревьевс

р узламинеболеечемв

р разпревосходит

общеечислоразличныхсвободныхдеревьев

р вершинами

Концеваявершинаордереназывается

листом.

Путьизкорназываетсявлист

ветвью.

Длинанаибветвиордерельшназываетсяй

высотой.Уровень

узлаордерева

—

этор асстоткодояузларн.Самиекореньяимеетуровень

0.Узлыоднуровнябразуютго

ярус дерева.

Замечание

Наср«аститяду»примеещельг«ннойяе»алогическаятерминологияся.Узлы,

достижимыеизузла

и,называются

потомками узла и (потомкиобразуют

оддерево)Если.

деревесущдугаствует

(u, v),тоузел

и называется отцом (или

родителем)узла

v, аузел

v

называется сыном узла и.Сыновьяодногоузланазываются

братьями.

Эквивалентноеопределениеордерева

Ордерево Т — эток нечноемножествоузлов,та

кихчто:

Diskretka.doc20.02.2014

92

1Имеется. одинузел

r, назывкорнемданногоемыйдерева.

k;попарнонепересекающихся

2Оста. узисл(ьныеключаяорень)содержатсяв

множествах Т1,... , Тk каждоеизкоторыхявляетсяордеревом

(k ≥0) .

Нетрудновидеть,чт

Т≡{{

r},Т 1,..Т.,

k}.

оданноеопределениеэквивалентноопределению9Достаточно.2.1.

r

Т1,..Т., k идалее

построитьорг, дугиовоафотзадузлаяанного

ккорнямподдеревьев

повторяярекурсивноэтотпроцессдлякаждогоизподдеревьев.

Упорядоченныедеревья

Множества Т1,.. .Т,

k вэквивалентномопределенииордереваявляютсяподдеревьями.

Еслиотносительныйпоряддеревьевок

Т1,..Т.,

k фиксирован,тоордереназываетсяо

упорядоченным.

Ориентиупоориеядочовантированныеревьятенсивноые

Пример

используютсяв

программировании.

1Выражения. .Дляпредставлвыражзыковпрогрени,какяйправиломмирования,

испориентильзуютсяпорядеревьяованные.доченнпредставлПримерыражения

а+ b*с покнарис. зан9. .7,

2Для.представленияблочнойструктурыпрогр

аммыисвязаннойнейструктуры

областейопреидентлениячастофикаторовсприентированноельзуд можетрево(тся

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

языковпрограммированиясчитаетсянесущественным)На.

рис. бпоказана9.7структура.

областейопреидентификаторовления

а, b,с,

d

е, причемдляотображенияиерархии

исповложенньзовобласти. ые

3Для.представленияиерархическойструктурывложенностиэлемеданных/илитов

операторовуправлениячастоис

пользуетехникаотс,показаннаясяуповрис. 9. .7,

4Структура. вложеннкаталифайловсовременныхстигоперационныхсистемах

являетсяупорядочориентировадеревомнным.Обычдляизображениятакихоным

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

рис. 9г. .7,

(а( b)(с d)(е))))

5Различные. уравновешенные« скобочныеструктуры»например(

являютсяориентиупордеревьяованныядоченными.

Отступление

Тотфакт,чтоб льшинствосистемуправле

нияфайламииспользуетор ентированные

деревья,отражаетсядажетерминологии

— «корневойкаталогдиска».

Замечание

Общепринятойпрактикойизображениидеревьявлясоглашениевт,сяомчто

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

рхувниз,поэстрелкиому

можнонеизображ.Таким,диаграммызомтьсвободных,ориентированных

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

дополнительнуказание,деревокакогоклассаиз набраженодиаграмме.Вбольшинств

е

случаевэтоясноизконтекста.

Diskretka.doc20.02.2014

93

Пример

Нарис. приведены9.8триаграммыдере,которшневьвыглядятне различными.

Обозначимдеревослева

— (1),вцентре — (2) исправа — (3).Какупорядоченныедеревья,

онивсеразличны:

(1)≠(2)

, (2)≠(3) , (3) ≠(1). Какориентированныедеревья

(1) = (2),но (2)

≠(3) .Каксвобдеревьяони, дныевсеизоморфны:

(1) = (2) = (3).

Рис. 9Диаг.8.деревьеваммы

Бинадеревьяные

Бинарное (или двоичное)

дерево - этоконечноемножествоузл,которлибопусто, е

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

- левогоиправого.

Бинадеревоное

неявляется упорядоченнымордеревом.

Замечание.

Понятиедвоичногодопускаетобобщение,

т-ичнымдеревом

называется

конечноемножествоузлов,которлибпусто,либосостоитеизкорня

т

непересекающихся т-ичныхдеревьев,имеющихномера

1,... ,т . Большаячастьутверждений

т-

иалгоритмовдлядвоичндеревьсравнительноможбытьхе легкораспространена

ичныедерссоответствующими( вьямодифик)Поэтому. ,хотянпрактикециями

т-ичные

деревьяииспол

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

деревьями.

Предеревкомпьютереевстав л ние

Обсужпредеревьставлниюможнопревнийдпослаточносвтеже тьи

рассужд,чтобылипреобсуждениюдпосланынияпредставленийграфовсм.( 7

.4)Кроме.

того,следуетпод,чзадачаеркнутьопре стаеревьпрограммелвстречаетсяния

горча,чемщездоадачапредставленияграфовобщеговида,потомуметодыеерешения

оказыещебольшееваютлияниенапрактикупрограммирования.

Представление свободныхдеревьев

Дляпредстаеревьможноисплетениявжельзоватьприёмы,чтодля

представленияграфовобщеговида

— матрсмежностиинциденцийцы,спискисмежности

идругие.Ноиспользуяособенныесвойстдереможноваьев

предложитьсущественнобо

лее

эффективныепредставления.

Diskretka.doc20.02.2014

94

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

кодПрюфера .

Допустим,чтовершиныдерева

T(V,Е)

занумерованычисламиизинтервала

1р...

Построим

последовательность А: аrrау [1р.. - 1]о f 1р.. всоответств иисалгоритмом9.1

Алгоритм9.1.

ПостроениякодаПрюфдеревасвободного

Вход:

Дерево T(V,Е) влюбомпредставленчислами,вершизанумерованыдерева

1

...р произвольнымобразом.

Выход:

Массив А: аrrау [1р... - 1]о

f 1р..

— кодПрюфдеревара

Т.

for: from 1 to p – 1 do

v:т= in {k V|d(k) = 1} {выбираемвершину

v — висячуювершна меньшимну

номером}

А[ i]: =Г(

v) {заносимвкодномерединственсмежнойвершины,

v}

V: = V — v { удаляемвершину

v издерева}

end for

Попостроенкодуможвосстановитьисходноемудеревопомощьюалгоритма

9.2.

Алгоритм9.2.

РаспаковкикодаПрюфдеревасвободного

Вход:

Массив А:

Массив А: аrrау [1р... - 1]о

f 1р.. — кодПрюфдеревара

Т.

Выход:

Дерево T(V,Е)

, заданноемнож ством

рёбер Е, вершизанумерованыдерева

числами 1р... .

Е: =

{вначалемножерёберпуство

}

В:=р1... {множенеисптвовершинльзовамеров}

ных

for: from 1 to p – 1 do

v:т=

in {k В|

j ≥ i k ≠ A[j]} {выбираемвершину

v; — неиспользованнуювершину

снаименьшимномером,которыйневстречосткодаПрюфераетсятке}

Е:Е=+ (

v,А[

i]) {добавляемребро

(v, А[ i]) }

В:=В

- v { удаляемвершину

v изсписканеиспользованных}

end for

Обоснование

КодПрюферадействительноявляпр дставлсвободядер.Чтобыенваогоием

Т'

— дерево,построенноеалгоритмом

9.2 покоду А,

убедитьсявэтом,покажем,чтоесли

котпорыйалгстроритмомен

9.1 подереву

Т,то

Т' изоморфно Т, Т'Т~ .

Дляэ тогоустановимотображение

f:р→11р....

междуномвевдеревьяхшинами

Т,

и Т' порядкувыборавершиналгоритмах:есливершина

v выбрана

i-омшаге

алгоритма9товершина.1,

f(v) выбрана

i-омшагеалгоритма

9.2.Заметим,что

Dom f =

1р.. ,поск

олькувисячиевершиныестьлюбомдереудалениевисячвершиный

оставлядерево.Далее,вомт

Iт f =р 1.. ,посколькуна

i-омшагеалгоритма

9.2

использовано i - 1 чизсло

р чиостаётсясел

р – i + 1 чисел,авхвостекодаПрюферазанято

неболее

р –

i чисел.Болеетого,

v

f(v)

= v.

Дейст,номеравершинительно,которые

являютсявисячимиисходномдер,непоявляютсявекодеПрюферакроме( ,можетбыть,

однойвисячейвершнаиномеромбны),альшимномеравершин,которые

еявляются

висячими,обязатепояв.Поскльнояютсяпривыборепервойлькувершины

v валгоритме

9.1 всершинысме ьшимиомявляютсяерами,сячимиихномерабудет

9.2.

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

Такимобр,нпервомзомшагеалгоритм

9.2 выбереттужевершину

v. Нопослеудаления

вершины v навторомшагесноваи деревоеется,ккотпримромутежрассуждениянимы.

Итак,

f - тождественноеи,значит,взаимно

-однозначноеотображ.Заметимтеп ние

ерь,

чтодляпределения

i-огоэлементакодана

i-омшагеалгоритма

9.1 используется,азатем

удалетсяребро

(v,

А[ i]) ивточностижеребродобавляетсядерево

Т'

на i-омшаге

алгоритма 9.2.Следовательно,

f

-

взаимно-однозначноеотображ,сохраняние

ющее

смежностьи

Т~Т'.

Diskretka.doc20.02.2014

95

Пример

9.10,кодПрюфера

7, 9, 1, 7, 2, 2, 7, 1, 2, 5, 12. На

Длядерева,представленногонарис.

этомрисункечиславвершинах

- этоихномечисла,а нарёбрахуказываютпорядок,

которомбудутвыбивершиныратьсясячиеуда

лятьсярёбраприпостроениикода

Прюфера.

Предстбинадеревьеввлениеных

Всвободнриентироватьякоедеревм жно,назначиводинизузловкорнем.Всякое

ордеревоможнпроизвоупорядочить.Дльно

отоднмкбратьевузлаого()

упорядоченордеопреотваделеностаршешениего

-младшелеве(

-правее)Всякое.

упоряддеревом предстжночбиннноеаер,витьпроведянымевомправуюсвязьк

старшемубрату,левую

— кмладшемусыну.

1Списочные. структуры:каждыйузелпредсзаптиавляетсяпасью

N,содержащейдва

поля( t и r)суказнлевыйателямиправыйузлыещеоднополе

r дляхраненияуказателя

наинформацию

обузле.Деревопредставляуказнкорень.телемТиптся

N обычно

опредследующимобразомляется:

n(p) объемпамяти,занимаемойпредставлбинаде,гдереногониемва

Обозначимчерез

- чисуз.Наиболеелочастовиспо представленияьзуюбинартсящие

ныхдеревьев.

N = record i: info;↑N l,r:

end record

Дляэтогопредставления

n(p) = 3p

Diskretka.doc20.02.2014

96

2.

Чтотакоестепеньв ршины?

3.

Перечислитеоснпо,внысвязанныенятиянеориентированнымиг

рафами.

8. Вчемсостоитматричныйспособзаданияграф

а?

13.

Сформулируйтепонятиесвязностиграфа.Какой

фназываетсясвязным?

19.

Какойграфназываетсягамиль

тоновым?

Таккакзданвсегомиравершивозведенонно

премудрымТворцо,томиренепроисходитни,вчемго

небыловиденсмыслкакого

-нибудьмаксилимума

минимума.

Булевойалгеброй

называетсядистрибутивн

аяструктуранеравнымидругу

Эйлер

единицей 1 инулем

0,вкоторойвсякийэлемедополнениент.

Булеваалгебра

всегда

содменеержитдвухэл .Алгебраментов,содержащаятолько

1

и 0,называется

вырожденной.

Оснлогическвныефункциие

Обозначим через E2 = {0, 1}

– множество,состоящчиселиздвух.Числа

0 и 1

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

“ложь” (

= {0})икак

“истина”=( {1}

).

… E = En являетсямножествомупорядоченн

Декартопроизвоедение

EЕ

ых

наб,состоящихровиз

п чиснулей( единиц)Какизвестно. ,

Еп cодержит

2п элементов

(упоряднаборов)Само. мнченныхжество

Еп можноестественнымобразомупорядочить,

k,

длячегодостаточносчитатькажнабвоичнымыйразложениемцелогочисла

записаннспомощьюго

п знаков.Упорядочениенаборовпроводитсячислу

k .

На,пример

п = 3 множество Е3 можетбытьупорядоченоследуюобраз. щим

0

1

2

3

4

5

6

7

000

001

010

011

100

101

110

111

Такупорядочениещеназывают

“скользящейединицей”

.

Этот

естественныйпорядокэлементов

Еп являетсамымраспространеннымя,но

иногдаудобендругойспосупо.рядоченияб

n переменных

Логическойбулевой( )функцией

(илипростофункцией)

y = f(x1, x2, …, xn)

Diskretka.doc20.02.2014

97

назывтакфункцияа,етсякоторойвсеп ременныеиса

мафункцмогутприниматья

толькодвазначения:

0 и 1.

0 и 1 называются

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

логическими переменныЗаметиили(просто). ,енныгическаячтол переменная

х можетподразумеватьчислом

0 некотороевыс,котазываниело,пжнорчисломд

1 выс,котороеазываисти. нноие

Пример.

ВысказыМосква“ находитсяЕвропеание”являетсяистинным,значит,точки

1.

зрениядискретнойматематпринз ачениемаетки

Высказываниесутках“ 27часов”является

ложным,ипеременная,котораязамен ет

этовысказывание,при ачениеимает

0.

Имногоеетвыс,якоторыеазыванийл бост,лложныбо, которыхмыне

знаем,чтои енасамометтоделе.Например,высказываниестудент“ Петровимеется(

видуко

нкрче)тныйимеетловкомпьютердома”Такого. родавысказываниятребуют

проверкиконечно(,еслнамваженэтотфакт)Поэтому. счи, переменнаяаем,

0 или 1.

заменяющаяэтовысказываниеможетпри ачениеимать

п переменных – это

Изопределелогическойфункцииследуеия

т,чтофункция

отображение Еп в Е, котмозадатьроежнопосредсттаблицей,называемойенно

таблицей

истинности даннойфункции.

Пример.

f(x,y,z)

Функциятрпеременных

можетпредследующейтаблицейляться

истинности.

x

y

z

f

(x,y,z)

Этоозначает,что

f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0)ит.д.

= 1

Двефункцииравны,есловпадаютихтаблицыистинностина(объединенномнаборе

переменных).

Еп всегдаупорядестественнымобразомчены,это

Притакомзадн нииборы

позволяетопределятьфункциютолькопостолбцомледнимкоторый( иногдадляэкономии

f(x,y,z) можнозадать

местазаписываетсястрочку)Например. ,нашемфункциюере

так: f = (10110100),этоозначает,что

постолледнийтаблицыистинностиец

Заметим,чтовсефункции

п перетакжеменныхожноперенумероватьпопринципу

“скользящейединицы”Теоретически. числотакихфункц й

– 22n , нонекоторыеизних

являютсяпосущес

твуфункцменьшегочиперемямисла,двенных

– вообщеконстантами.

Еслифактическифункцнезависитнекоторойяпеременной,тотакуюпеременную

называют фиктивной.

Теперьможнописатьосновныефункциидискретнойматематики.

Булевафункция.

Булевойф

ункцией от n аргументов x1, x2, … ,xn,

называетсяфункция

f из n-ойстепени

множества{0,множество1}{0, 1}

f: {0,1}n .→ {0,1}, т.е.функция,котораяпроизвольному

наборуизнулейиединицставитсоозначениеветствиефункции

(ФАЛ)называютсятакжебулфункцвыми,

ями

f(δ 1, δ2, δ… , n) {0,1}.

Функцииалгебрылог ки

двоичными

функциями и переключательнымифункциями

.

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

сигналввых.Поустдныевройствоь

f

имеет n входов x1, x2, … ,xn накотморыежет

подаваться(1)илинеподаваться(0)одинквых,накотодестькром(1)или(0).

xi = 1 интеркакпосретоканауплениеирутся

i-й

Такимобразом,значениепеременной

Diskretka.doc20.02.2014

98

вход,а

xi = 0

- какнепоступ

лениитока.Значениевыходеустройства

f(δ 1, δ2, δ… , n) = 1,

означаеттоквыхопризадвходеанноми

f(δ 1, δ2, δ… ,

n) = 0 - токанавыходенет.

Иначеговоря,булевафункция

– этофункция,аргументызначениекоторой

принадлежитмножеству{0, 1}.

Множество{0,мыбудальнейшем1} бозначатьчерез

B.

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

n аргумеможрассматриватьнтовкак

n-местнуюалгебраическую

операциюнамножестве

B.Приэтомалгебра

<B;W>,где

W –

множествовсевозможных

булевыхфу,называетсякций

алгебройлогики .

Вдискретнматематикебольшуюиграютйконечныефункции.

Конечнойфункцией

называют отображение одногоконечногомножествадругое.

Важныйклт функцийсскихобразбулевыфункции.ют

Булевафункция

(от n переменных)

- этопроизвольное

тображениевида

f: Bn →B,

B={0,1};

n-элементныхпоследовательностей(

n-

Булевафункцияопределенамножествевсех

элемекорт)нулейтныхижейдипридвцнимаетозможныхзначения: 01.

Булеваконстанта

- это индивиднконстантая

собласть

юзначений

{0,1}.Таким

образом,существуетдвебулевыконс: и0Поантыопределению1. принимается,что

нульарная операция).

каждаябулеваконстанта

естьтакжебулфункцияотвапеременных0 (

Булевопеременное

- это индивидноепеременное

собластью значений {0,1},т.е.это

переменное,кот принимроежеттолькодвазн:ачениять01.

f: {0,1}n →{0,1} задается y = f(x1, . . . , xn), вкоторойкаждое

Тогдабулевафункция

булевопеременное

xi (i = 1, . . .,n)

ифункция f принимаютдвозможных

начения: 01.

Переменные x1, . . . , xn называют - переменбулевойфункцииыми

f.

Кортежизмножества

{0,1}n

называется наборомзначенийпеременных

x1, . . . , xn .

Мощностьэтогомн 2жества

n

Числофункции

f: M → N равно NM

(2 встепени

2n

22n )

Булевфункцмопрйжнодругойиидатьсмысл.

1 – истина

0 – ложь

Тогдаизпростыхвысказывсложноейможносо та. вить

Алгебралогики

- множествовысказыванийопераций

- одной унарной и4

бинарных:

А1 = ‹b, { ← , , ,→, ~}›

← : {0,1} → {0,1} - отрицание

: {0,1}2 → {0,1} - конъюнкциялог(.умножение)

– "и"

: {0,1}2 → {0,1}- дизъюнкциялог(.сложение)

- "или"

Или 1 – включено, 0

- выключено.

Тогдаполучаемпереключательнуюфункциюилидвоичнуюфункцию

Примеры

Параллельноеипоследовательноесоединения

Двоичноедерево

Двухэлементнаябулеваалгебра.

Рассммножествотрим

Во = {0,1} иопределимнанемоперации

, ,

,согласно

таблицамистинностиформул

x y , x y ,

.

x

Тогдасистема

Bо =

B0 ; , ,

,0,1 являетсядвухэлембулевалгсвсемиобройнтной

свойстваминаопер.Формулыалгец и

Bо.

брылогики,содержащиелишьлогическиеоперации

, ,

являютсятермами

Термом

являетсяюбоефункциональноевыражение,

Diskretka.doc20.02.2014

100

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Этоэлементарныефу

нкцСимволы.

- логическиесвязкиоперации( )

f0

- константа 0.

f1 – конъюнкция f1 = xy ( x&y; x y)

f2 – запорет

y

xy

f3 – повторение

x

f4 – запорет

x

xy

f5 – повторение

y

f6 – суммапомодулю2

f6

= x y

f7 – дизъюнкция

f7 = x y

f8 – стрелкаПирса

f8 = x ↓ y

f9 – эквивалентность

f9 = x ≡ y

f10 – отрицание y

f10 = ¬y

f11 – импликацияот

y

к x y → x, y x, y x

f12 – отрицание x

f12

= ←x

f13 – импликацияот

x

к y

x → y, x y, x y

f14 – штрихШеффера

f14

= x

y

f15

- константа 1.

ДляинженВТалглогикиебраВТ(

– алгпебрареключательныхсхемили

комбинацлогика)являесисоннаятсяемо

йалгебраичлогическихметодовреш ния

зад,тасовокупныхкжечзадач,решаемыхтакимиметодами;дляВТ

- этоинструмент

синтезакомбинационявляющихсясхем, ча лучаэлементнойтныконм????,чных

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

менты,

Предметдвузначнойалгебрылогикиявлм.однородныедвузначныелогические

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

(упрощение,минимизацрешения)сцеалгорьюизадачтмизации.

Валгебрелогикивыскразывания

ссматриваютсятолькоточкизренияистинности

иложноибезрассихтиматриваниясмысла.

Индексфункции

fi(x,

y) являетсядесятичнымэквивалентомчисла,чного

образованногоизвекторазначефункциинаупорядочиймножнаборовзначенийнномстве

аргументов:

{(0,0),(0,1),(1,0),(1,1)}.Функции

f0,

f3, f5, f10, f12, f15 являютсярасширениемна

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

f1(x,y) = x y

(конъюнкция)

f7(x,y) = x

y (дизъюнкция)совместнофункциейинверсии

(f10, f12) были

использованыпредыраздляпостроущихелахфоремдставления

переключательныхфункций,пригодныхдляаналитереключательныхскойзаписи

функцийпроизвольнойсложности.

f0 = 0 и

f15 = 1

Рассмболееп дэтфункциироб.Двемизнихо

являются

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

обозначения.Заметим,чтоэтиобозначенияневсегдаобщеприняты.

Перечислимважнейш7 функц: ихй

И ( )) двухыск

азываний X и Y называетсявысказывание

X

1)конъюфункция(

Y, котороеис олькоинновтомслучае,когда

конъюнкций

X и Y обаистинны.

Таблицаистинностидля

X Y

X

Y

0

0

0

0

1

0

1

0

0