Графтар теориясының элементтері

 
Анықтама.
 
Мүлтіксіз конъюнктивті
 
қалыпты форма
 
(МКҚФ) деп 
мынадай КҚФ айтылады: әрбір элементар дизъюнкцияға әрбір айнымалы бір ақ 
рет енеді және не тек өзі, не оның терісі ғана, элементар дизъюнкция арасында 
бірдейлері болмау керек.
а) 
3
2
1
3
2
1
x
x
x
x
x
x

- МДҚФ;
б) 






)
(
)
(
z
y
x
z
y
x
)
(
z
y
x



- МКҚФ;
в) 
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x


- МДҚФ емес, себебі екі бірдей элементар 
конъюнкция бар;
г) 
3
2
1
3
1
1
x
x
x
x
x
x

- МДҚФ емес, себебі бір элементар конъюнкцияда әрі 
айнымалы, әрі оның терісі бар: 
1
1
,
x x
.

Теорема.
 

(МДҚФ және МКҚФ бар болуы және жалғыздығы). Кез келген 
логикалық 
формула 
жалғыз 
жолмен 
(элементар 
конъюнкциялар 
(дизъюнкциялар) түрлену ретінің дәлдігіне дейін) МДҚФ (МКҚФ) түріне 
келтіруге болады.
МДҚФ-ке келтіру үшін екі әдістің біреуімен қолдану керек. 

І әдіс: формуланы ДҚФ-ке келтіреміз; Егер қандай да бір элементар 

конъюнкцияда қандай да бір 
у 
айнымалысы жоқ болса, онда тарқату заңы 
бойынша оны енгізуге болады: 
)
(
)
(
y
x
y
x
x




; идемпотенттік заңын 
қолданып
 
бірдей элементар конъюнкцияларды алып тастаймыз: 
x
x
x


.

Мысалы 2.3.6
- ДҚФ түрінде жазылған 
zu
xz
xy




функцияны МДҚФ- 
ке келіру керек:

{
(
)(

)} { (
)(
)} {
(
)(
)} {(
)
xy z
z u
u
xz y
y u
u
zu x
x y
y
xyz
xyz












(
)} {(
)(
)} {(
)(
)}
u
u
xzy
xz y u
u
zux
zux y
y
xyzu
xyzu
xyuz











xyzu
xzyu
xzyu
xzu y
xz yu
zuxy
zux y
zuyx
zux y
xyzu











xyzu
xyuz
xyzu
xz yu
zux y
zuyx
zux y







- МДҚФ. 

ІІ әдіс:
 

берілген формуланың ақиқаттық кестесін құрамыз. Содан соң а 
Шеннон теоремасына негізделген ережені қолданамыз:
)
,...,
(
1
n
x
x
f
функциясының МДҚФ-дағы элементар конъюнкция саны 
f
мәнінің 
бағанындағы бірлер санына тең; әрбір 
)
,...,
,
(
2
1
n



нолдер мен бірлердің бірлік 
жиынтығына барлық айнымалылардың элементар конъюнкциясы сәйкес келеді: 
егер 
0

i

болса, онда 
i
x
терісімен жазылады, ал егер 
1

i

болса, онда 
i
x
өзгеріссіз жазылады. 
Мысалы 2.3.7
- ДҚФ түрінде жазылған 
z
y
x
yz
x




, функцияны 
МДҚФ-ке келтіру керек 
Ақиқат кестесін құрамыз: 
2.3.1 кесте 
x
y
z
x
y
z
y

y
x

z
y
x
yz
x


0 0 0 1 1 
0 
1 
0 
0 
0 
0 0 1 1 1 
0 
1 
1 
0 
1 

31 
0 1 0 1 0 
0 
0 
0 
0 
0 
0 1 1 1 0 
1 
0 
0 
1 
1 
1 0 0 0 1 
0 
0 
0 
1 
1 
1 0 1 0 1 
0 
0 
0 
1 
1 
1 1 0 0 0 
0 
0 
0 
1 
1 
1 1 1 0 0 
1 
0 
0 
1 
1 
Функция аргументтің келесі мәндерінде 1 мәнін қабылдайды:
)}
1
,
1
,
1
(
),
0
,
1
,
1
(
),
1
,
0
,
1
(
),
0
,
0
,
1
(
),
1
,
1
,
0
(
),
01
,
0
{(
- бұл оның бірлік жиынтықтары. Жоғарыда 
келтірілген ереже бойынша 
xyz
z
xy
z
y
x
z
y
x
yz
x
z
y
x







- МДҚФ. 
Формуланы МКҚФ-ке келіру МДҚФ-ке келіру сияқты жүргізіледі. Екі 
әдіс арқылы МКҚФ-ке келтіруге болады:
а) элементар түрлендіру әдісі;
б) ақиқат кестесінен функцияның нөлдік жиынтықтыры жазып алынады; 
)
,...,
(
1
n
x
x
f
функциясының МКҚФ-дағы элементар дизъюнкция саны 
f
мәнінің 
бағанындағы нөлдер санына тең; әрбір 
)
,...,
,
(
2
1
n



нолдер мен бірлердің нөлдік 
жиынтығына барлық айнымалылардың элементар дизъюнкциясы сәйкес келеді: 
егер
1

i

болса, онда 
i
x
терісімен жазылады, ал егер 
0

i

болса, онда 
i
x
өзгеріссіз жазылады. 
Мысалы 2.3.8
– Алдыңғы мысалдағы функцияны қарастырайық: 
z
y
x
yz
x




. Оны МКҚФ-ке екі әдіспен келтіреміз: 
а) 














)
(
)
(
z
y
x
z
y
x
z
y
x
yz
x
z
y
x
yz
x


;
МКҚФ
)
(
)
(
)
(
)
)(
(




























y
x
z
y
z
x
y
x
z
y
z
x
y
x
z
y
z
x
y
x
z
y
x
z
y
x
z
y
z
x
y
y
x
z
y
x
z
y
z
x
x
z
y
x
z
y
z
x
x
z
y
x
z
y
z
x
y
y
x
z
x
y
x
z
y
б) 2.3.1 кестеден нөлдік жиынтықты теріп жазамыз: 
)
0
,
1
,
0
(
)
0
,
0
,
0
(
0




, 
яғни, жоғарыдағы әдіс бойынша


)
(
)
(
z
y
x
z
y
x





- МКҚФ. 
2.4 Дәріс 7. Буль функцияларын минимизациялау 
Дәріс мазмұны: ДҚФ классында буль функцияларын минимизациялау; 
Карно картасы. 
Дәріс мақсаты: минимизациялау ұғымының мағынасы; минимизациялау 
әдісінің бірін қарастыру. 
Қолданбалы 
есептерді 
шығарғанда 
логикалық 
формулаларды
минимизациялау қажеттігі жиі туындайды. Мысалы, ең аз айнымалылы немесе 
ең аз қисабы бар формулаларды және т.б. табу есертері. Қазіргі уақытта 
айнымалы ең аз енетін дизъюнктивті формаларды табу терең зерттелген.
Айнымалының енуі деп айнымалының формуладағы алатын орны түсініледі. 

Анықтама.

 
Минималды ДҚФ деп айнымаллары ең аз етін ДҚФ айтылады.

32 
Минималды ДҚФ-ты табудың бірнеше әдісі бар (Квайн әдісі, белгісіздер 
коэффициенті, гиперкуб көмегімен және т.б.). Ең қарапайымына тоқтаймыз –
Карно картасын (диаграммасын) қолдану арқылы.

 
Карно картасы
 
– бұл әрбір тор (ұяшық) барлық айнымалылардың қандай 
да бір элементар конъюнкцияға сәйкес келетін кесте. 
n
x
x
x
,...,
,
2
1
 
n
айнымалылы 
функция үшін 
n
2
мәндерінің 0 және 1-ден тұратын мүмкін комбинациясы 
сәйкес келеді. Яғни, 
n
=2 болса, 
4
2
2

элементар конъюнкциялар 
y
x
y
x
y
x
xy
,
,
,
, 
оларға 0 және 1-лердің келесі жиынтықтары сәйкес келеді: (1,1), (1,0), (0,1), 
(0,0); n=3 болса,
8
2
3

- 
z
y
x
z
xy
xyz
,
,
,

- (1,1,1), (1,1,0),…,(0,0,0) және т.с.с. 
Карно картасы
 
2
2
n k
k


өлшемді кесте түрінде құрылады, оның бағанына 
k
x
x
x
,...,
,
2
1
 
айнымалыларының мәндері,
 
жолдары - 
n
k
k
x
x
x
,...,
,
2
1


(немесе 
керісінше). Жалпы, бір функцияның бірнеше картасы болуы мүмкін, тек 
ұяшықтарды біріктіру (тігінен, не көлденеңінен) бір айнымалының мәніне 
өзгешеленуі керек. Көбіне бір, екі, үш және төрт айнымалылы функцияны 
қарастырамыз. Олар үшін Карно картасы келесі түрде болады:
а) екі 
х, у
айнымалылы функция үшін Карно картасы 2.4.1 суретте;
б) үш 
z
y
x
,
,
айнымалылы функция үшін - 2.4.2 суретте;
в) төрт 
t
z
y
x
,
,
,
айнымалылы функция үшін - 2.4.3 суретте. 
2.4.1 сурет 2.4.2 сурет 2.4.3 сурет 
Буль функциясының минималды ДҚФ анықтау үшін алдымен оның 
МДҚФ табу керек. Содан соң МДҚФ-тағы әрбір элементар конъюнкцияны 
Карно картасында бірмен белгілеу керек.

Мысал 2.4.1
-
y
x
xy


1

және 
z
y
x
z
y
x
z
xy



2

функциялары МДҚФ 
формасында жазылған. 
1

үшін Карно картасы 2.4.4 суретте; 
2

үшін 2.4.5 
суретте.
2.4.4 сурет 2.4.5 сурет 
Айта кетелік, егер Карно картасында 2, 4, 8 көрші ұяшықтарда (тігінен не 
көлденең) 1 тұрса, онда бұл ұяшықтар блоктарға бірігеді (картада олар сопақ 

33 
сызықпен 
белгіленеді), 
және 
осы 
блоктарға 
сәйкес 
элементар 
конъюнкциялардың дизъюнкциясын қысқартуға болады. 2.4.1 мысалдағы 
1

функция үшін 2 ұяшықты блок аламыз (2.4.4 суретте сопақ сызықпен 
белгіленген). Бұл блокқа 
y
x
xy

дизъюнкциясы сәйкес келеді, оны қысқартсақ:


y
x
xy
x
x
y
y
x





1
)
(
. Сонымен, 2 ұяшықты блок бір 
х 
айнымалысына тең 
болады, дәлірек айтқанда осы блокты толық «қамтитын» айнымалы. Формула 
қысқартылды: 
x

1

. 
2

функциясы үшін де 2 ұяшықты блок аламыз (2.4.5 суретті қара), оған 
элементар конъюнкциялардың дизъюнкциясы сәйкес келеді 
z
y
x
z
xy

. Оны 
қысқартсақ 
z
y
, яғни үш айнымалылы 2 ұяшықты блокқа осы блокты 
«қамтитын» екі айнымалылы конъюнкция сәйкестенді. Формула қысқартылды: 
z
y
x
z
y


2

.
Тағы бірнеше мысал қарастырайық. 
Мысал 2.4.2
- 
z
y
x
z
y
x
yz
x
xyz





- функцияның МДҚФ. Оның Карно 
картасы 2.4.6. суретте бейнеленген. z картаның екі шетінде де 
орналасқандықтан, картаны «бұрауға» болады және картаның бұрыштары төрт 
ұяшықты блок құрайды деп есептейміз. Бұл ұяшықтарды 
z 
айнымалысы 
қамтиды. Сонымен функцияның МДҚФ-ы:
z


. 
2.4.6 сурет 2.4.7 сурет 
Мысал 2.4.3
- 
zt
y
x
yzt
x
zt
y
x
xyzt





- функцияның МДҚФ. Оның Карно 
картасы 2.4.7. суретте бейнеленген. Картада 
z
және 
t
айнымалыларын 
қамтитын төрт ұяшықты блок бар, сондықтан функцияның МДҚФ-ы: 
zt


. 
Мысал 2.4.4
- 
x
yzt
t
z
x
y
t
x
yz
t
z
xy
t
xyz
z
xyt
xyzt











t
z
y
x
t
z
y
x
t
y
xz
y
xzt


- функцияның МДҚФ. Оның Карно картасы 2.4.8. суретте 
бейнеленген.

34 
2.4.8 сурет 
Картада 8 ұяшықты блокты 
y 
айнымалысы қамтиды, төрт ұяшықты екі 
блокты сәйкес элементар конъюнкциялар 
xt
және 
xz
қамтиды. Сондықтан
функцияның МДҚФ-ы: 
xz
xt
y




. 
2.5 Дәріс 8. Буль алгебрасының изоморфизмі. Математикалық 
логиканың кейбір қолданулары 
 
Дәріс мазмұны: буль алгебрасы және жиындар теориясы; коммутациялық 
сұлбалар. 
Дәріс мақсаты: буль алгебрасының изоморфизмінің маңыздылығын атап 
өту; жоғарыда атап өтілген материалдың қолдану мысалдарын көрсету. 

Буль алгебрасы және жиындар теориясы. 
Жиындарға қолданылатын қисаптардың қасиеттері мен логикалық 
қисаптар арасындағы аналогты байқауға болады. Бұл кездейсоқ емес. 
Анықтама.
 
1) - 9) шарттарын қанағаттандыратын (буль алгебрасының 
негізгі эквивалентті қарым-қатынастары немесе жиындарға қолданылатын 
қисаптардың негізгі қасиеттерін қара) екі бинарлы және бір унарлы операциясы 
бар кез келген алгебра буль алгебрасы деп аталады. 
Сонымен, буль алгебрасы: 
а) 
)
,
,
,
(
2


P
- конъюнкция, дизъюнкция, теріске шығару қисаптарымен 
барлық буль алгебрасы; 
б) 
)
,
,
),
(
(
2


m
P
- 
m
айнымалылы логикалық функциялардың буль 
алгебрасы – бұл 
)
,
,
,
(
2


P
алгебрасының ішкі алгебрасы, себебі 
2
2
( )
P m
P

; 
в) (
P
)
,
,
),
(



U
- 
U
универсумдағы қиылысу, бірігу, толықтауыш 
қисаптарымен жиындардың буль алгебрасы;
г) 
)
,
,
,
(


n
B
- 
n
ұзындықты екілік векторлардың буль алгебрасы, мұнда 
),
,...,
,
(
2
1
n






)
,...,
,
(
2
1
n





екілік векторларға логикалық қисаптар келесі 
жолмен анықталады 
1) 
)
,...,
,
(
2
2
1
1
n
n













, мұндағы егер 
1


i
i


, онда 
,
1


i
i


; кез келген жағдайда 
0
i
i




; 

35 
2) 
)
,...,
,
(
2
2
1
1
n
n













, мұндағы егер 
0
,
0


i
i


онда 
,
0


i
i


; кез келген жағдайда 
1
i
i




; 
3) 
)
,...,
(
n
i




, мұндағы егер 
1

i

, онда 
,
0

i

егер
0
i


, онда 
1
i


. 
Егер 
P
),
(
U
n
B
және 
)
(
2
m
P
жиындарының қуаттары тең болса
(
P
2
( )
( )
n
U
B
P m


), онда олардың арасында өзара бірмәнді сәйкестік орнатуға 
болады, ал сәйкес буль алгебралары изоморфты бола алады. Буль
алгебраларының изоморфизмі компьютер есептеулерінде кеңінен қолданылады, 
мысалы, жиындарға немесе логикалық функцияларға қолданылатын 
қисаптардың орнына олардың изоморфты аналогтары – екілік векторларға
разряд бойынша операциялар орындалады.
 
Коммутациялық сұлбалар. 
Математикалық логиканың техникалық сұрақтарда қолданылатындығы 
ХХ ғасырдың 30-шы жылдары анықталды. Мысалы, электр шынжыры мен 
логикалық функциялар арасындағы байланыс байқалды. Бұл жаңалық ЭЕМ 
дамуына әсер етті. Осы байланыстың қысқартылған түрін қарастырайық.
Релейлі-байланыс құрылғыларының басты элементі электр-механикалық 
реле болып табылады (ауыстырып-қосқыш). Реле шынжырды бекітеді және 
ажырата да алады. Шынжыр тұйық болғанда (тоқ өтеді), 
р-ға 
1 мәнін береміз, 
ал шынжыр ажыратылғанда (тоқ өтпейеді), 
р-ға 
0 мәнін береміз. 
2.5.1 суреттегі электр шынжырын қарастырайық. 
p
және 
q
контакттерінің 
былай орналасуында лампы жанады (яғни сұлба 1 мәнін қабылдайды), егер
p
және 
q
ауыстырып-қосқыштың екеуі де тұйықталған болса (яғни 1 мәнін 
қабылдайды). Сонымен, бұл сұлба 
q
p

логикалық формуласына сәйкес келеді, 
ал ауыстырып-қосқыштың бұлай орналасуы «
p
және 
q
» логикалық элементі 
немесе логикалық көбейту сұлбасы деп аталады. Оны сұлбалы түрде 2.5.2 
суреттегідей бейнелейді.
2.5.1 сурет 2.5.2 сурет
2.5.3 суреттегі сұлбаны қарастырамыз. Бұл шынжырда лампочка жанады 
және сұлба мәні 1-ге тең. Егер 
p
немесе 
q 
екі контакттің ең болмағанда біреуі, 
немесе екеуі де тұйықталған болса, яғни немесе 
1

p
, немесе 
1

q
, немесе екеуі 
де 
1


q
p
. Сонымен, бұл сұлба 
q
p

логикалық формуласына сәйкес келеді, ал 
ауыстырып-қосқыштың бұлай орналасуы «
p
немесе 
q
» логикалық элементі 

36 
немесе логикалық қосу сұлбасы деп аталады. Оны сұлбалы түрде 2.5.4 
суреттегідей бейнелейді.
2.5.3 сурет 2.5.4 сурет 2.5.5 сурет 
Егер бір ғана
p 
ауыстырып-қосқышы бар сұлба қарастырсақ, онда ол 
келесі қасиетке ие болады:
p
тұйықталғанда ғана лампа жанады (яғни 
р
=0 
болғанда сұлба 1 мәнін қабылдайды, р=1 болғанда сұлба 0 мәнін қабылдайды), 
онда бұл сұлба 
p
сәйкес келеді. Бұндай логикалық «
р емес
» немесе инвертор 
деп аталады, оны жиі 2.5.5 суреттегідей бейнелейді.
Қарапайым логикалық формулалар қолданылатын сұлба мысалдарды 
қарастырайық. 
Мысал 2.5.1
- 2.5.6 суреттегі сұлба 
)
(
)
(
3
1
2
1
x
x
x
x



формуласына 
(ауыстырып-қосқыш функциясына немесе өткізгіштік функциясына) сәйкес; 
1
2
1
2
(
)
(
)
x
x
x
x



формуласының сұлбасы 2.5.7 суретте бейнеленген; 2.5.8 
суреттегі сұлба 
)
(
))
(
(
2
1
3
2
1
x
x
x
x
x




формуласына сәйкес. 
 
2.5.6 сурет 2.5.7 сурет 2.5.8 сурет
 
 
 
Кез
 
келген логикалық формуланы ДҚФ немесе КҚФ-ке келтіруге 
болғандықтан, оған әрқашан контакт сұлбасын құруға болады. Өткізгіштіктің 
анықтаушы функциясының формуласы неғұрлым қарапайым болса, соғұрлым 
сұлба да қарапайым. Сондықтан сұлбаны қысқарту есебі сәйкес функцияны 
қысқартуға әкеледі. Жоғарыда бұндай есептерді шығардық. 
Мысал 2.5.2
- 2.5.9 суреттегі сұлбаны қысқартайық.

 
2.5.9 сурет 

37 
Ауыстырып-қосқыш функцияны құрамыз 
)
(
)
(
)
((
)
,
,
(
z
x
z
y
y
x
z
y
x
f






. 
Эквивалентті түрлендірулерді қолданып, осы функцияны қысқартамыз. 







)
(
))
(
)
((
)
,
,
(
z
x
z
y
y
x
z
y
x
f








)
(
)
(
z
x
z
y
z
x
y
x
z
y
x
z
y
x
z
x
y
z
y













)
(
1
)
(
)
1
(
. 
Соңғы формулаға қысқартылған сұлба сәйкес келеді: 
2.5.10 сурет 

38 
Әдебиеттер тізімі 
1.
Новиков Ф.А. Дискретная математика для программистов. Учебник
для вузов. 2-е изд. – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для 
вузов»).
2.
Андерсон. Д. Дискретная математика и комбинаторика.: Пер. с 
англ. – М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. 
англ. 
3.
Шапорев С.Д. Дискретная математика. Курс лекций и практических
занятий. – СПб.: БХВ-Петербург, 2006.- 396 с. 
4.
Досанбай П.Т. Математикалық логика. Оқулық. - Алматы, 2011. 
5.
Жетпісов Қ. Математикалық логика және дискретті математика. -
Алматы, 2011. 
6.
Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика:
Учебное пособие.- Ростов н/Д: «Феникс»6 Харьков: «Торсинг», 2003. -144 с. 
7.
Плотников А.Д. Дискретная математика: Учебное пособие/ 
А.Д.Плотников. – 2-е изд., испр. и доп. – М.: Новое знание, 2006.– 304 с.
Мазмұны 
 
1 Жиындар теориясының элементтері
1.1 Дәріс 1. Жиындар
 
3 
1.2 Дәріс 2. Қатынастар 
6 
1.3 Дәріс 3. Арнайы бинарлы қатынастар 
9 
2 Математикалық логика элементтері 
2.1 Дәріс 4. Тұжырымдар және логикалық қисаптар (операциялар) 
16 
2.2 Дәріс 5. Эквивалентті формулалар. Алгебра логикасының негізгі 
эквивалентті қарым-қатынастары 
21 
2.3 Дәріс 6. Дизъюнктивті және конъюнктивті қалыпты формалар (ДҚФ, 
КҚФ) 
25 
2.4 Дәріс 7. Буль функцияларын минимизациялау 
29 
2.5 Дәріс 8. Буль алгебрасының изоморфизмі. Математикалық логиканың 
кейбір қолданулары 
31 
Әдебиеттер тізімі 
35 

39 
2014 ж. жиынтық жоспары, реті 364
Астраханцева Людмила Николаевна 
Байсалова Мәншүк Жұмамұратқызы 
ДИСКРЕТТІ МАТЕМАТИКА 
 
5В070300- Ақпараттық жүйелер мамандығының студенттері үшін
дәрістер жинағы 
Редактор Қ.С.Телғожаева 
Стандарттау бойынша маман Молдабекова Н.Қ. 
Басуға қол қойылды_______ Пішіні 60х84 1/16 
Таралымы 25 дана №1 типографиялық қағаз
Көлемі 2,3 баспа табақ Тапсырыс______Бағасы 1150 тг. 
«Алматы энергетика және байланыс университеті» 
Коммерциялық емес акционерлік қоғамының 
көшірме-көбейткіш бюросы 
050013, Алматы, Байтұрсынұлы көшесі, 126