Diskretka

Diskretka.doc20.02.2014

2

КлашановФ..Дискрматематика.Курстнаяле

кций.Учебноепособие.М.МГСУ: ,

2011. – 198с .

Вучебнпосдискретнойбиимматематикепредсматериалвпомощьавлены

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

строительномуниверситенафакульИСТАСобучающихсятете

по направлению

подготовки230100

«Информатикавычислительнаятехника

»,ап рофильподготовки

:

Автоматизсистемыобработкинформациированныеуправлениястро тельстве

(АСОИУ)

иСистемыавтоматизациипроектированиеСАПР()строительстве

.Учебное

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

состоитиз

следующих взаимосвязаразд:элетеориилмевн;сведенияхожествыизбулевой

алгебры;элементыкомби;остеорииовыаторграфов.Учебноепособиекивзаимосвязано

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

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

односеместровоеза ятиеа1

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

Вконцекажд

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

Diskretka.doc20.02.2014

3

Лекция1

………………………………………………………………………………….

8

ВВЕДЕНИЕ ……………………………………………………………………...

8

Цельизад ачипредмета……………………………………………………….

8

Преддискретнойма ематики…………………………………………….

9

Основныеразделыдискретнойматематики……………………………….

10

Изоморфизм……………………………………………………………………

11

Контрольныевопросы…………………………………………………………………

15

Лекция2

………………………………………………………………………………….

16

ОСНТЕОРИИМНОЖЕСТВВЫ

…………………………………………………...

16

Интуитивноепонятиемножества.Основпри………………….ципыые

16

Множествоиэлементымножества…

……………………………………….

16

Конибесконечныемножества……….

……………………………….

18

Заданиемн ожества. ……………………………………………………………..

18

Мощностьмножества…………………………………………………………...

18

Подмножество,собственнподмножество………………………………..

20

Кортеж……………………………………………………………………………

21

Символичязыксодержательныхмножествскорий………………

22

Добавлениеудалениеэ

лементов………………………………………….

23

Булеан и универсумом

……………………………………………………….

24

ДиаграммыВеннаКруги( Эйлера) ……………………………………………

24

Ограмниченные.ожестваГрам ицыожеств…………………………….

24

Точверхняя(аяижняя)граница…………………………………………..

25

Принципдвойственности

………………………………………………………

26

Линейныепространства………………………………………………………...

26

Контрольныевопросы…………………………………………………………………

31

Лекция3

………………………………………………………………………………….

33

ОПЕРАЦИИНАДМНОЖЕСТВАМИ

……………………………………………...

33

Симметрическаяразность

……………………………………….…………….

34

Дополнение ………………………….………………………………………….

34

Двумопестныерации

……….………………………………………………….

34

Порядвыпоперацлненкияй

.……………………………………………..

34

Теоретико-множественныетождества………………………………………

35

Законыдля

объединенияпересечение

…………………………..……….

31

Законыдлядополнений

……………………………………………………….

32

Законыдляразностеймножеств

…………….……………………………….

32

Покрытиеразбиениемножеств

…..………………………………………

37

Частичноупорядочмноженныества

……………………………………………..

38

Контрольныевопросы…………………………………………………………………

40

Лекция4

………………………………………………………………………………….

41

ОТНОШЕНИЯ.ОТОБРАЖЕНИЯ.СООТВЕТСТВИЯ

…………………………...

41

Бинарныеотнош ния

…………………………………………….…………….

41

Свойсбинарныхтношенийва

……………………………………………….

42

Отношениеэквивал нтности

…………………………………………….

43

Отношение толерантности .………………………………………………..

45

Отнпошениярядка

………………………………..………………………

45

Тернарныеотношения

…………………………………………………………

46

n-арныеотношения …………………………..………………………………….

45

Отображения …………………………………………………………………….

46

Соответствие……………………..

………….………………………………….

46

Функция

…..………………………………………………………..……………

46

Предсфункциивтермавлениеотношенийнах…………………………..

47

Diskretka.doc20.02.2014

4

Функции,функционалы,операторы…………………………………………..

50

Суперпозициябинарныхотношений

……………………………………….

51

Обратнаяфункция……………………………………………………………….

51

Классификацияотображений………………………………………………..

51

Операция…………………………………………………………………………

51

Частичноупорядочмнож………………………………………..енныества

52

Минимизациипредставлениямножества…………………………………..

52

Контрольныевопросы…………………………………………………………………

53

Лекция5

………………………………………………………………………………….

55

ЭЛЕМЕНТЫКОМБИНАТОРИКИ

……….….……………………………………...

55

Основныеправилакомбинаторики

…………..……………………………….

55

Правилопроизведения

…………………………………………………….

55

Правилосумм

……………………………………………………………….

55

Перечислкомбинаторикательная

…………………………………………..

54

Перестановки ………………………….……………………………………

54

Размещения ……………………………….…………………………………

56

Размещениясповторениями

…………….…………………….……….

56

Упоразмещеядоченноеие

…………………………………………….

57

Сочетания ………………………….……………………………………….

59

Сочетаниясповторениями……..

…………………………………………

59

Комбинацииэлементовсповторениями

………………………………

59

БиномНьютона………………………………………………………………….

61

Разбиения.

Комбинаторные числа СтиБелларлинга

………………….

62

ЧислаСтирлинга2

-города……………………………………………...

63

Метпроизводящийфункций………………………………………………...

64

Контрольныевопросы…………………………………………………………………

66

Лекция6

………………………………………………………………………………….

67

АЛГЕБРАИЧЕСКАЯСИСТЕМА

……….…………………………………………...

67

Замыканиеподалг бры

………………………………………….……….…

67

Морфизмы…..

…………………….…………………………………………….

68

Гомоморфизмы

…………..………………………………………………….

68

Фундамалгебрынтальные

.……………….…………………………………..

69

Алгебрысунарнымиоперациями……...

……………………………………

69

Алгебрысбинарнымиоперациями

…………………………………………

69

Алгебрысоднойбинарнойоперацией

…………………………..………….

69

Полугруппа ………………………….…………………………………………….

70

Моноид………………………….. …………….………………………………….

71

Группоид

…..…………………………….………………………………………

71

Группа………………………………………………………………………………

72

Абелевагруппа…………………………………………………………………

72

Алгебрасдвумяоперациями………………………………………………..

72

Кольца………………………

.…………………………………………………

72

Тело…………………………………………………………………………….

73

Поля…………………………………………………………… ………………

73

Отношения………………………………………………………………………

73

Граф………………………………………………………………………………

73

Матрицасмежности…………………………………………………………….

73

Фактор-множества ифактор -алгебра ……………………………………………

74

Diskretka.doc20.02.2014

5

Целыечислапомодулю

m …………………………………………………………

74

Конгруэнции ……………………………………………………………………….

75

Контрольныевопросы…………………………………………………………………

76

Лекция7 ………………………………………………………………………………….

76

ЭЛЕМЕНТЫТЕОРИИГРАФОВ

……. ……………………………………………...

76

Определение ……………………………………….……………. ………………...

76

Граф,ве, шинаебро…………………………….

………………………….…….

77

Неориентированныйграф

……….…………………………………………….

78

Инцид,смеграфшнтностьнный

.……………………………………………..

78

Эквивалентныйориентированныйграф

………………………………………

78

Обратноесоответствие…………………….

………………………………………

79

Изоморфизмграфов

……………………………………..………………..……….

79

Путь,ориентированныймаршрут

……………………………………………….

79

Смежныедуги,смежныевершины,степеньршины

……………………….

80

Компонентнаясвязность

………………...………………………………………

80

Графсовзвешеннымидугами………….

..………………………………………

81

Подграф …………...……………………………………………………………..…

87

Контрольныевопросы…………………………………………………………………

87

Лекция 8 ………………………………………………………………………………….

88

ДЕРЕВЬЯ ……. …………………………………………………………………..……...

88

Свободныедеревья

…………………………….……………. ………………...

88

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

…….…………………..

91

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

……………………………………………………….

91

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

…………………………………………..

93

Контрольныевопросы…………………………………………………………………

97

Лекция 9 ………………………………………………………………………………….

98

БУЛЕВААЛГЕБРА

...……………………………………………………………….....

98

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

…………………………………………………..

98

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

……………………………………………………….…………….

99

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

100

…………….

y = f(x) ………………………………......................

100

Функцииоднойпеременной

101

Таблицы булевыхфункций……………………………………………………….

101

Функциидвухпеременных

z = f(x,y) ………………………………………………

105

Порядвыпоперацлненкияй

……………………………………………………

105

Эквивалентностьформул

………………………………………………………….

107

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

………………………………….

109

Фактор-алгебраалгебрыформул

…………………………………………………..

109

Контрольныевопросы…………………………………………………………………

Лекция 10 ………………………………………………………………………………….

110

ДИЗЪЮНКТИВНЫЕКОНЪЮНКТИВНОРМАЛЬНЫЕФОРМЫ

110

Определение ………………………….………………………………………….

110

АлгоритмприведенияформулыкДНФ

….…………………………………….

110

СовершенныеСДНФ( )иСКНФ( )

………………………………..

111

ПерваятеорШ маннона

……………….………………………………………

112

Вторая

еоремаШеннона

…………………………………………………………

112

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

……………………………………………………..……….

113

АлгоритмнахожденияСДНФ

……………………………………………………….

113

МинимизабулефунквклассеыхДНФцияй

….………………………………….

114

МетодКвайна

…..………………………………………………………..

115

Контрольныев

опросы…………………………………………………………………

116

Лекция 11 ………………………………………………………………………………….

116

Diskretka.doc20.02.2014

6

ПОЛНЫЕСИСТБУЛЕВЫХФУНКЦИЙМЫ

……………………………….

116

Каноническоепредставленлогичфункцскиехй

……………………………..

116

Системыбулевыхфункци

й

….………………………………………………….

117

Теорема( одвухсистемах ) ………..……………………………………………..

117

БазисЖегалкина

………………..………………………………………………

118

Классыбулевыхфункций

……………………………………………………….

118

Теорема (Пост -Яблонского)

…………………………..………………………….

119

Теорема (Пост) …………………………………………………………………….

120

АлгебраЖегалкина

…………………………….………………………………….

122

Контрольныевопросы…………………………………………………………………

123

Лекция 12 ………………………………………………………………………………….

123

ЛОГИКАВЫСКАЗЫВАНИЙ

……………………………………………………….

123

Определения ………………………….………………………………………….

123

Формулылогикивысказываний

……………………………………………….

125

Порядвыпоперацлненкияй

.……………………………………………..

126

Правилапреобразованияформул

………………………………………

126

Осноравносильностиые

……………..………………………………………

127

Правилопереходакбулевымфункциям

…………………………..……….

128

Нормальнформыформуллогикивысказыванийе

……………………….

129

Заклогикивыскны.Тавтологиизываний

129

.………………………………….

131

Контрольныевопросы…………………………………………………………………

Лекция 13 ………………………………………………………………………………….

131

ЛОГИКА ПРЕДИКАТОВ ……………………………………………………….

131

Определениепредиката

………………………………………………………….

131

Языклогикипредикатов

……….………………………………………………….

132

Логическиеоперациисвязк( )надпр дикатами

………………………….……..

134

Кванторы ………………………………………………….…………………………

138

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

………………………

139

Буалгебраевапредикатов

…………………………………..…………..……….

142

Формулы ……………………..………………………………………………….

143

Алгоритмпреобразовформулнормформуанияльную

…………………….

145

Исчислениепредикатов

…..………………………………………………………

146

Следованиеэквиваленция

………………………………………………………

146

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

………………………………………..

147

Отрицаниявисчислениипредикатов

…………………………………………….

150

Контрольныевопросы…………………………………………………………………

151

Diskretka.doc20.02.2014

7

Цельизадачипредмета

ВВЕДЕНИЕ (2часа)

Даннучебнпопредставляетсобиесобойди

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

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

МосковгосудасткомроитуниверситествнафакульнномльномИСТАСтете

раснастудечитан,обучающихсяпотспециальнв220200Автоматизисти«

рованные

системыобработкиинформацииуправления»кодпо(ОКСО230102)понаправлению

654600Информатикавычислительн« техника»кодпоОКСО( 230100),а апокжея

специальности220100

– Вычислительныемашины,комплексы,сетисистемы.Тематикой

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

математическойлогикитеорииграфов, нтерпретированныенадискретныеобъекты.

Исслед,особенколичественнойваоцие,предусматриваетнкойразработку

адекватныхинформационныхс

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

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

вовсехегопроявленнемыслбезкомпьюи,маяхперсональныхтиероваксуперЭВМ.

Дляэтогонеобходимопострои

тьмодереаобъектовльипроцессовныхихпреобразования

ввидедискретныхконструкций,посколькуименноцифрЭВМовыелучилинаиболее

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

развдискретнватьсяматем. атикая

Какотмечает/60/,висторразвитияц вилизациичеловечестваможновыделить

трипериода:

аграрный,индустриальный

и

информационный.

Аграрный период,

закончившийсяXVII,являлсяосновоположникомэле ентарнойатематикиарифметики( )

количественноописыва

ющейматеприальнедставлением удовлетворявшейсяра

числом.

Индустриальный пери,сXVIIпоXXвекад,потребовалразвитиядрург вняго

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

Информационный

потребовалразвитиявысшей

математики – анализа,введенияфункции.

периодначалсяXXвека,базируетсянаобработкеинформ,потребовалзвитияции

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

Такимобр, зомтекакнаукумоатику

жноразнаделискретнують

непрерывконти( )В.континуаальнуюматематикеяв ьнойеявносод ржится

идтепоярнепрерывностиеделов,применявшаясяешениизадачсплошныхсред.

Сразвфисразвиватикилемкванподходткоповыйься

исаниювещества.Все

осталь,чтонеотконтинуальнойк еситсяматематике

– этодискретнматем,кудатикая

вчастностивходятарифм,алг,темнобтикаробщаяжтеострияображенийв,

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

идр.

Дискретная

математика особенноактивносталараз XXиввеке, основнаятьсяветвьматематики.

Этообъясняетсяследующимипричинами:

•

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

математики;

дискретнматематикая

– этеорети

чесосновакаяомпьютернойматематики;

•

Цельчитаемогокурса

– помочьстудентамовлмат аппаратомтьматическим

синтезаанализадискретныхструктурси( осредоточеннымитемпараметрами

;

процессов,протекающихдискретмомевремени),егосыетыдержанием

- являются

Diskretka.doc20.02.2014

8

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

этизад.Важносчи

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

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

устройслежазнименноядискретнойваматематики,которявляется( н укой21

-го

века,ибееразвития

немыслимыуспехитехническогопрогресса)Поэтому. освоение

элементарныхзнанийвобладисматематкретнойтирасшкругозорстудентаики,

повыситегоматематическультурупоземувкаолиткуюой

-тостепенипониматьработу

вычиуслительныхтройствлучш

еориентивсовмирем.оватьсяДискретнаянном

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

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

Вкласскурсдическийкретной

матемвходяттакжетакиетикиразделы,каккодирование

(необходимоедля

безошибочной передачиинформациинарасстоя,именнопомиещью

кодированияработаютИнтернетэлектроннаяпочта),теориягр фовлгоритмов.Тема

теорииграфовважнатем,чтоона

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

числе сети (сетевойграф).

Втечениеучебногогода

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

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

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

,элементытеоиприикодакт,теориякированияграфов,элементытеории

конечныхавтоматов,машТьюрингасоответствнаучебнопособиекурсал кцийнно

состоизвзаитразделовмосвязанных,раскрывающихвышеутем.Вконцетикузанную

каждойразделаприв

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

практическихлабораторныхзанятиях.

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

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

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

Преддискретнойма ематики

Предмет искретнаяфинитная( ,конечная)математика

– напрматематикивление,

изучающеесвойдисструктуртвакретных,товремякакклассическаянеп(

рерывная)

математикаизучаетсвойствабън пректовхар;вчастностиактераывногоонаявляется

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

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

Вкурсематематианализаизуфунчаескогоются

кции,определённыеначисловой

прямойилинаотрезкечисловойпрямойилинагипер(

-)плоскости..Такилииначе,

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

– непрерывное множе.Вкурседискретнойтвоматематикиизучаются

функции,областьопределениякоторых

– дискретное множество.

Простейшимно(нетривиальным)такиммножествомявляетсямножество,состоящее

издвухэлементов,накотостроитсяалгебралогиким.Здесьжевводитсяпонятиебулевой

функции.

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

ытовой

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

вероятнос, такиеопределетребуютсянеи.Осебенинаполняютдержаниемпо

мереихприменения.

Основныеразделыдискретнойматематики

Логика возниклат

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

рассуждать,чтобыполучитьправильнинтересвывод.Активныйлогикесреди

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

-IVвв.до

н.э.Первбольшоес чинение

,посвященноеспециальнологик

– этоАналитики" "

Аристотеля, (384

- 322гг.дон.э.Параллельно). инезависвознбуддистскаялогикакламо.

ВЕвроперазвитиелогикиначотнаетсязученияАристотеля.Вобычную" "логику

начинаютпроникатьматематические

илогичзнакисцезаменыскиельюсловоб чного

Diskretka.doc20.02.2014

9

живогоязыка.Появилидеятом,что,засьпвсеисхдаводныепущениянаязыке

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

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

нийбылипереведенынаязык

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

допущений.Такуюлогическую" маши"сконеществ рвекаедниеуировалРаймунд

Луллий(1235

-1315)ДалееЛейбниц.(1646

-1716)внесойкладвуниверсал

ьнлогическое

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

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

Началосозданиюаппаратасовреммателогикиматическойнн( ки

выск)заложилзыванийДжорджБуль(1815

-1864)Логико.

-математическиеязыкитеория

ихсмыслабылизатемзначительноразвитыработахФрече(1848

-1925)Применение.

математическойлогивне разделахоторыхматематикипроизвелПеано(1858

-1932)В20 .

-

мвеке – этоработыРасселаиУайтхеда,издан

ныев1910

- 1913гг.ипробоснованияграмма

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

Гильбертом(1862

-1943)Впринципеспрограммы. Гильбертаначинсовременноется

развитиематематическойлогики.Вэтотпериодпрои

сходпритменениемочных

математическформальныхметодовприизученаксиоматическихи теорий/7/.

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

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

точностимысл,

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

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

словоупотреблению.

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

только

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

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

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

Вматематическойлогике

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

яоказываютсяматематический

анализ,алгебра,элемгеометринтарная,арифметдр.Влогикематематкатеорические

изучаютсявцелом

- иэтооднаизособенносматемалогикипосравнениютейической

другимиматематическимидисциплинами.Математическую

еориюописываютнабазе

логико-матемаязыка,ээтотическогоназываетсяп

формализациейтеории

.После

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

матемаизучениюестопонойспроблемытановкойкомуиполучениемматемат

непротиворечивость теории,..невыводится

ических

результат.Такипроблемамимобытьвгут:

ливдантеориинойекотоутвеиегоотрицаниеждение.Так,спомощьюетода

интерпрКэлиКлпоказалиетациййн,чтогеометрияЛобачевскогонепротив,

речива

если

непр,обычнаятиворечиваевклидовагеометрия.Кнастоящемувременинепротиворечивость

такихтеорий,какэлемгеометринтар,арифметика, на,хорошоялизизучена

достнадёжобоснованаточ.

– это полнота теории.Вомногихмат

Следующаяпроблема

ематическихтеориях

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

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

проблемувсёжеудаётсяразрешить.Нов зможнатакаяситу ция

:проблемуневозможно

нидоказать,ниопровергнутьрамкахиссл .МаториидуемойГ доказалматикдель

всякаядостатбогатаяте чнория

теонепрему,котораяутверждаетлноте,что

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

утьв

рамкахтеории.

Нотакиетеории,какэлемгеометринта,теориявекторныхная

пространствоказывполными.Т ютсятарский1948г.построилконкретныйалгоритм,

позввсякомуляющийутверждэлемгеометриинвытарнойию,явснлиэтояетсять

утверждениеистиннымложным.

Метлогикаможнодамидоказать,чтомногиетеории,напри,анализфметикамер,

теориямножеств,

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

Diskretka.doc20.02.2014

10

суждентеорузнавать,истиюоноилнноожнои.В сущестпрос

вованиныхтехили

алгоритмов заниважноеместоаетисслогикойедо.Большоеванияхниманиеуделяется

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

(сложениенатуральныхчисел),являющаясяразре,ориейможетшмой

иметьтолоченько

сложныеразрешающиеалгоритмы.

Вопрпостроениясыптимальсложностиповремениработыых

кибернетике - науке,

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

тесносвязматематическойннойлогикой.

Есликоснуться

ис,томатематическийрииап,пригодныйаратдляописания

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

/7/.

Созданиеалгебры« высказываний»связаноименемДж.Буля(1815

— 1864),хотяиунего

былипредшественники,кото

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

Появившаяся1847г.работаБуляположиначалоисс ,результатомедованиямкоторых

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

математикидвадцвека.Всвоейтого

онографииИсследов« законовмышления, ние

которыхоснованыматематтеорлогикиверческие»отчятностейуказалнатливосвязь

построенногоимисчитакжеоснлениятеорииванвероятностей.Этасвязьми

основываетсяаналогиимеждусобытиями« »

«высказываниями»,позволяющей

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

«событие»

— это,чтомпроизойтижетилинепроизойти;высказывание« »же

— это,

чтомбытьжетисилинноожно.Средисобытийестьдостоверн

ыеиневозможные;

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

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

-следственнаясвязь:однособыиногдаватиет

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

;они

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

высказывание,утверждающ,чтоэтопробыти.Сдругойзошлоесторе,всегдаможноны

истолковатьвыскаутверждениезываниеобосущ которогоствленсобыт. ияи

Сказанноесейчасубеждаетввозмпостржнедисо«ногоенчти»,к слениямтороегло

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

событий»Такое. исчибылосозданоДжение.Булем.

Втечениеполувекаоноразвивалос

ьвчистологическом« »русле.Мерное

значительноеисследовантеориипоаксиоматвероятностейпоявилоськелишь1917г.;

егоавторомбылС.Н.Бернштейн.Последующиеисследосвязанныеявэтойобласти,

первуюочередьсработамиА.Н.Колмогорова,

кончапоставтеориюльноли

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

вособенности - натеориюмеры.

Ви20веках21связиразвитиемкомпьютерныхтехнологийалгебраические

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

тсявовсехобластяхчеловечдеят,томельностиской

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

применениевычислительнойтехникиразлсферахчеловеччныхдеятельностиской

базируютвычисленияна нади кретных

структурах.Разработкакомплексных

интегрированныхавтоматизирсистемобрабинфорихванныхткикомациипонент

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

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

когоанализа.

Дискрматематикаявляетсятнаяоднимизосновныхдлядальнейшегоизучения

практическогорешениязадач,встречающихсяприпроизвЛогика. ительствадстве

применениядискретнойматематисводитсявданномслучаекследующ.Требуемутся

четкоилаконичноописатьреальнуюситуацию,имеющуюместоприпроизводстве

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

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

решения алгебраичзадачипробравеспереводкойтиный

–

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

техническийязык.