АЛМАТЫ ЭНЕРГЕТИКА ЖӘНЕ БАЙЛАНЫС ИНСТИТУТЫ
ЖОҒАРЫ МАТЕМАТИКА КАФЕДРАСЫ
Дискрет математика
Есептеу-графикалық жұмыстарды орындауға
арналған әдістемелік нұсқаулар мен тапсырмалар
(050704 – Есептеу техникасы және бағдарламалық қамтамасыз
ету мамандығы бойынша оқитын барлық бөлім студенттері үшін)
2 бөлім
ҚҰРАСТЫРУШЫЛАР: Л.Н. Астраханцева, М.Ж.Байсалова. Дискрет математика. 050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері үшін есептеу-графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар. «Есептеу техникасы және бағдарламалық қамтамасыз ету» мамандығы
бойынша оқитын барлық бөлім студенттеріне арналған есептеу графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар
«Дискрет математика» пәнінің № 3 типтік есептеулерден тұрады.
Бағдарламаның теориялық сұрақтары енгізілген. Типтік варианттың шешімі
келтірілген.
1 Есептік-графикалық жұмыс 2. Математикалық логика
1.1 Теориялық сұрақтар
1 Тұжырымдар логикасының негізгі ұғымдары. Тұжырымдар, негізгі логикалық қисаптар.
2 Логикалық айнымалылар мен формулалар. Логикалық қисаптар мен формулалардың ақиқаттық таблицасы.
3 Логика алгебрасының функциялары. Логикалық функцияларының берілу жолдары (ақиқаттық таблицасы, нөлдік және бірлік жиынтықтар, мәндердің векторы, формула).
4 Формулалардың эквиваленттігі. Логика алгебрасының негізгі эквиваленттік қатынастар.
5 Логикалық функциялар жүйесінің толықтығы. Логикалық функцияларды ДҚФ, КҚФ-ке келтіру.
5 Мүлтіксіз ДҚФ және КҚФ (МДҚФ және МКҚФ).
6 ДҚФ класында минимизациялау. Карно картасы.
7 Коммутациялық сұлбалар.
8 Қосалқылық. Буль алгебрасы және жиындар теориясы.
1.2 Есептік тапсырмалар
1. Формула үшін ақиқаттық таблицасын құру керек
1 К е с т е
|
1.1 |
1.16 |
|
1.2 |
1.17 |
|
1.3 |
1.18 |
|
1.4 |
1.19 |
|
1.5 |
1.20 |
|
1.6 |
1.21 |
|
1.7 |
1.22 |
|
1.8 |
1.23 |
1 кестенің жалғасы
|
1.9 |
1.24 |
|
1.10 |
1.25 |
|
1.11 |
1.26 |
|
1.12 |
1.27 |
|
1.13 |
1.28 |
|
1.14 |
1.29 |
|
1.15 |
1.30 |
2. Формулалардың эквиваленттігін:
а) ақиқаттық кестесінің көмегімен;
б) формуланы эквивалентті түрлендіру көмегімен МДҚФ немесе МКҚФ келтіру арқылы тексеріңіз.
2 К е с т е
|
2.1 |
2.16 |
|
2.2 |
2.17 |
|
2.3 |
2.18 |
|
2.4 |
2.19 |
|
2.5 |
2.20 |
|
2.6 |
2.21 |
|
2.7 |
2.22 |
|
2.8 |
2.23 |
|
2.9 |
2.24 |
|
2.10 |
2.25 |
|
2.11 |
2.26 |
|
2.12 |
2.27 |
|
2.13 |
2.28 |
и 
и 
2 кестенің жалғасы
|
2.14 |
2.29 |
|
2.15 |
2.30 |
и 
3 Формуланы қысқартыңыз
3 К е с т е
|
3.1 |
3.16 |
|
3.2 |
3.17 |
|
3.3 |
3.18 |
|
3.4 |
3.19 |
|
3.5 |
3.20 |
|
3.6 |
3.21 |
|
3.7 |
3.22 |
|
3.8 |
3.23 |
|
3.9 |
3.24 |
|
3.10 |
3.25 |
|
3.11 |
3.26 |
|
3.12 |
3.27 |
|
3.13 |
3.28 |
|
3.14 |
3.29 |
|
3.15 |
3.30 |
4 Формуланы қарапайым айнымалылырға тек Ø, Ù, Ú операциялары қолданған түрінде жазыңыз
4 Ке с т е
|
4.1 |
4.16 |
|
4.2 |
4.17 |
|
4.3 |
4.18 |
|
4.4 |
4.19 |
|
4.5 |
4.20 |
|
4.6 |
4.21 |
|
4.7 |
4.22 |
|
4.8 |
4.23 |
|
4.9 |
4.24 |
|
4.10 |
4.25 |
|
4.11 |
4.26 |
|
4.12 |
4.27. |
|
4.13 |
4.28 |
|
4.14 |
4.29 |
|
4.15 |
4.30 |
5-12. Берілген формула үшін:
а) ақиқаттық кестесін құру керек;
ә) ДҚФ-ға келтіру керек;
б) ақиқаттық кестесі бойынша МДҚФ құру керек;
в) Карно картасын құру керек;
г) Карно картасы көмегімен минималды ДҚФ;
д) минималды ДҚФ-тан КҚФ-қа көшу керек;
е) МКҚФ табу керек;
ж) Карно картасы бойынша минималды КҚФ табу керек.
5 К е с т е
|
1 |
16 |
|
2 |
17 |
|
3 |
18 |
|
4 |
19 |
|
5 |
20 |
|
6 |
21 |
|
7 |
22 |
|
8 |
23 |
|
9 |
24 |
|
10 |
25 |
|
11 |
26 |
|
12 |
27 |
|
13 |
28 |
|
14 |
29 |
|
15 |
30 |
13 Сұлбаны қысқарту керек
 |
13.1
13.2
 |
13.3
 |
13.4
 |
13.5
 |
13.6
 |
13.7
 |
13.8
 |
13.9
 |
13.10
 |
13.11
11.12
 |
13.13
 |
13.14
 |
13.15
 |
13.16
13.17
13.18
 |
13.19
 |
13.20
|
13.21
13.22
 |
13.23
|
13.24
 |
13.25
|
13.26
|
13.27
|
13.28
 |
13.29
|
13.30
1.3 Типтік варианттың шешуі
1. 
және 
формулаларының:
а) ақиқаттық кестесінің көмегімен;
ә) формуланы эквивалентті түрлендіру көмегімен МДҚФ немесе МКҚФ келтіру арқылы эквиваленттігін көрсетіңіз.
Шешуі:
а) формулалар үшін ақиқаттық кестесін құрайық, ол үшін формулаға енетін операциялардың ақиқаттық кестесін қолданамыз:
6 Кесте
|
x |
y |
z |
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
7-ші және 10-шы бағандары, яғни 
және 
формулаларының
мәндерінің бағандары
бірдей болғандықтан, бұл формулалар эквивалентті;
ә) логикалық
операциялардың белгілі
қасиеттерін пайдаланып формуласын алдымен дизъюнктивті қалыпты формаға (ДҚФ) түрлендіреміз: =[дистрибутивтік]=
=
[идемпотенттік]=
. Соңғы өрнек формуласы үшін ДҚФ болып табылады. Мүлтіксіз
дизъюнктивті қалыпты формаға (МДҚФ) келтіру үшін, тарқату
заңын қолданып бірінші және екінші конъюнкттерге жетпей
тұрған айнымалыларды қосамыз.
(
): =
=
=[коммутативтік, идемпотенттік]
= 
– формуласының МДҚФ.
формуласы ДҚФ түрінде
берілген, сондықтан оның МДҚФ анықтау үшін
әрбір конъюнктке жетпей тұрған айнымалыларды қосамыз:
=
=
=[коммутативтік, идемпо-
тенттік]=- формуласының МДҚФ.
Екі формуланың да МДҚФ бірдей болғандықтан, олар эквивалентті.
2. 
формуласын қысқарту керек.
Шешуі:
формуланы
қысқарту үшін логикалық қисаптардың
қасиеттерін қолданамыз: 
=[белгілі эквиваленттікті
қолданамыз 
]=
= [дистрибутивтік]=
=
=
[коммутативтік, қарама-қайшылық заңы, идемпотенттік]=
=[нөлдің қасиеті, коммутативтік]=
=
[дистрибутивтік]=
=[бірдің қасиеті, идемпотенттік]=
.
3. 
формуласы берілген:
а) ДҚФ-ға келтіру керек;
ә) ақиқаттық кестесін құру керек;
б) ақиқаттық кестесі бойынша МДҚФ құру керек;
в) Карно картасын құру керек;
г) Карно картасы көмегімен минималды ДҚФ;
ғ) минималды ДҚФ-тан КҚФ-қа көшу керек;
д) МКҚФ табу керек;
е) Карно картасы бойынша минималды КҚФ табу керек.
Шешуі:
а) формуланың ДҚФ-ын
операциясының
анықтамасын және логикалық операциялардың
қасиеттерін қолданып таба аламыз: =
=[ Де-Морган заңы]
=
=[екі рет теріске
шығару]=
=
=[дистрибутивтік]=
=
=[идемпотенттік]=
=
.
Соңғы өрнек формуланың ДҚФ болып табылады;
ә) формулалардың ақиқаттық таблицасын құрамыз (7 кесте);
б) ақиқаттық
кестесі бойынша формуланың мүлтіксіз дизъюнктивті қалыпты
формасын (МДҚФ) құрамыз. Ол үшін формуланың 1
мәнін қабылдайтын (
=1) айнымалы
мәндерінің жиынтықтарын тізіп жазамыз:
{(0011),(0100),(0101),(0110),(0111),(1011),(1111)}.
Келесі ережені қолданамыз: 
функциясының мәндерінің бағанында қанша бірлік
болса, МДҚФ-ында сонша конъюнкт болады; әрбір 
нөлдік және бірлік жиынтықтарына: егер 
болғанда 
теріске шығарылып, ал 
болғанда теріске шығарылмай
алынған барлық айнымалылардың конъюнктасы сәйкес келеді.
Сонымен, берілген формуланың МДҚФ дизъюнкциясы
түріндегі жеті конъюнкталардан
тұрады (
таңбасын
жазбадық);
7 Кесте
|
A |
B |
C |
D |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
в) төрт айнымалылы функцияның
Карно картасы 
ұяшықтан
тұратын кестені білдіреді (төрт айнымалылы функцияның
мүмкіндігінше қанша
0 және 1 жиынтықтары болса, сонша ұяшық саны), көрші ұяшықтар бір
айнымалының мәніне өзгеше болатын жолдар мен бағандар
айнымалы мәндеріне немесе оның терісіне сәйкес келеді.
Минималды ДҚФ алу үшін функцияның МДҚФ-ң
әрбір конъюнктасы Карно картасындағы сәйкес
ұяшықта бірмен беелгіленеді:
|
|
|
|
|
||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|
1 Сурет
г) минималды ДҚФ алу үшін
бірліктер қатар тұрған тік және көлденең
жолдарды біріктіру керек. Біріктірілген бірліктерді блок деп те атайды. Блок
2, 4, 8 ұяшықтан тұруы мүмкін, 2 ұяшықтан
блок деп қатар тұрған емес, кестенің бір жақ
бұрышында тұрған бірліктерді айтуға болады. Немесе кестенің
төрт бұрышында тұрған 4 бірліктен тұратын да 4
ұяшықты блок болады, бұл жағдайда бағанды
бағанға (С-ны С-ға) және жолда жолға (Д-ны
Д-ға) “бұрауға” болады. Біздің Карно картасында 4
ұяшықтан тұрған екі блок бар. Төменгі сол
бұрыштағы блокты 
және 
айнымалылары жабады, сондықтан оған конъюнкциясы сәйкес келеді, картаның
бұрышындағы 4 ұяшықты блокқа 
конъюнкциясы сәйкес келеді. Сонымен, 
формуланың минималды ДҚФ;
ғ) минималды ДҚФ-ы конъюнктивті қалыпты формаға келтірейік (КҚФ):
=[екі рет теріске шығару]=
=
[Де-Морган заңы
]=
=[Де-Морган заңы
]=
=
=[дистрибутивтік]=
=
=[Де-Морган заңы
]=
=
=[Де-Морган заңы, екі рет
теріске шығару
]=
=
- формуланың КҚФ;
д) айнымалының нөлдік мәндерінің жиынтығын
пайдаланып, мүлтіксіз конъюнктивті
қалыпты формасын (МКҚФ) алуға болады.
Ақиқаттық кестесінен формула 0 мәніне ие болатын (=0) жиынтықтарды теріп жазамыз: 
. Енді МКҚФ мәндер бағанында
қанша нөл болса, сонша дизъюнкттан тұратынын
және нөл мен бірлерден
тұратын нөлдік жиынтық барлық айнымалылардың дизъюнктасы
сәйкес келетінін ескереміз. Егер болса, онда i-ші айнымалы
теріске, шығарылып, ал болса, теріске
шығарылмай алынады. Бұдан
–
формуланың МКҚФ;
е) минималды КҚФ-ы алу үшін Карно картасын қолдануға болады. Карта бойынша ДҚФ минималдандырған сияқты, ондағы айнымалыларды оның терісіне және керісінше алмастырулар жасап, бос орындарға 0-ді қойып және 1-ді алып тастап, немесе МКҚФ-тың дизъюнкттеріне сәйкес ұяшықтарды нөлге толтырамыз.
Картада 2,4,8 және т.б. көршілес нөлдік блоктарды белгілеп аламыз. Біздің жағдайда 4 ұяшықты 4 блок бар, оларға екі айнымалының қысқартылған дизъюнкттеры сәйкес келеді. Сонымен, формуланың минималды КҚФ-ы мына түрде болады
.
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
0 |
|
0 |
|
|
|
|
|
|
0 |
0 |
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
2
Сурет
4 Схеманы
қысқартыңыз
3 Сурет
Шешуі:
берілген сұлбаның өткізгіштік функциясын құрамыз
. Әдістердің бірін қолданып ( мысалы, элементарлық түрлендірулер әдісі, Карно картасы көмегімен
минимизациялау және т.б.), бұл
функцияны қысқартамыз:
[дистрибутивтік]=
=[жұту қасиеті]=
=
. Алынған формулаға қысқартылған сұлба
сәйкес келеді:
4 Сурет
1.4 Анықтамалық мәліметтер
Логикалық қисаптар және олардың ақиқаттық кестесі
1. Конъюнкция – (
), «x және y» деп
оқылады.
2. Дизъюнкция – ( 
), «x немесе y» деп
оқылады.
3. Отрицание (инверсия) – (
),«x емес » «x-ті теріске шығару » деп
оқылады.
4. Импликация - (
),«егер х, онда у» деп оқылады.
5. Эквиваленция – (
), «х егер тек егер
у» деп оқылады.
6. Шеффер штрихы – (
), конъюнкцияның терісі болып
анықталады «x емес және y».
7. Пирс стрелкасы – (
), дизъюнкцияның
терісі болып анықталады «x немесе y».
8. Сақиналы қосынды – (
),
эквиваленцияның терісі болып анықталады «тек сол жағдайда
емес».
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
0 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
Негізгі эквиваленттік қатынастар (заңдар)
|
1 |
Коммутативтік |
|
|
|
|
2 |
Ассоциативтік |
|
|
|
|
3 |
Дистрибутивтік |
|
|
|
|
4 |
Идемпотенттік |
|
|
|
|
5 |
Сіңіру заңы |
|
|
|
|
6 |
Де-Морган заңы |
|
|
|
|
7 |
Екі рет теріске шығару
|
|||
|
8 |
Константалардың қасиеті |
|
|
|
|
9 |
|
|
||
-
-Тағы да басқа керекті эквиваленттік қатынастар:
|
10 |
Жапсыру заңы |
|
|
10 а |
Тарқату |
|
|
11 |
Жалпыланған жапсыру |
|
|
12 |
|
|
|
13 |
|
|
|
14 |
|
|
|
15 |
|
|
|
16 |
|
|
5 Сурет
Әдебиеттер тізімі
1. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.
2. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.
3. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 2-е изд. – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).
4. Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.
5. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.
6. Яблонский С.В. Введение в дискретную математику. – М. «Высшая школа», 2001.
Мазмұны
1 Есептік-графикалық жұмыс 3. Аналитикалық геометрия, квадраттық формалар
1.1 Теориялық сұрақтар
1.2 Есептік тапсырмалар
1.3 Типтік варианттың шешуі
1.4 Анықтамалық материал
Әдебиеттер тізімі