Diskretna matematika i algoritmi

Ана Савић

Светлана Штрбац

-

Савић

Амела Зековић

Д И С К Р Е Т Н А

М А Т Е М А Т И К А

И

А Л Г О Р И Т М И

друго

издање

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

струковних студија

Београд, 2012

. 

Аутори:

Др Ана Савић

, 

мр Светлана Штрбац

–

Савић, дипл. инж. Амела Зековић

Дискретна математика

и алгоритми

Рецензенти

: 

Др Слободан Обрадовић

, 

доцент,

Факултет за рачунарске науке

у 

Београду

Мр Зоран Мишковић, предавач

, 

Висока школа

електротехнике и 

рачунарства

струковних студија

у Београду

Издавач

: 

Висока школа

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

струковних студија

Београд, Војводе Степе 283

Техничка обрада

: 

Др Ана Савић, дипл. инж. Амела Зековић

Корице

: 

Струк. инж. Ненад Толић

Слике

: 

Струк. инж. Мирко Ступар

Тираж:

 15 

Штампа:

МСТ Гајић

Наставно  веће  Високе

школе

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

струковних студија у Београду одобрило је коришћење овог уџбеника

у 

настави.

Забрањено прештампавање и копирање. Сва права задржава издавач.

П Р Е Д Г О В О Р

Овај уџбеник написан је

за студенте прве године Високе школе 

електротехнике 

и 

рачунарства 

у 

Београду 

који 

слушају 

једносеместрални  курс  из  предмета  Дискретна  математика  и 
алгоритми

. 

Прилагођен  је  плану  и  програму  предмета  Дискретна 

математика и алгоритми

и подељен је у 

15 

поглавља.

Планирано је да 

се свако поглавље обради  у току  једне радне  недеље. Свако поглавље 
садржи  циљеве  учења,  теоријски  део,  употпуњен  примерима  као  и 
питања  и  задатке  за  проверу  знања  на  крају  сваког  поглавља,  што  је 
стандард у савременој литератури.

Аутори  позивају  све  читаоце  и  кориснике  да  дају  своје 

сугестије, да би наредна издања била још квалитетнија и садржајнија.

У Београду

,   

Аутори

17. 03. 2012. 

Садржај

Увод

1 

Језик математике

2 

1.

Основни појмови математичке логике

3 

1.1.

Логика

3 

1.2.

Математичка логика

4 

1.2.1.

Искази

5 

1.3.

Основне логичке операције

6 

1.4.

Приоритет логичких операција

12 

1.5.

Превод језичких реченица

12 

1.6.

T

аутологије и логички закони 

13 

2.

Примена математичке логике у рачунарству и техници

19 

2.1.

Дигитална и логичка кола

20 

3.

Основни појмови теорије скупова

29 

3.1.

Појам скупа

29 

3.2.

Операције са скуповима

31 

3.3.

Број елемената скупа

 - 

кардинални број

35 

3.4.

Раселов парадокс

37 

4.

Релације

43 

5.

Функције

48 

5.1.

Начини задавања функција

50 

5.2.

Реалне функције једне променљиве

51 

5.3.

Инверзна функција

51 

5.4.

Слагање функција

52 

6.

Основе

комбинаторике

54 

6.1.

Принципи пребројавања

54 

6.2.

Пермутације без понављања

55 

6.3.

Пермутације са понављањем

57 

6.4.

Варијације без понављања

57 

6.5.

Варијације са понављањем

58 

6.6.

Комбинације без понављања

59 

6.7.

Комбинације

са

понављањем

60 

7.

Биномна

формула

67 

8.

Теорија

графова

73 

8.1.

Основни појмови

74 

9.

Представљање графова помоћу рачунара

82 

9.1.

Шетње по графу

82 

9.2.

Матрица суседства

82 

9.3.

Матрице инциденције

85 

10.

Стабла

88 

10.1.

Бинарна стабла претраге

93 

11.

Теорија алгоритама

108 

11.1.

Алгоритми

108 

11.2.

Дијаграм

- 

блок шема

110 

11.3.

Врсте алгоритамских шема

111 

11.3.1.

Линијске алгоритамске шеме

112 

11.3.2.

Цикличне алгоритамске шеме

114 

11.4.

Особине алгоритама

117 

11.5.

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

117 

12.

Математичка дефиниција алгоритма

122 

12.1.

Рекурзивне функције и алгоритми

123 

12.2.

Рекурзивни алгоритми

125 

12.3.

Черчова теза

127 

12.4.

Тјурингова машина

128 

13.

Теорија сложености 

a

лгоритама

133 

13.1.

Проблеми одлуке

134 

13.2.

Рачунски ресурси

134 

13.3.

Неукротивост

135 

13.4.

Особине алгоритама

135 

13.5.

Претраживање

136 

13.6.

Секвенцијално претраживање

137 

13.7.

Оптимизације секвенцијалног претраживања

139 

13.8.

Секвенцијално претраживање у уређеним табелама

140 

13.9.

Бинарно претраживање

141 

13.10.

Претраживање коришћењем бинарног стабла

143 

13.11.

Основне операције бинарног стабла 

145 

13.12.

Авл стабла

157 

13.13.

Црвено 

– 

црна стабла

160 

14.

Графовски алгоритми

162 

14.1.

Алгоритми 

- 

разапињућа стабла

162 

14.2.

Алгоритми 

- 

претрага у дубину

163 

14.3.

Алгоритам 

- 

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

164 

14.4.

Алгоритми 

- 

претрага у ширину

167 

14.5.

Алгоритам 

- 

стабло претраге у ширину

168 

14.6.

Дајкастрин алгоритам

171 

15.

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

185 

15.1.

Основни појмови

185 

15.2.

Докази и аксиоме

187 

15.3.

Основне теореме

188 

15.4.

Бинарна булова алгебра

188 

15.5.

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

189 

15.6.

Дисјунктивне и конјуктивне форме

189 

2 

Ц И Љ   П Р Е Д М Е Т А

Основни циљеви су

: 



развијање способности

логичког размишљања,



развијање

логички исправне форме закључивања,



савладавање

основне технике доказивања,



савладавање рада

са симболичким изразима, 



савладавање рада

са дискретним структурама,



упознавање

са основним техникама пребројавања, 



схватање

конструкција алгоритма, 



савладавање теорије

графова,



развијање способности

коришћења математичке

аргументације

, 



уочавање

како резултате дискретне математике је могуће 

користити у њеним применама.

Ј Е ЗИК   МАТ Е МАТ ИК Е

Поред

говорног

језика

у

математици

се

користе

разни

математички

знаци

-

симболи

који

чине

језик

математике

. 

Тај

језик

је

универзалан

и

омогућава

једноставно

и

свима

разумљиво

записивање

математичких

садржаја

. 

Језик

математике садржи:



константе

:

1

1, 3, , , 2,

2









променљиве

: 

, , , , , ,

x y a b

 





операцијске

знакове

: 

алгебарске операције: 

, , , /

  

; 

логичке операције: 

, ,

,

,

    

; 

скуповне операције: 

, , , ,



 



. 



релацијске

знакове

: 

, , , , ,

   



. 



специјалне

знакове

:

 

 

 

, , , , , , , ,!,

 



Коришћењем ових елемената математичког језика

дефинишемо

изразе

и

формуле

. 



Изрази

садрже

константе

, 

променљиве

и

операцијске

знаке.

Пример

:

3

x



је

израз

. 

Изрази

у

обичном

језику

представљају 

речи

. 



Формуле

су изрази који морају да садрже релацијски знак.

Пример

:

3

7

x

 

је

формула

. 

Формуле

су

у

обичном

језику

реченице

. 

3

1 .

О С Н О В Н И

П О Ј М О В И

М А Т Е М А Т И Ч К Е

Л О Г И К Е

Ц И Љ Е В И

У Ч Е Њ А

Када

савладате ово

поглавље

требало

би

да

знате

: 

1.

дефиницију

исказа

, 

2.

дефиниције

логичких

операција

, 

3.

приоритете

логичких

операција

, 

4.

шта

су

таутологије

, 

а

шта

контрадикције

, 

5.

основне

логичке

законе

. 

1 . 1 .

Л О Г И К А

Логика

је

вештина

и

метода

правилног

мишљења

. 

Логика

је

наука

о

закључивању

и

као

таква

користи

се

у

најразличитијим

областима

науке

, 

а

поготово

у

математици

. 

Основа

је

целокупног

математичког

резоновања

. 

Настала

је

у

  4. 

веку

п

.

н

.

е

. 

На

основу

основних

ставова

, 

које

називамо

аксиомама

, 

одређује

се

који

су

математички

искази

тачни

, 

а

који

не

, 

и

формализују

се

поступци

добијања

сложених

реченица

из

простих

у

складу

са

правилима

исправног

закључивања

. 

5

1 . 2 . 1 .

И С К А З И



Реченице

које

имају

тачно

одређену

истинитосну

вредност

T

или



називају

се

искази

. 

Значи

T

, 

тзв

. 

истинитосне

вредности

су

, 

у

ствари

, 

замене

редом

ових

речи

: 

тачан

  (

истинит

), 

нетачан

  (

неистинит

, 

лажан

).

Обично

се

записом

 

p



означава

истинитосна

вредност

реченице

p

. 

Рецимо





2 2

4

T



 



, 

   





2

3

6





 

 



и

сл

. 

Реченице

које

имају

тачно

одређену

истинитосну

вредност

T

или



као

што

је

случај

са

реченицама

, 

односно

формулама

  2 2

4





, 

   

2

3

6



 

 

називају

се

искази

.

Формуле

су

уопште

математички

записи

који

прочитани

обичним

речима

дају

реченицу

природног

језика

. 

Тако

, 

запис

5

x



и

сл

. 

јесте

пример

формуле

, 

док

запис

као

6 7 2

 

то

није

 (

он

је

пример

израза

). 

Наравно

, 

има

и

реченица

, 

односно

формула

које

нису

искази

. 

Такав

је

, 

на

пример

, 

случај

са

формулама





1 3,

1, 2, 3 ,

4

x

x

x

x

 



 

где

слово

x

служи

као

заједничка

ознака

  (

каже

се

и

променљива

) 

за

реалне

бројеве

. 

У

овом

случају

за

разне

вредности

променљиве

x

из

датих

формула

настају

посебне

формуле

и

свака

тако

добијена

формула

јесте

исказ

, 

односно

тачна

је

или

нетачна

. 

Тако

, 

за

2

x



добијамо

ове

исказе





2 1 3, 2

1, 2, 3 , 2

4 2

 



 

чије

истинитосне

вредности

су

по

реду

T

, 

T

, 



. 

Друкчије

се

каже

да

 2 

јесте

решење

прве

две

формуле

, 

а

није

решење

последње

. 

Променљива

је

уопште

неко

слово

као

  , ,

x y



које

договорно

служи

као

заједничка

ознака

за

чланове

неког

скупа

. 

Некад

се

уместо

је

променљива

за

реалне

бројеве

говорило

је

општи

број

. 



Истинитосна

вредност

исказа

је

 

T,

је

тачан

исказ,

,

je

нетачан

исказ.

p

p

p





 





Напомена

: 

Уместо

T

и



користе

се

и

ознаке

  1 

и

  0 . 

У

овом

случају

симболе

 1 

и

  0  

не

треба

схватати

као

бројеве

 1 

и

  0 . 

6

Пример

:

Реченица

: 5 3

8

p

 

је

исказ

и

има

тачну

истинитосну

вредност

, 

тј

. 

 

p





T

. 

Пример

:

Реченица

: 5 3

8

q

  

је

исказ

и

има

нетачну

истинитосну

вредност

, 

тј

. 

 

q





.

Пример

: 

Реченица

2

4

x



није

исказ

јер

нема

дефинисану

истинитосну

вредност

. 

За

неке

вредности

променљиве

x

, 

тј

за

2

x

 

формула

је

тачна

, 

а

за

све

остале

је

нетачна

. 

1 . 3 .

О С Н О В Н Е

Л О Г И Ч К Е

О П Е Р А Ц И Ј Е

У

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

језику

, 

реченице

се

комбинују

у

сложене

реченице

, 

коришењем

везника

и

,

или

, 

не

,

ако

онда

и

многих

других

. 

Истинитосна

вредност

сложене

реченице

условљена

је

истинитошћу

њених

делова

.  

Пример

:

:

p

Данас

сија сунце.

:

q

Данас

је

22. јул 2010

. 

Сложена

реченица

гласи

Данас

сија сунце

и

данас

је

22. јул

 2010. 

Састоји

се

од

два

дела

спојених

везником

и

. 

Симболички

се

може

написати

и

p

q

, 

или

коришћењем

ознаке

за

логичку

операцију

и

, 



, 

у

облику

p

q



. 

Основне

логичке

операције

су

:  



конјункција

 (

и

), 

у

ознаци



, 



дисјункција

 (

или

), 

у

ознаци



, 



импликација

(

ако

 - 

онда

), 

у ознаци 



, 



еквиваленција

 (

ако

и

смо

ако

), 

у ознаци



, 



негација

(

не

), 

у ознаци 



. 

Напомена

: 

Разликујемо 

унарне

и 

бинарне

логичке  операције. 

Негација је унарна операција.

8

Истинитосна таблица импликације

 

p



 

q







p

q





T

T

T

T







T

T





T

је нешто замршеније и изискује прилично допунског објашњења и 
„одбране“.  Најнеобичније  су  трећа  и  четврта  врста  те  таблице. 
Зашто се узима, рецимо да 

Ако 

 

p







, 

 

q





T

, 

онда





p

q







T

; као и:

Ако 

 

p







, 

 

q







, 

онда





p

q







T

.

Нека је 

p

, на пример, реченица: 

Србија је највећа на свету

, која је 

нетачна.

Тада, обе следеће реченице

Ако је Србија највећа на свету, онда је она већа од Француске.

Ако је Србија највећа на свету, онда је она већа од Црне Горе.

су тачне!

Код прве је присутан случај 



је 

T

, а код друге 



T

је 

T

. 

Пазите,  првом  се  реченицом никако  не тврди да  је  Србија  већа

од 

Француске, већ једино условно каже: кад би Србија била највећа на 
свету, била би већа од Француске.

Постоје и разни обични математички примери који „бране“ таблицу 
импликације. Уочимо, рецимо формулу

3

2

x

x

 



 (

x

је природан број)

Која је тачна.

Замењујући  место 

x

редом  1,  2,  3,  4,  5,  ...  добијамо  ове  посебне 

формуле

1

3

1

2

  

,  2

3

2

2

 



,  3

3

3

2

  

,  4

3

4

2

 



, ... 

9

Које  би  требало  прихватити  као  тачне.  Међутим,  управо  у  тим 
формулама  су  присутни  наведени  необични  случајеви  тачности 
импликације. Прве две  формуле су  у вези са случајем 



је 

T

, 

трећа  је  у  вези  са  случајем 



T

је 

T

,  а  остале  су  у  вези  са 

„природним“ случајем 

T



T

је 

T

. 

Према истинитосној таблици импликације, она  је нетачна  једино  у 
једном  случају:  када  је 

p

тачна,  а 

q

нетачна  реченица.  У  свим 

осталим  случајевима  је  импликавија  тачна.  Случајеви 



је 

T

, 



T

је 

T

се обично, ради лакшег памћења, описују овим речима: 

Из  лажи  произилази  све

,  а  случајеви 

T



T

је 

T

, 

 

T

је 

T

речима: 

Истина произилази из било чега

. 

Импликација се може читати

на следеће начине:

ако 

p

, онда 

q

, 

p

је претпоставка последице 

q

, 

p

повлачи

q

, 

из 

p

следи 

q

, 

p

је довољан услов за 

q

. 

q

је потребан услов за 

p

. 

За импликацију

, 

p

q



, 

везане су три

додатне врсте исказа:

конверзија

q

p



,

инверзија

p

q

  

, 

контрапозиција

q

p

  

. 

Пример: 

Ако је он

тенисер, онда је он

популаран

. (

импликација

) 

Ако је он

популаран, онда је он

тенисер

. (

конверзија

) 

Ако он

није тенисер, онда он

није популаран.

(

инверзија

) 

Ако он

није популаран, онда он

није тенисер

. (

контрапозиција

)

Водећи рачуна о томе да је еквиваленција 

p

q



, у ствари, двојна 

импликација 

p

q

q

p



 

,  лако  се  гради  истинитосна  таблица 

еквиваленције. Она изгледа овако:

11

Пример  1.

Решити  дату  формулу,  односно  наћи  све  вредности 

одговарајућих  променљивих  за  које  је  истинитосна  вредност 
формуле једнака 

T

: 

а)

  3

5 10

x

 

(где 

x



), 

б)

6

x

(где 

x



), 

в)

9

x

x



 

, 

г)

3

5

x

x

x

    

,  

д)





1

5

.

x

x

x

 



 

Пример 2.

Зашто је празан скуп подскуп било ког скупа?

Пример

 3.

Решити

формулу 





2

4

2

x

x



 



, где 

x



. 

Дефиниција

: Знаке 

1

1

1

1

, , , ,

,

, ,

,

,

,

,

,

,

n

n

n

n

p q r s p q r s

p q r s





назовимо, договорно,

исказна слова. 

Тада се исказне формуле уводе на следећи начин:

 
(1)

Свако исказно слово је исказна формула.

(2)

Ако  су 

A

, 

B

исказне  формуле,  онда  и  речи 





A

B



, 





A

B



, 





A

B



, 





A

B



, 

A



су исказне формуле.

(3)

Исказне  формуле  су  једино  оне  речи  које  се  могу  добити 
примењивањем коначно пута правила (1), (2).

Пример  4

.

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

исказна формула



 





 



3

2

,

,

,

,

,

.

r

s

p

q

r r

s

p

q

p

q







 







Напомена

.

Обично  се  и  у  случају  исказних  формула,  ради  краткоће, 

изостављају  неке  заграде.  Један  такав  договор  се  односи  на 
изостављање спољних заграда, па се, рецимо формуле 





r

s



, 





p

q



, 





p

q



, 









p

q

r





означавају  краће  овако: 

r

s



, 

p

q



, 

p

q



, 





p

q

r





. 

Пример 5. 









,

,

p

q

p p

q

r

p p

q





 





су формуле.

12

1 . 3 . 1 .

П Р И О Р И Т Е Т

Л О Г И Ч К И Х

О П Е Р А Ц И Ј А

Комбиновањем

исказних

слова

и

логичких

оператора

добијамо

сложене

изразе

, 

као

што

су

на 

пример 

p

q

p



 

, 





p

q

p

r



  

. 

Приликом

одређивања

истинитосне

вредности

ових

израза

важно

је

знати

приоритет

логичких

операција

. 

Наводимо таблицу приоритета логичких операција

. 

логички

оператор

приоритет



1 

,

 

2 

,

 

3 

1 . 3 . 2 .

П Р Е В О Д

Ј Е З И Ч К И Х

Р Е Ч Е Н И Ц А

Превод

садржаја

из

обичног

језика

у

запис

математичке

логике

је

један

од

најважнијих

проблема

хардверских

и

софтверских

послова

. 

Проблем

се

своди

да

се

садржај

обичног

језика

сведе

на

тачан

и

недвосмислен

логички

запис

који

може

да

буде

предмет

даљег

проучавања

. 

Пример

:  

Аутоматски

, 

одговор

не

може

бити

послат

ако

је

унутрашња

меморија

пуна

 . 

Нека

је

реченица

p

: 

Одговор

се

аутоматски

шаље

. 

Нека

је

реченица

q

: 

Унутрашња

меморија

је

пуна

. 

Онда

p



је

реченица

: 

Одговор

се

не

шаље

аутоматски

. 

Логички

запис

би

био

q

p

 

. 

14

З А Д А Ц И

И   П И Т А Њ А   З А

П Р О В Е Р У   З Н А Њ А

1.

Шта је исказ?

2.

Навести основне логичке операције.

3.

Шта је таутологија?

4.

Невести основне логичке законе.

5.

Испитати да

ли

су

дате реченице

искази

: 

а

)

1

1

7

4



,   

б

) 

2

2

2

x

y

xy





, 

в

) 





2

2

2



 

,   

г

) 

2

x

y



. 

Решење

: 

а

) 

да

,  

б

) 

да

, 

в

) 

да

, 

г

) 

не

. 

6.

Одредити

истинитосну

вредност

следећих

исказа

: 

а

)

1

1

7

4



,   

б

) 

2

2

2

x

y

xy





, 

в

) 





2

2

2



 

,   

г

) 



 



1 3

3

5







. 

Решење

: 

а

)

1

1

7

4



















, 

б

)





2

2

2

x

y

xy









T

, 

в

)









2

2

2





 



, 

г

)



 







1 3

3

5











T



T



T

. 

7.

Дати

су

искази

: 

1

1

1

1

10

:

2

3

4

5

3

p



 













 





 



, 

1

1

1

1

37

:

2

3

4

5

6

q











 









,  

1

1

1

1

:

7

2

3

4

5

r





















,     

1

1 1

1

2

:

2

3 4

5

5

s









. 

15

Одредити

њихову

тачност

и

на

основу

тога

одредити

истинитосну

вредност

следећих

изказа

: 

а

)





p

q

r





,  

б

)



 



p

q

r

s







, 

в

)









p

q

r

s





 

,     

г

)









p

q

r

s

 





. 

Решење

: 

Како

је

 

p





T

, 

 

q





T

, 

 

r





, 

 

s





, 

а

)









p

q

r









(

T



T

)

 

T

 

T

, 

б

)



 







p

q

r

s











 (

T



T

)





    

T

 

T

, 

в

)













p

q

r

s







 



, 

г

)













p

q

r

s



 







. 

8.

Дати

су

искази

: 



 



3

5

4

3

2

2

3

4

: 2

2

p

x y

x y

x y





 ,    



 



2

2

4

2

6

4

3

: 3

3

q

x y

x y

xy





, 







2

2

2

2

4

r

x

y

x

y

x

y











,    





2

2

2

2

4

4

s

x

y

x

xy

y











. 

Одредити

њихову

тачност

и

на

основу

тога

одредити

истинитосну

вредност

следећих

изказа

: 

а

)





p

q

r





,  

б

)



 



p

q

r

s







,  

в

)









p

q

r

s





 

,     

г

)









p

q

r

s

 





. 

Решење

: 

Како

је

 

 

 

,

,

p

q

r













T

, 

 

s





, 

а

)









p

q

r









T

, 

б

)



 







p

q

r

s











, 

в

)













p

q

r

s







 



T

, 

г

)













p

q

r

s



 







. 

9.

Написати

на више начина

импликацију

2

0

x

x

  



. 

17

б

) 









p

q

p

q





   

је

таутологија

, 

в

) 





p

q

p



 

је

таутологија

, 

г

)





p

p

p





је

таутологија

, 

д

)







 



p

q

r

p

r

q

r



 







. 

Нека је 





M

p

q

r







, 



 



N

p

r

q

r









и







 



F

p

q

r

p

r

q

r





 







. 

 

p



 

q



 

r







p

q





 

M







p

r









q

r





 

N



 

F



T

T

T

T

T

T

T

T

T

T

T



T



T

T

T



T



T

T

T

T

T

T

T

T





T



T









T

T

T

T

T

T

T

T



T



T





T









T





T

T

T





















Формула







 



p

q

r

p

r

q

r



 







није

таутологија

. 

12.

Доказати

да

су

следеће

формуле

таутологије

а

)









p

q

q

p







закон

комутације

, 

б

)









p

q

p

q





   

Де

Морганов

закон

, 

в

) 





p

p

p





закон

иденпотенције

, 

г

)

p

p

 

закон

двојне

негације

, 

д

)



 







p

q

p

r

p

q

r













закон

дистрибуције

. 

18

13.

Методом

свођења

на

противречност

испитати

да

ли

је

следећа

формула

таутологија









p

q

p

p







. 

Решење

:  

Ако

посматрана

формула

не

би

била

таутологија

, 

морало

би

бити

, 

за

неке

вредности

p

и

q

који

се

појављују

у

овој

формулу

да

је













p

q

p

p











. 

То

се

може

десити

у

случају

да

је

















p

q

p

T

и

 

p





. 

На

основу

тога

добијамо

да

је













 

p

q

T

, 

односно





p

q







. 

Овај

израз

може

бити

нетачан

само

у

једном

случају

, 

а

то

је

када

је

 





p

T

и

 

q





. 

Како

смо

већ

претпоставили

да

је

 

p





, 

долазимо

до

контрадикције

. 

Значи

не

можемо

наћи

вредности

израза

p

и 

q

за

које

је

полазна

формула

нетачна

. 

Према

томе

полазна

формула

мора

бити

таутологија

. 

14.

Методом

свођења

на

противречност

испитати

да

ли

су

следеће

формуле

таутологија.

а

)





p

p

q





, 

б

)









p

q

p

p







, 

в

)

















p

r

p

q

r

r











, 

г

)









p

q

p

q



  

, 

д

)









p

q

p

p

q







 

. 

К Љ У Ч Н Е   Р Е Ч И

Исказ

Конјункција

Дисјункција

Импликација

Еквиваленција

Негација

Таутологија

Контрадикција

20 

Рачунари  морају  имати  могућности  да  меморишу  и  обрађују  и 

ненумеричке,  односно  текстуалне  податке.  Они  су  или 

низови

(

string

)  или 

знакови

  (

charácter  data

), 

затим

слова

,

знакови

интерпункције

, 

математички

знаци

, 

специјални

знаци

и слично.

Подаци  овог  типа  су  меморисан  у  облику  низа  битова.  Данас  се 
користе  ASCII  и  EBCDIS  код.  На  пример  1111001  представља 
слово б. 

Дакле, бинарни бројеви су основа за функционисање рачунара. 

Дигитална

кола

комбинују

нуле

и

јединице

, 

и

генеришу

нове

нуле

и

јединице

. 

Машинске

инструкције

су

такође

приказане

као

низови

нула

и

јединица

. 

Сви  програми  написани  у  асемблеру  или  неком 

вишем  програмском  језику

да  би  могли  да  раде  морају  бити

преведени у низове нула и јединица.

2 . 1 .

Д И Г И Т А Л Н А   И   Л О Г И Ч К А   К О Л А

Клод

Елвуд

Шенон

  (

Claude  Elwood  Shannon

,  1916.  –  2001) 

био

је

амерички

научник

и

инжењер

. 

Међу

најзначајнија

открића

овог

научника

спадају

теорија

информација

и

дизајн

дигиталних

рачунара

и

кола

. 

1938.  године  открио  је  везу  између  таблица  истинитости  и 

електричних  кола.

Шенон

је

познат

као

утемељивач

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

теорије

са

својим

научним

радом

објављеним

  1948. 

године

. 

Такође

се

сматра

утемељивачем

теорије

дигиталног

рачунара

и

теорије

дизајна

дигиталних

кола

, 

када

је

као

 21-

годишњи

студент

МIТ

-

а

, 

написао

тезу

где

доказује

да

је

примјеном

Булове

алгебре

на

дигитална

електрична

кола

, 

могуће

решити

било

који

логички

или

нумерички

проблем

.  

21 

Дигитална

кола

су

тако

пројектована

да

имплементирају

принципе

бинарне

аритметике

и

математичке

логике

.  



Исказне формуле у којима се појављују само операције 

, ,

  

, 

при

чему



се  односи  само

на

исказна

слова

, 

имају

једну

занимљиву

интерпретацију

која

се

користи

у

техници,  у 

пројектовању дигиталних кола

и

назива

прекидачка

алгебра

. 



Исказна

слова

се

третирају

као

нормално

отворени

прекидачи

,

а

њихова

негација

као

нормално

затворени

прекидачи

.

Ако

исказно

слово

има

вредност

1

p



сматра

се

да

је

прекидач

затворен

, 

тј

. 

да

проводи

струју

, 

а

за

0

p



је  отворен,  тј.  да  не 

проводи струју.

Формула

се

третира

као

мрежа

са

два

краја

састављена

од

прекидача

који

су

повезани

паралелно

или

серијски

. 

Таутологијама

одговарају

мреже

које

увек

проводе

струју

. 

Пример

:  

Посматрајмо

прекидачко

коло

које

садржи

прекидач

и

сијалицу

. 

Вредност

  1 

додељујемо

прекидачима

p

и 

q

када  су  затворени,  тј 

ако кроз њих протиче струја. У супротном додељујемо им вредност 
0. Када су прекидачи редно везани, сијалица ће светлети и коло ће 
имати  вредност  1  само  ако  су  оба  прекидача 

p

и 

q

затворена. 

Према томе, ово коло ће одговарати исказу 

p

и 

q

, односно 

p

q



и 

зове се 

А

ND –

и

коло

. 

23 

Коло са једним прекидачем 

p

,  у коме сијалица светли

само ако је 

прекидач  отворен.  Према  томе  коло  ће

имати  вредност  1  ако  је 

прекидача 

p

затворен,  односно  ако  је 

p

једако  0.  Такво  коло 

назива се

не

коло

или 

инвертор

. 

p



Елементи дигиталних логичких кола осим стандардних наведених 

(

и

коло

, 

или

коло

и 

не

коло

) су и следећа кола:

ни

коло

, одговара логичком изразу 





p

q





. 

нили коло

, 

одговара логичком изразу 





p

q





. 

ексклузивно

или

одговара логичком изразу 

p

q



. 

24 

З А Д А Ц И

И   П И Т А Њ А   З А   П Р О В Е Р У   З Н А Њ А

1.

Шта је прекидачка алгебра?

2.

Зашто

се користи

бинарни систем?

3.

Шта је бит?

4.

Формули 



 



p

q

p

r







одредити:

а

) 

прекидачку шему,

б

)

дигитално логичко коло.

Решење

:  

а

) 

б

) 

9.

Формули





p

q

r



 

одредити

: 

а

) 

прекидачку шему,

б

)

дигитално логичко коло.

Решење

:  

26 

а

)  

б

) 

в)

27 

Решење

: 

а

)



 







p

q

r

p

q







 

12.

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

шеме

које

одговарају следећим дигиталним електричним колима:

а

) 

б

)

Решење

: 

а

) 





p

q

r

 



. 

29 

3 .

О С Н О В Н И   П О Ј М О В И  

Т Е О Р И Ј Е   С К У П О В А

Ц И Љ Е В И

У Ч Е Њ А

Када

ово поглавље проучите требало би

да

: 

1.

знате дефиниције

основних

скуповних

релација

, 

2.

знате дефиниције

основних

скуповних

операција

, 

3.

знате

шта

је

кардинални

број

скупа

, 

4.

знате шта је

Раселов парадокс.

3 . 1 .

П О Ј А М   С К У П А

Са скуповима радимо свакодневно у различитим приликама. Корпа 
јабука,  стадо  оваца,  скуп  континената,  популација  бактерија,  скуп 
тачака  на  кружници,  скуп  природних  бројева,  све  су  то  примери 
скупова. Скоро свака делатност човека односи се на неке скупове.

Одлучујући корак  у синтетизовању математичких знања  је

теорија 

скупова, односно теорија бесконачних скупова

, 

чији

је творац

Џорџ

Кантор  (

Georg  Kantor

  1845.-1918.

).  Настала  је  као  резултат 

изградње строге теорије реалних бројева. Кантор је први у историји 
математике 

прихватио 

појам 

бесконачног 

без 

икаквих 

тајанствености.



Скуп

је

основни

појам

који

се

не

дефинише

. 

Чине

га

елементи

који

имају

бар

једно

заједничко

својство

. 



Објекти скупа називају се његовим 

елементима

.



Скупови се обележавају

најчешће великим словима 

A

, 

B

, 

C

, ... 

а његови елементи малим словима 

a

, 

b

, 

c

, ... 



Неки  елемент 

a

може  припадати

датом  скупу 

A

,  што  се 

означава  са 

a

A



,  или  не  припадати  истом  скупу,  што  се 

означава са 

a

A



. 

30 



Скуп који нема елемената назива се 

празан

скуп

и обележава са 



. 



За  графичко

представљање  скупова  користе  се 

Венови

дијаграми

.



Кажемо  да  је 

A

подскуп

скупа 

B

и  пишемо 

A

B



,  ако  сваки 

елемент

скупа 

A

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

B

.  





A

B

x x

A

x

B







 

. 



Два  скупа 

A

и 

B

су 

једнака

,  ако  сваки  елемент  скупа 

A

припада  и  скупу 

B

и  ако  сваки  елемент  скупа 

B

истовремено 

припада и скупу

A

. 





A

B

x x

A

x

B







 

. 

32 



Пресек

скупова 

A

и 

B

је скуп 





A

B

x x

A

x

B





 



. 

Пример

:

 

1, 2

A



, 





2, 3, 6, 7

B



; 

 

2

A

B





. 



Ако је пресек два скупа 

A

и 

B

празан, тј.

A

B

 



, тада за 

та 

два скупа кажемо да су 

дисјунктни

.



Ако  је  дато  коначно  много  скупова 

1

2

,

,

,

n

A A

A



њихов  пресек 

је:

1

2

1

n

i

n

i

A

A

A

A











. 



Разлика

скупова 

A

и 

B

је скуп 





A B

x x

A

x

B





 

. 

33 

Пример

:

 

1, 2

A



, 





2, 3, 6, 7

B



; 

 

1

A B



,





3, 6, 7

B A



. 



Симетрична

разлика

скупова

  A

и 

B

је унија скупова 

A B

и 

B A

, тј.



 



A B

A B

B A





. 



Комплемент

скупа 

A

у  односу  на  скуп 

B

(или  допуна  скупа 

A

до скупа 

B

) где је 

A

B



је скуп 

B

C A

B A



. 



Пар  елемената 

( , )

a b

називамо 

уређеним

паром

(или  уређеном 

двојком) ако је тачно одређено који је елемент на првом, а који 
на другом месту.



Уређени парови 

( , )

a b

и 

( , )

c d

су једнаки ако и само ако је 

a

c



и 

b

d



. 



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

скупова 

A

и 

B

назива  се  скуп 





( , )

A B

a b a

A

b

B











. 

Пример:

Дати су скупови 





1, 2, 3

A



и 





,

B

x y



. 





(1, ), (2, ), (3, ), (1, ), (2, ), (3, ) ,

A B

x

x

x

y

y

y









( ,1), ( , 2), ( , 3), ( ,1), ( , 2), ( , 3)

B A

x

x

x

y

y

y





. 

Очигледно  је 

A B

B A







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

скупова не важи закон комутације.

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

A A



се  означава  са 

2

A

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

2





представља реалну раван.

n

A A

A

A

 







и 

n











. 

35 

3 . 3 .

Б Р О Ј   Е Л Е М Е Н А Т А   С К У П А

  -  

К А Р Д И Н А Л Н И   Б Р О Ј

Одређивање  броја  елемената  коначних  скупова  своди  се  на  њихово 
пребројавање . Међутим, када се ради о бесконачним скуповима ,ствар 
је  много  сложенија.  Тада  се  срећемо  са  доста  неочекиваним 
ситуацијама.



Ако постоји „1

-

1“ и „на“ пресликавање 

f

скупа 

A

на скуп 

B

, 

(

бијекција) онда се за скупове 

A

и 

B

каже да су еквивалентни.



Еквивалентни  скупови 

A

и 

B

имају  исти 

кардинални

број

, 

у

ознаци

 

 

k A

k B



. 



Код

коначних

скупова

кардинални

број

представља

број 

елемената скупа.

Пример:

Еуклидова

аксиома

каже

: 

Целина

је

већа

од

дела

. 

Кардинални

број

скупа

природних

бројева

једнак

је

кардиналном

броју

скупа

свих

парних

природних

бројева

. 

Та

једнакост

се

види

из

пресликавања

1

2

3

4

2 1 2 2

2 3 2 4

2

n

n





























Дакле 

 





2

k

k



. 

Још  1638  године  Галилеј  је  сматрао  да  се

овде

ради  о  парадоксу. 

Интиутивно  се  чини

да

је

скуп  природних  бројева  има  више 

елемената него скуп парних природних бројева. 

Канторова

теорија  показује  да  се  бесконачни  скупови  могу 

упоређивати. Скупови 

и 

2

су еквивалентни, али скупови 

и 

нису.

36 

Кардинални  број  скупа 

је  већи  од  кардиналног  броја  скупа 

, 

значи  можемо  рећи  да  је  неки  бесконачни  скуп  „бесконачнији“  од 
другог.

Пример:

Скуп

свих

тачака

праве

еквивалентан

је

са

скупом

тачака

равни

. 

Скуп

свих

реалних

бројева

између 0 и 1 има већи кардинални број 

од скупа свих рационалних бројева 

. 

Пример:

Кардинални

број

празног

скупа

је 0, и пишемо 

 

0

k

 

. 



Кардинални  број  скупа  природних  бројева  означава  се 
хебрејским словом 



и чита се 

алеф

, 

са

индексом

 0 

 

0

k

 

. 

38 

Јасно  је  зашто  је  ова  теорија  на  почетку  свога  настанка  имала 
велики  број  противника.

Међутим

, 

почетком

овог

века

када

је

теорија