Коммерциялық емес акционерлік қоғам
АЛМАТЫ ЭНЕРГЕТИКА  ЖӘНЕ БАЙЛАНЫС УНИВЕРСИТЕТІ
Жоғары математика кафедрасы

ДИСКРЕТ МАТЕМАТИКА
Есептеу-сызба жұмыстарға әдістемелік нұсқаулар мен тапсырмалар
(5В070400 Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығына арналған) 2 бөлім

Алматы 2014

ҚҰРАСТЫРУШЫЛАР: Астраханцева Л.Н., Байсалова М.Ж. Есептеу-сызба жұмыстарға әдістемелік нұсқаулар мен тапсырмалар (5В070400 Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығына арналған) 2 бөлім.  - Алматы: АЭжБУ, 2014. -  23 б.

Бұл есептеу-сызба жұмыстарға әдістемелік нұсқаулар мен тапсырмаларында 5В070400 – Есептеу техникасы мен бағдарламалық қамтамасыз ету мамандығының барлық оқу түрінің студенттеріне «Дискрет  математика» пәнінің «Математикалық логика элементтері» оқып, үйрену үшін арналған.

Бұл материал көрсетілген мамандықтың «Дискрет  математика» пәнінің бағдарламасына сәйкес құрылған.

Тапсырмалар берілген және қажет теориялық мәліметтер келтірілген.

Кестелер- 9, без.- 1, әдеб.көрсеткіші – 7 атау.

«Алматы энергетика және байланыс университеті» коммерциялық емес акционерлік қоғамының  2014 ж. жоспары бойынша басылды

ã «Алматы энергетика және байланыс университеті» КЕАҚ, 2014 ж.

1 Типтік есеп № 2. Математикалық логикиа элементтері

1.1 Теориялық сұрақтар

1 Тұжырымдар логикасының негізгі ұғымдары. Тұжырымдар,  негізгі логикалық қисаптар (операциялар).

2 Логикалық айнымалылар және формулалар. Логикалық қисаптар мен формулалардың ақиқаттық кестесі. Логикалық қисаптардың орындалу реті туралы келісу.

3 Логика алгебрасының функциялары. Логика функцияларының берілу тәсілдері (ақиқаттық кестесі, нөлдік және бірлік жиынтықтар, мәндер векторы, формула).

4 Формулалардың эквиваленттілігі. Логика алгебрасының негізгі эквивалентті қарым қатынастар.

5 Логикалық функциялардың толық жүйесі. Логикалық функцияларды ДҚФ, КҚФ келтіру.

6 Мүлтіксіз ДҚФ және КҚФ (МДҚФ және МКҚФ).

7  ДҚФ класында минимизациялау. Карно картасы.

8 Коммутациялық сұлбалар.

9 Екі жақтылық. Буль алгебрасы және жиындар теориясы.

1.2 Есептік тапсырмалар  

1- кестегі формуламен берілген  f(x,y) функциясын:

а) ақиқаттық кестесімен;

 б) нөлдік және бірлік жиынтықтармен;

в) мәндерінің векторымен жазу керек.

1 кесте

№

f(x,y)

№

f(x,y)

1.1

1.2

1.3

1.4

1.5

1.6

1.7

1.8

1.9

1.10

1.11

1.12

1.13

1.14

1.15

1.16

1.17

1.18

1.19

1.20

1.21

1.22

1.23

1.24

1.25

1.26

1.27

1.28

1.29

1.30

2. Логикалық қисаптардың орындалу реті туралы келісуді қолданып f(x,y) формуласында жақшаларды қою керек.

 2 кесте

№

f(x,y)

№

f(x,y)

2.1

2.2

2.3

2.4

2.5

2.6

2.7

2.8

2.9

2.10

2.11

2.12

2.13

2.14

2.15

2.16

2.17

2.18

2.19

2.20

2.21

2.22

2.23

2.24

2.25

2.26

2.27

2.28

2.29

2.30

3. 2- тапсырмадағы формуланы тек теріске шығару, конъюнкция және дизъюнкция қисаптары көмегімен жазу керек; осы формуланы қысқарту керек.

4.   және  формулаларын эквиваленттілікке тексеру керек:

а) ақиқаттық кестесі көмегімен;

б) формулаларды эквивалентті түрлендіру көмегімен МДҚФ немесе МКҚФ-ке келтіру арқылы.

3 кесте

№

4.1

4.2

4.3

4.4

4.5

4.6

4.7

   

4.8

4.9

4.10

4.11

4.12

4.13

4.14

4.15

4.16

4.17

4.19

4.20

4.21

4.22

4.23

4.24

4.25

4.26

4.27

   

4.28

4.29

4.30

5. Берілген  f(A,B,C) функциясы үшін  ақиқаттық кестесін құру керек.

4 кесте

№

f(A,B,C)

№

f(A,B,C)

5.1

5.2

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10

5.11

5.12

5.13

5.14

5.15

5.16

5.17

5.18

5.19

5.20

5.21

5.22

5.23

5.24

5.25

5.26

5.27

5.28

5.29

5.30

 

5- тапсырмадағы функция үшін келесі амалдар орындау керек:

1) ДҚФ-ке келтіру;

2) ақиқаттық кестесі көмегімен МДҚФ табу керек;

3) Карно картасын құру керек;

4) Карно картасы көмегімен минималды ДҚФ;

5) минималды ДҚФ-тан КҚФ-ке көшу керек;

6) МКҚФ табу керек;

         7) Карно картасы бойынша минималды КҚФ табу керек.

6- берілген сұлба бойынша ауыстырып-қосқыш функциясын құрып, оны қысқарту керек. Қысқартылған функцияның сұлбасын салу керек

6.1

6.2

6.3

6.4

6.5

6.6

6.7

6.8

6.9

6.10

6.11

      

6.12

6.13

6.14

6.15

6.16

6.17

6.18

6.19

6.20

6.21

6.22

6.23

6.24

6.25

6.26

6.27

6.28

6.29

6.30

1.3 Типтік варианттың шешуі

1. Берілген  f(x,y) =   функциясын:

          а) ақиқаттық кестесімен;

         б) нөлдік және бірлік жиынтықтармен;

         в) мәндерінің векторымен жазу керек.

Шешуі:

         а) f(x,y) =   функциясының ақиқаттық кестесі:

5 кесте

f(x,y)

0

0

1

1

1

1

0

1

1

0

0

0

1

0

0

0

1

0

1

1

0

0

0

1

б) бірлік жиынтығы: 1=f(0,0)=f(1,1); нөлдік жиынтығы: 0=f(0,1)=f(1,0);

в) мәндерінің векторы: (1001).

2. Логикалық қисаптардың орындалу реті туралы келісуді қолданып f(x,y)=  формуласында жақшаларды қою керек.

         Шешуі: логикалық қисаптардың орындалу реті сұлбасы бойынша: , біздің формулада жақшалар былай қойылу керек: 

= .

3. 2 тапсырмадағы формуланы тек теріске шығару, конъюнкция және дизъюнкция қисаптары көмегімен жазу керек; осы формуланы қысқарту керек.

Шешуі:

= = | 15, 16 | == | 6 | =

== | 1 | = = | 5 | = .

         Түрлендіруде 20 беттегі анықтама материалдағы формула нөмірі көрсетілген. Формуланы қысқарту деп айнымалы саны аз енетін формуланы алуды түсінеміз.

4. = және =  формулаларын эквиваленттілікке тексеру керек:

а) ақиқаттық кестесі көмегімен;

б) формулаларды эквивалентті түрлендіру көмегімен МДҚФ немесе МКҚФ-ке келтіру арқылы.

        

         Шешуі:

         а)  және   ақиқаттық кестесі:

6 кесте

0

0

0

0

1

1

1

1

0

0

1

0

1

1

1

1

0

1

0

0

1

1

1

1

0

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

0

1

0

0

0

1

0

1

1

0

0

0

1

0

0

1

1

1

1

1

1

1

1

 және  формулаларының баған мәндері тең болғандықтан, бұл формулалар эквивалентті;

б) логикалық қисаптардың белгілі қасиеттерін қолданып, алдымен формуланы  ДҚФ – дизъюнктивті қалыпты формаға, содан соң тарқату заңын пайдаланып мүлтіксіз дизъюнктивті қалыпты формаға (МДҚФ) келтіреміз:

== | 15 | =  = | ДҚФ,10 а | =

== = | 4 | =

=  - МДҚФ;

= = | 15 | = = | 3 | =

= = | 4,10 a | =  =

= |1,10a | = = | 1,4 | =

= - МДҚФ.

Егер ауыстырымдылық  заңды басқаша қолдансақ –  «жақшаны ашпай», ал «жақша сыртына шығарсақ», онда түрлендіру қысқа болады:

= = | 15 | =

= = | 3 | == | 10a | =…=.

         Екі формуланың МДҚФ-ы тең болғандықтан, бұл формулалар эквивалентті.

5. Берілген  функциясы үшін  ақиқаттық кестесін құру керек.

Шешуі:

 функциясы үшін  ақиқаттық кестесі:

7 кесте

0

0

0

1

0

0

1

0

0

1

1

0

1

0

0

1

0

0

1

1

0

0

1

1

0

1

0

0

1

0

0

1

1

0

0

1

0

1

1

1

1

0

1

1

0

0

0

1

0

1

1

1

0

0

0

1

5- тапсырмадағы функция үшін келесі амалдар орындау керек:

   1) ДҚФ-ке келтіру;

   2) ақиқаттық кестесі көмегімен МДҚФ табу керек;

   3) Карно картасын құру керек;

   4) Карно картасы көмегімен минималды ДҚФ;

   5) минималды ДҚФ-тан КҚФ-ке көшу керек;

   6) МКҚФ табу керек;

             7) Карно картасы бойынша минималды КҚФ табу керек.

6.     5- тапсырмадағы функцияны ДҚФ-ке келтіру келтіру керек.

Шешуі:

= | 15,16 | =  = | 6 | =

= =  =

== | 3 | ==

= | 9,3 | =  = | 4,9 | = - ДҚФ (әрі МДҚФ).

         7. 5-тапсырмадағы функцияның ақиқаттық кестесі көмегімен МДҚФ табу керек.

         Шешуі: функцияның ақиқаттық кестесі бойынша оның бірлік жиынтығын жазамыз: . Енді  функциясының баған мәнінде қанша бір болса, МДҚФ-да сонша конъюнкт бар болатындығы белгілі. Әрбір бірлік жиынтығының нөлдері мен бірлеріне  барлық айнымалылардың конъюнктасы сәйкес келеді, мұнда  егер  болса, онда  терістеуімен, ал егер  болса, онда өзгеріссіз жазылады. Сонымен, біздің формуланың МДҚФ-ы екі конъюнкттың дизъюнкциясынан тұрады:  ( таңбасы алынып тасталынған). Айта кетелік, МДҚФ алдыңғы пунктте элементар түрлендіру әдісімен де алынған болатын.

7– 9. 5- тапсырмадағы функцияның Карно картасын құру керек; Карно

картасы көмегімен минималды ДҚФ.

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

8 кесте

1

1

Минималды ДҚФ алу үшін тік және көлденең жолдарда қатар тұрған бірлерді блоктарға біріктіру керек, олар 2, 4 және т.б. ұяшықтардан тұрады (блокқа бұрышта тұрған бірлерді  де біріктіруге болады). Біздің Карно картасында тек екі бірлік бар, олар блокқа бірікпейді, сондықтан Минималды ДҚФ МДҚФ-қа тең: .

10. 5- тапсырмадағы функцияның минималды ДҚФ-тан КҚФ-ке көшу керек.

Шешуі: элементар түрлендіру көмегімен, логикалық қисаптар қасиеттерін пайдаланып (тік жақшада формула нөмірі көрсетілген), формуланы КҚФ-ке түрлендіреміз:

= | 7 | = = | 6 | = =

= | 3 | =

=   = | 9, 8, 6 | =

=  = | 6 | =

=- КНФ.

         11. 5- тапсырмадағы функцияның МКҚФ табу керек.

Шешуі: тарқату заңын қолданып, алдыңғы пунктте алынған КҚФ-ты МКҚФ-ке келтіреміз: 

= | 10a | =

 

= | 1,4 | =

- МКҚФ.

Мүлтіксіз конъюнктивті қалыпты форманы (МКҚФ) айнымалылардың нөлдік жиынтығын қолданып табуға болады. Ол үшін ақиқаттық кестесінен нөлдік жиынтығын теріп жазып аламыз:

=.

Енді,  ереже бойынша ақиқаттық кестесінде  мәндер бағанында қанша нөлдер болса, сонша МКҚФ-те дизъюнкт болады. Әрбір нөлдік жиынтықтың   нөлдері мен бірлерінің орнына келесі дизъюнкт сәйкес келеді: егер  болса, онда айнымалы терісімен, ал егер болса, онда теріске шығарылмай айнымалының өзі алынады. Алынған МКҚФ:  

.

12.            5 -тапсырмадағы формула үшін Карно картасы бойынша минималды

КҚФ табу керек.

Шешуі: минималды КҚФ алу үшін минималды ДҚФ алған сияқты Карно картасын қолдануға болады. Бұл картада айнымалыларды олардың терістеріне айырбастау керек және керісінше; бос жерлерге 0 қойып, 1 алып тастау керек. Немесе Карно картасында МКҚФ-қа сәйкес келетін дизъюнкттерге нөлдер қою керек. Содан соң картада 2, 4 және т.б. көрші нөлдік ұяшықтарды максималды блоктарға біріктіру керек.  Біздің жағдайда екі айнымалылы қысқартылған дизъюнкттерге 2 ұяшықтан 3 блок сәйкес келеді. Айта кетелік, ұяшықтарды қалауымызшы таңдауымызға болады. Біз варианттардың бірін таңдап алдық.

9  кесте

0

0

0

0

0

0

Бұл карта бойынша формуланың минималды КҚФ:

.

12              Берілген сұлба бойынша ауыстырып-қосқыш функциясын құрып, оны қысқарту керек. Қысқартылған функцияның сұлбасын салу керек.

 


Шешуі: берілген сұлба бойынша ауыстырып-қосқыш функциясын құрамыз

.

         Бұл функцияны қысқартамыз (мысалы, элементар түрлендіру әдісі, Карно картасы көмегімен минимизациялау, т.с.с.). Элементар түрлендіру әдісі бойынша:

= | 3 | = = | 5 | =.

         Көрнекілік үшін  таңбасы алынып тасталынған.

Карно картасы көмегімен минимизациялау үшін алдымен МДҚФ алу керек:

 = | 5 | = = | 3 | =  =

= | 10 a | = = | 4 | = - МДҚФ.

         Карно каптасында конъюнкттарды бірлермен белгілейміз, қатар тұрған бірлерді блоктарға біріктіріп минималды ДҚФ аламыз.

10 кесте

1

1

1

1

         Минималды ДҚФ: = |дистрибутивтік заңды қолданып,  айнымалысын жақша сыртына шығарамыз | = .

Қысқартылған формулаға келесі сұлба сәйкес келеді:

 


1.4 Анықтама материалы

Логикалық қисаптар және олардын ақиқаттық кестесі.

         1. Конъюнкция – (), оқылуы  «x  және y».

         2. Дизъюнкция – ( ), оқылуы «x немесе y».

         3. Теріске шығару (инверсия) – (), оқылуы «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

         

          Логикалық қисаптардың орындалу ретінің сұлбасы:  .  Бұл сұлбада қисаптардың таңбасы кему ретімен орналасқан, ал дөңгелек жақшаларда бірдей мәнділері көрсетілген. Логикалық қисаптардың орындалу ретінің сұлбасын былай құруға болады:

Әдебиеттер тізімі

1.Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.

2.Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.

3.Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 2-е изд.  – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).

4.Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: Издательский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.

5.Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.

6.Яблонский С.В. Введение в дискретную математику. – М.: «Высшая школа», 2001.

7.Байсалова М.Ж  Дискрет математика: оқу құралы  – Алматы, АЭжБИ. 2007. - 76 бет.

Мазмұны

1 Типтік есеп № 2. Математикалық логикиа элементтері

3

1.1 Теориялық сұрақтар

3

1.2 Есептік тапсырмалар

3

1.3 Типтік варианттың шешуі

13

1.4 Анықтама материалы

21

Әдебиеттер тізімі

23

        

2014 ж. жиынтық жоспары, реті 212  

Астраханцева Людмила Николаевна
Байсалова Мәншүк Жұмамұратқызы

ДИСКРЕТ МАТЕМАТИКА
Есептеу-сызба жұмыстарға әдістемелік нұсқаулар мен тапсырмалар (5В070400 Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығына арналған) 2 бөлім

Редактор  Қасымжанова Б.С.
Стандарттау бойынша маман Молдабекова Н.К.

Басуға қол қойылды_______
Пішіні 60х84  1/16
Таралымы   500  дана
№1 типографиялық қағаз
Көлемі  1,3  баспа табақ
Тапсырыс______Бағасы  650 тг.

«Алматы энергетика және байланыс университеті»
Коммерциялық емес акционерлік қоғамының
көшірме-көбейткіш бюросы
050013, Алматы, Байтұрсынұлы көшесі, 126