ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ

|ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ                                                 |
|БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ                                              |
|ШӘКӘРІМ атындағы                                                          |
|СЕМЕЙ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ                                            |
|3 деңгейлі СМЖ құжаты   |ПОӘК              |                              |
|                        |                  |ПОӘК 042-14.01.20.205/03-2013 |
|«Дискретті математика»  |02.09.2008 №1     |                              |
|пәніне арналған         |басылым           |                              |
|оқу-әдістемелік         |                  |                              |
|материалдар ПОӘК        |                  |                              |









                      ПӘНДЕРДІҢ ОҚУ-ӘДІСТЕМЕЛІК КЕШЕНІ





                           «Дискретті математика»


                   5В011100 – «Информатика» мамандығы үшін


                         ОҚУ-ӘДІСТЕМЕЛІК МАТЕРИАЛДАР























                                    Семей
                                    2013

                                   Мазмұны



|1    |Дәріс оқулар                                                  |3     |
|2    |Практикалық және зертханалық сабақтар                         |15    |
|3    |Студенттің өздік жұмысы                                       |22    |












































      1 ДӘРІС ОҚУЛАР


      Дәріс сабақтардың құрылымы:


      Дәріс 1


      Дәріс сабақтың мазмұны:

                                   КІРІСПЕ

      ХХ ғасырдың бас кезінде жиын  теориясында  қайшылықтар  табылды.   Бұл
қайшылықтар  математиктерді   қатты  толғандырып,  олардың  алдарына   үлкен
мәселе қойды. Осы мәселені шешу  жолында  математиктердің  алдында  мынандай
сұрақтар туды: «теорема» деген не,  «дәлелдеу»  деген  не?  Немістің  атақты
математигі Д.Гильберт программа  жариялады.  Осы  программа  бойынша  барлық
математиканы былай құру керек:
     1. Математиканың тілін дәл анықтау керек.
     2. Аксиомаларды беру керек.
     3. Дәлелдеудің  дәл анықтамасы берілуі керек.
      Осындай  системаларды  формальдық  система  дейді.  Оларды  зерттейтін
ғылымды  математикалық  логика  деп  атайды.   Гильберттің   ойынша   бұндай
формальдық системада қайшылық деген ұғымды дәл анықтауға,  содан  кейін  бұл
системаның қайшылықсыз екендігін дәлелдеуге  болады.  Математикада  жоғарыда
аталған система құрылып, бұл системалардың қайшылықсыздығын дәлелдеу  қиынға
соқты. Осы айтылған ең негізгі, түйінді  қиыншылық  болып  шықты.  Оны  1931
жылы  Гедельдің  екі  атақты  теоремасы  шешті.  Егер   формальдық   система
қайшылықсыз болса,  онда  бұл  қайшылықсыздықты  осы  формальдық  системаның
ішінде  дәлелдеуге  болмайды.  Бұл,  Д.Гильберт  ойлағандай   болмай,   оның
программасы тұйыққа тірелді. Бірақ бұл  программа  математикада  үлкен  орын
алады.    Формальдық    системалар    математиканың    негізін    зерттеуде,
аксиоматикалық әдістің маңызын зерттеуде елеулі табыстарға жетті.
   Дискретті математика математика аймағының қасиеттерін зерттейді.
     Дискретті  математика   компьютерлік   техниканың   қарқынды   дамуымен
байланысты, яғни ақпаратты тасымалдау мен өңдеу  тәсілдерінің  қажеттігінен,
әртүрлі модельдерді  компьютерде  беруінен  көрінеді.  Бұл  жоғарыда  айтқан
математиканың соңғы сипатындағы сұлбалары.
      Дискретті математика :
    - формальды елестетудің әмбебап тілі;
    - ақпаратты тиімді ауыстыру тәсілі;
    - бір тілден екінші тілге көшкенде модельдің мазмұнды сақтап қалу  шарты
      мен мүмкіндігін береді.


      Дәріс 2 – 3


      Дәріс сабақтың мазмұны:

                       ЖИЫНДАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ

       Жиын  үғымы   басқа   жай   ұғымдар    арқылы   анықтауға   келмейтін
математиканың    ең    алғашқы    қарапайым    үғымдарының    бірі     болып
табылады. Математикада  белгілі  бір  ортақ  қасиеттер  арқылы   шоғырланған
немесе ойымызға біртұтас ұғым туғызатын кез келген топты жиын деп  түсінеді.
Мысалы,  аудиториядағы  студенттер  жиыны,  бүтін   сандар   жиыны,   теңдеу
шешімдерінің жиыны тағы  басқалар  туралы  айтуға  болады.  Жиынды  құрайтын
заттар  немесе объектілердің әрқайсысын жиынның элементі  деп  атайды.
Жиын латын альфавитінің бас әріптерімен А, В, С, ...., ал элементтері  жазба
әріптерімен а, в, с, ...., белгіленеді.
            Элементтерінің саны  нақты  бір  санға  тең  болатын  жиындарды,
ақырлы жиындар деп атайды.
      Элементтер саны ақырсыз көп  болып  келген  жиынды  ақырсыз  жиын  деп
атайды.     Бірде – бір элементі жоқ жиынды бос (құр)  жиын деп атайды.
      Дәріс 4 – 5


      Дәріс сабақтың мазмұны:


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


      Қайталамалы  және   қайталаусыз   орналастырулар.   «m-дік   x   жиыны
элементтерінен ұзындығы k  неше  кортеж  құруға  болады?»  Ізделінді  сан  k
көбейткіштің   [pic]  декарттық  көбейтіндісі  кортеждерінің   санына   тең.
Көбейтінді ережесі бойынша [pic], [pic] болғандықтан [pic].
Анықтама.  m-дік  жиын  элементтерінен  құрылған  ұзындығы   k   кортежі   m
элементтен   k-дан   жасалған   қайталамалы   орналастырулар   деп   атайды.
[pic](arrangement - орналастыру деген француз сөзі).
      «m-дік  Х  жиыны  элементтерінен  реттелген  неше  k-лік  жиын  құруға
болады?»
Анықтама.  m-дік  жиын  элементтерінен  құрылған,  реттелген  k-лік   жиынды
берілген жиынның реттелген  k-лік  ішкі  жиыны  немесе  m  элементтен  k-дан
жасалған қайталаусыз орналастырулар деп атайды.
                                    [pic]
Қайталамалы және қайталаусыз алмастырулар. «m-дік жиынды неше түрлі
тәсілмен реттеуге болады?»
Анықтама. Әр түрлі m элементтен тұратын реттелмеген  жиыннан  алуға  болатын
әр түрлі  m  элементтен  құрылған  шектеулі  реттелген  мүмкін  жиындарды  m
элементтен жасалған қайталаусыз алмастырулар деп атайды. Pm=m!.  (permeation
– алмастыру деген француз сөзі).
Анықтама. Бір құрамдағы әр түрлі  кортеждердің  саны  қайталануы  n1,n2,…,nm
арқылы берілген m элементтен  жасалған  қайталамалы  алмастырулар  саны  деп
аталады.
                                    [pic]
      Қайталамалы  және  қайталаусыз  терулер.  «Берілген  m-дік   Х   жиыны
элементтерінен  әрқайсысы  k  элементтен  тұратын  неше  ішкі  жиын   құруға
болады?».
Анықтама.  Берілген  жиынның  m  элементінен  таңдап  алынған  әр  түрлі   k
элементтен тұратын шектеулі реттелмеген ішкі жиындарды  m  элементтен  k-дан
жасалған қайталаусыз терулер деп атайды.
                                    [pic]
Анықтама. m - дік жиын  элементтерінен  құрылған  k  кортеждердің  әр  түрлі
құрамын m элементтен k –дан жасалған қайталамалы терулер деп атайды.
                                    [pic]
Ньютон биномы.
                                  [pic] (1)
      (1) формуланы Ньютон биномы деп атайды. Мұндағы [pic] -  биноминальдық
коэффициент.

      Дәріс 6 – 7


      Дәріс сабақтың мазмұны:


                              БУЛЬ ФУНКЦИЯЛАРЫ

Анықтама.  Функция  f(x1,…,  xn)  Буль  функциясы  деп  аталады,  егер  оның
аргументтері және өзі екі 0 немесе 1 мәндерін ғана қабылдаса.
      f(x1,…,  xn)  функциясының  аргументтері  x1,…,  xn  белігілі   мәндер
қабылдасын: [pic];  [pic];  ...;  [pic]   осы  мәндердің  белгілі  тәртіппен
реттелуін аргументтер  мәндерінің  құрамасы  деп  атаймыз.  Мәндердің  санын
құраманың  ұзындығы  деп  атаймыз.  Ұзындығы  n–ге  тең   құраманы   былайша
белігілейміз;  [pic].
      Ноль және бірден тұратын құраманы [pic] натурал  санның  [pic]  екілік
системадағы жазылуы деп қарастыруға болады. Бұл жағдайда [pic]  санын  [pic]
құраманың номері деп атаймыз. Номер [pic] мынандай формуламен анықталады:
                                   [pic].
. [pic]формуласын Жегалкин полиномы деп атайды.
       х1,...,хn  аргументтерінен  құралған  кез-келген  Жегалкин  полиномын
былай жазуға болады:
                                   [pic].
Бұл жерде [pic] . Яғни полиномға кірсе 1, басқа жағдайда 0 болады.
Теорема.  Кез-келген  f(x1,…,xn)   функциясы   үшін   оны   реализациялайтын
Жегалкин полиномы бар болады және мұндай полином біреу ғана.
Мысалы.  [pic]

             Функциялар системасының толықтылығы мен тұйықтылығы
      Р2 символымен барлық Буль функциялар жиыны белгіленсін.
Анықтама. Р2 жиынының ішкі  жиыны  болатын  система  P={f1,…,fs}  толық  деп
аталады,  егер  әрбір  Буль  функциясы  Р  системасы  үстіндегі   формуламен
реализацияланатын болса.
Мысал. [pic] системасының толық  екендігін  көрсетейік.  Ол  үшін  кезкелген
f(x1,…,xn)  фукнциясын Р жиыны үстіндегі  формуламен  реализацияланатындығын
дәлелдеуіміз керек. Мынандай екі жағдай болуы мүмкін:
   1)  f(x1,…,xn)=0.  бұл   жағдайда   f   функциясын   [pic]   формуласымен
      реализациялаймыз.
   2) f(x1,…,xn)  ≠0  мұндай  функциялар  үшін  мүлтіксіз  ДҚФ  бар  болады.
      Мүлтіксіз ДҚФ Р жиыны үстіндегі формула.
      Анықтама. Р системасының тұйығы деп осы жиынның  үстіндегі  формуламен
реализацияланатын барлық Буль функцияларының жиынын айтамыз. [P]  символымен
Р системасының тұйығын белгілейміз.
      Тұйықтың мынандай қасиеттері бар:
1. [pic]    2. [[P]]=[P]     3. егер[pic], онда [pic]
Анықтама. Р класы тұйық деп аталады, егер [P]=P болса.
Анықтама. Р класы толық деп аталады, егер [P]=P2 болса.
                     Өзіне-өзі қосалқы функциялар класы.
Анықтама. f   функциясын  өзіне-өзі  қосалқы  функция  дейміз,  егер  f*=  f
болса.[pic] және [pic] қарама-қарсы құрамалар деп атаймыз.
Анықтама. f  функциясы өзіне-өзі қосалқы  деп  аталады,  егер  ол  кезкелген
қарама-қарсы құрамалар жұбында қарама-қарсы мән қабылдаса.
       Функцияның   өзіне   өзі   қосалқылығын   тексеру   үшін   f(x1,…,xn)
функциясының мәндер құрамасын табамыз.  Табылған  құрамадағы  бірді  нольге,
нольді бірге ауыстырып,  шыққан  құраманы  180  градусқа  бұрамыз.  Осылайша
алынған құрама  тексеріліп  отырған  функцияның  мәндер  құрамасымен  бірдей
болса, f(x1,…,xn)  функциясы өзіне-өзі қосалқы болады.
      Дәріс 8 – 9


      Дәріс сабақтың мазмұны:



                            АЙТЫЛЫМДАР АЛГЕБРАСЫ

      Функцияларды   аргументтері   бойынша   жіктеу.   Дизъюнктивті    және
конъюнктивті нормальды формалар. (х1,…,хn) – логикалық айнымалылардың  жиыны
болсын. ∆=(δ1,…,δn) – бір  мен  нольдің  жиынтығы.  Конституентті  бірлердің
жиынтығы  ∆  конъюнкт  деп  аталады   К-1(δ1,…,δn)=   [pic].   Конституентті
нольдердің жиынтығы ∆ дизъюнкт деп аталады К0(δ1,…,δn)= [pic].  Сонымен,  К-
1(δ1,…,δn)=1 (К0(δ1,…,δn)=0) болады сол жағдайда, егер х1=δ1, …, хn=δn.
       Мүлтіксіз  ДҚФ  деп  құрамалары  бірдей  емес  конституент  бірлердің
дизъюнкциясын айтамыз,  ал  МКҚФ  деп  құрамалары  бірдей  емес  конституент
нольдердің конъюнкциясын айтады. Сонымен,  МДҚФ  (МКҚФ)  деп  отырғанымыздың
өзі ДҚФ (КҚФ), яғни әрбір конъюнкт (дизъюнкт) {х1,…,хn} құрамасындағы  әрбір
айнымалы хi үшін бір рет қана  кездеседі,   хi  өзі  немесе  оның  терістеуі
[pic].
      Берілген эквивалентті φ формуласының МДҚФ және МКҚФ табу үшін,  булдік
функция f(х1,…,хn) к айнымалыға жіктеп аламыз (дәл нақтылық үшін х1,…,хк)  -
Шеннон жіктеуі .
      Теорема (Шеннонның  бірінші  теоремасы).  Кез-келген  f(х1,…,хn)  буль
функциясын Шеннон жіктеуі түріне келтіруге болады:
[pic]Дәлелдеуі.  Ең  алдымен,  [pic]  байқаймыз.  к  айнымалылардың   орнына
кезкелген мәндерін қоямыз: [pic].  Сонда  дәлелдеп  отырған  формуланың  сол
жағы [pic]тең болады. Оң жағы 2к дизъюнкцияның  конъюнкциясы  түріне  келеді
[pic], сонда  осылай  ауыстыру  қойғанда  екі  класқа  бөлінетіні  көрінеді.
Бірінші класқа конъюнкция жатады,  оның  [pic]құрамасы   [pic]құрамамен  дәл
келеді:
      [pic]
      Бұл  конъюнкция  формуланың  сол  жағына  тең.  Екінші   класқа   2к-1
конъюнкциялар жатады, олардың әрбіреуінің ең болмағанда бір хi,  i∈{1,2,…,к}
айнымалысы үшін [pic]шарты орындалады. Яғни, олардың әрқайсысы  нольге  тең.
а(0=а заңын пайдалансақ, формуланың  оң  жағы  да  сол  жағы  да  кез-келген
ауыстыруда тең болатыны шығады
Теорема (Шеннонның екінші теоремасы). Кез-келген f(х1,…,хn) буль  функциясын
Шеннон жіктеуі түріне келтіруге болады:
[pic] Бұл жағдайда, егер  k=n  болғанда  нольге  тең  емес  f(х1,…,хn)  буль
функциясы үшін, мүлтіксіз ДҚФ төмендегідей түрде аламыз:
      [pic]
тура  осындай  жолмен  бірге  тең  емес  f(х1,…,хn)  буль  функциясы   үшін,
мүлтіксіз КҚФ төмендегідей түрде аламыз:
[pic]
жоғарыда алынған формулалардан келесі теорема қортылып шығады.
      Теорема (функцияның  толықтығы  туралы  теоерема).  Кезкелген  f  буль
функциясы үшін f функциясын беретін ( формуласы  табылады.  Егер  f(0,  онда
МДҚФ болатын φ формуласы табылады:
      [pic],
егер f(1, МКҚФ болатын φ формуласы табылады:
      [pic].
      Мысалы. f(x,y,z) функциясы үшін ақиқат кестесі  арқылы  берілген  МДҚФ
және МКҚФ табу керек.


      x00001111y00110011z01010101f(x,y,z)10010101
Функцияның толықтығы туралы теоремадан МДҚФ түрі [pic], ал МКҚФ [pic] болады.
МДҚФ табудың алгоритмі.  Берілген формуланы ДҚФ келтіреміз, содан кейін оның конъюнкцияларын бірлік конституентке төмендегідей ауыстырамыз:
1) егер конъюнктке айнымалы өзінің терістеуімен бірге кірсе, онда оны ДҚФ құрамынан алып тастаймыз;
2) егер конъюнкт құрамында хδ литері бірнеше рет қайталанса, онда хδ литерінің біреуін ғана қалдырып, қалғандарын жоямыз;
3) егер қайсыбір [pic] конъюнкт құрамына у айнымалы кірмесе, онда ол конъюнктті [pic]эквивалентті формулмасымен  ауыстырамыз,  дистрибутивті заңды пайдаланып, шыққан формуланы ДҚФ келтіреміз; егер жетпейтін айнымалылар саны бірнешеу болса, онда оның әрқайсысы үшін [pic] түріндегі формуланы конъюнктке қосамыз;
4) егер шыққан ДҚФ бірнеше бірдей бірлік конституент болса, онда оның біреуін ғана қалдырамыз. 
 Нәтижесінде МДҚФ шығады.
Мысал. ДҚФ [pic] үшін МДҚФ табамыз.  Сонда:
[pic]Жегалкин полиномы. Анықтама. хі1∙хі2∙∙∙хіr – түріндегі логикалық көбейтінді монотонды элементарлық конъюнкция деп аталады, егер оның құрамына кіретін аргументтер бір-бірінен өзгеше болатын болса. МЭК құрамындағы аргументтердің саны оның рангісі деп атайды. 1-ді рангісі 0-ге тең МЭК деп атаймыз. 
Дәріс 10 – 12

Дәріс сабақтың мазмұны:


ПРЕДИКАТТАР  АЛГЕБРАСЫ

 Предикаттар логикасында жай сөйлемдер жіктеледі. Мысалы f(x) – үзіліссіз функция. Егер осы f(x) функцияның орнына берілген бір функцияны алсақ, онда осы қасиет бұл функцияға не орындалуы не орындалмауы мүмкін. 
Анықтама 1. А жиыны берілсін. Егер берілген бір заңдылық бойынша А-ның әрбір элементіне сәйкес не «1» не «0» қойылса, онда А жиынында 1-орынды предикат анықталған дейміз. Бір орынды предикаттарды P(I), R(I), …, P1(I), R1(I), …, P2(I), R2(I), … деп белгілейміз. 
 Анықтама 2. А жиыны берілсін. Осы жиынның кез келген Р бөлігін 1-орынды предикат дейміз. Егер аєР, онда а элементі Р предикатты қанағаттандырады дейміз және Р(а) деп жазамыз. Ал, егер а¢Р, онда а элементі Р предикатты қанағаттандырмайды  және ¬Р(а) деп жазамыз.
 Анықтама 3. А жиыны берілсін. Егер берілген бір заңдылық бойынша кез келген (а; b)єА2 элементіне сәйкес не «1» не «0» қойылса, онда А жиынында 2-орынды предикат анықталған дейміз. Бір орынды предикаттарды P(2), R(2), …, P1(2), R1(2), …, P2(2), R2(2), … деп белгілейміз. 
 Анықтама 4. А2 жиыны берілсін. Осы жиынның әрбір бөлігі А жиынында анықталған 2-орынды предикат дейміз. 
 Реттелген (а1, а2, …, ап) тізбектер қарастырайық. Мұнда а1є А1, а2 є А2, …, апє Ап. Барлық осындай тізбектердің жиынын  А1, А2, …, Ап жиындарының тік көбейтіндісі болады. Егер А1,=А2= …= Ап=A, онда А×А×...×А жиынын А-ның тік n дәрежесі дейміз және Ап деп жазамыз. 
 Анықтама 5. А жиыны берілсін. Егер берілген бір заңдылық бойынша кез келген (а1, а2, …, ап)є Ап элементтеріне сәйкес не «1» не «0» қойылса, онда А жиынында n-орынды предикат анықталған дейміз.
Кванторлар
Жалпылық кванторы. P(x) бас айнымалысы x бойынша предикаты болсын.  [pic]xP(x)  өрнегі ақиқат сөйлем егер P(x)  айнымалы x –тің барлық мүмкін болар мәнін қабылдағанда, P(x)  предикаты тепе-тең ақиқат болғанда ақиқат болатын сөйлемді түсінеміз. Енді [pic]xP(x)  сөйлемі x  -тен тәуелсіз болды. P(x)  предикатының сол жағына тіркеп жазылатын [pic]x  белгісі жалпылық кванторы деп аталады. 
Табылу кванторы. P(x) бас айнымалысы x–тен тәуелді предикат болсын. [pic]xP(x)  өрнегі P(x)  айнымалы x –тің ең болмағанда бір мәні үшін ақиқат мәнін қабылдағанда, P(x)  предикаты ақиқат болатын сөйлемді түсінеміз.
Предикат формулалары. Логика заңдары
Анықтама. Элементар формула деп предикат символдан оған кіретін x,y,z,... айнымалылардың орнына міндетті түрде әртүрлі емес заттың айнымалыларына қойған нәтижесінде алынатын өрнекті айтамыз.
Предикаттық формулалар. Предикаттық формулалар келесі амалдар арқылы енгізіледі:
а) кез келген элементарлық формула предикаттық формула болады.
ә) Егер А және В предикаттық формулалар болса, онда (¬А), [pic]предикат формулалар. Егер А предикат формула және х заттық айнымалылары болса, онда [pic]предикат формулалар.
б) Ереже предикат формула болады, сол жағдайда егер ол элементар формула болса немесе тізбектен а), ә) пунктінен қолданған элементарлық формулалардан құралса.
Анықтама. Предикаттық формулаға кіретін элементарлық формулалардың орнына кез келген предикат қойғанда нәтижесінде тепе-тең ақиқат предикат болатын предикаттық формула ортақ мәндес предикаттық формула деп аталады.
Анықтама. Предикаттық формулаларға кіретін элементарлық формулалардың орнына кез келген предикат қойғанда нәтижесінде мәндес предикаттар болатын предикаттық формулалар мәндес деп аталады. [pic]
Предикат логикасының заңдары. Предикаттар логикасында маңызды роль атқаратын бірқатар ұқсастықтарды қарастырайық. 
[pic].  (1)
 «[pic] объектісінің А(х) шартын қанағаттандырады деген дұрыс емес» және «А(х) шартын қанағаттандырмайтын объект х табылады» деген сөйлемдердің мәні бір екендігін (1) ұқсастық көрсетеді.
[pic].  (2)
«А(х) шартын қанағаттандыратын х объектісі табылатыны дұрыс емес» деген сөйлемді «Ешбір х объектісі А(х) шартын қанағаттандырмайды» деген қос терістеу заңына сүйене отырып (1) мен (2)-нің екі жағына да терістеу амалын қолдансақ, нәтижесінде
[pic].    (3)
[pic].    (4)
Бұдан біз жалпылық кванторын табылу кванторы арқылы және керісінше табылу кванторы жалпылық кванторы арқылы көрсетуге болатынын көреміз.
Келесі екі ұқсастық конъюнкцияға қатысты жалпылық кванторының дистрибутивтік қасиетін және дизъюнкцияға қатысты табылу кванторының дистрибутивтік қасиетін көрсетеді.
[pic].  (5)
[pic].  (6)


 Дәріс 13– 15 

Дәріс сабақтың мазмұны:

ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ


Графтардың түрлері мен берілу тәсілдері. Көптеген қолданбалы есептерде әртүрлі объектілер арасындағы байланыс жүйесі  қарастырылады. Міне  осындай шектеулі математиканың мәселелерін шешуге геометриялық тұрғыдан келу графтар теориясы деп аталады. Ең алғаш рет «граф» терминін венгер математигі Д.Кениг енгізген. Ол нүктелер жиынынан және осы нүктелерді байланыстыратын түзулер кесінділері мен қисықтардан құрылған схемаларды граф деп атады. 
Жазықтықта әртүрлі бес A, B, C, D, E нүктелерін белгілейік. Осы нүктелерді графтың төбелері, ал оларды қосатын сызықтарды (түзу немесе қисық) графтың қабырғалары деп атайды. 
Бұл графты A, B, C, D, E нүктелерін қосатын сызықтар осы нүктелерден басқа ешбір нүктелерде қиылыспайтындай етіп те кескіндеуге болады. Қабырғалары тек төбелерінде ғана қиылысатын графты жазық граф деп атайды.
Төбенің дәрежесі.
 G бағытталмаған графы берілген, а төбесінің дәрежесі немесе валенттілігі деп а төбесі қабырғаларының ұшы болатын қабырғалардың санын айтамыз (ілмек екі рет есептеледі). а төбесінің дәрежесін degGa немесе dega деп белгілейміз. Дәрежесі 0 тең төбе – оқшауланған (изолированный), 1 тең болса – соңғы немесе аспалы (висячей) д.а. 
Қол алысу туралы лемма. Графтың барлық төбелерінің дәрежесінің қосындысы жұп сан болады және қабырғаларының екі еселенген санына тең.
G – бағытталған граф. а төбесінен шығатын жарты дәрежесі deg+a а төбесінен шығатын доғаның санына тең.  а төбесіне кіретін жарты дәрежесі deg-a а төбесіне кіретін доғаның санына тең.  Сонда dega= deg+a+ deg-a.
Математик, механик Л.Эйлер байланысқан бағытталмаған  мультиграфта оның барлық қабырғаларынан тұратын цикл болатынын тұжырымдап берді.  Мультиграфтың барлық қабырғаларынан тұратын цикл Эйлерлік д.а.
 Теорема. Байланысқан бағытталмаған мультиграф Эйлерлік болады сол жағдайда, егер оның әр төбесінің дәрежесі – жұп сан болса.
Эйлерлік мультиграфта эйлер циклін табудың алгоритмі:
кез келген а төбені аламыз.
а төбесіне инцидентті  кез келген u қабырғаны алып, оған 1 номер береміз (бұл қабырғаны жүрілген д.а.)
әрбір жүрілген қабырғаны сызып, 1 ден артық номер беріп отырамыз.
х төбесінде тұрып а төбесімен қосатын қабырғаны таңдамаймыз, егер басқа мүмкіндік болатын болса.
х төбесінде тұрып, сызылған қабырғаны таңдамау керек.
графтың барлық қабырғасы номерленгеннен кейін эйлер циклі пайда болады. Реттелген номер графтың айналу ретін көрсетеді.
Байланысқан және байланыссыз графтар. Графтағы ешбір қабырға арқылы 1-ден артық рет өтпейтін сызық шынжыр деп аталады. Егер қозғалысты А нүктесінен бастап, барлық төбелерден әр қабырға бойымен тек бір ғана рет жүре отырып, сол А төбесіне қайта оралу мүмкін болса, мұндай жолды цикл деп атайды. Егер циклдың барлық төбелері әртүрлі болса, мұндай цикл қарапайым цикл, ал қарсы жағдайда – қарапайым емес цикл деп аталады. Кей жағдайда цикл графтың барлық қабырғаларын дәл бір реттен қамтиды. Мұндай циклдарды Эйлер сызықтары деп атайды.
 Егер графтың кез келген екі төбелері қандай да бір шынжырмен байланысып тұрса, ондай графты байланысты граф дейді, яғни байланысты граф дегеніміз бірде бір оқшауланған нүктесі болмайтын граф. 
 Егер графтың ең болмағанда екі төбесін қосатын жол болмаса, оны байланыссыз граф деп атайды, яғни оның қандай да бір төбесінен шығып, басқа төбелеріне қабырғаларының ешқайсысынан бір рет қана өте отырып бару мүмкін болмайды.
 Байланысты графтың қасиеттері:
1. кез келген байланысты графтың дәрежелері тең болатын ең болмағанда екі төбесі бар болады.
 2. барлық төбелерінің дәрежелері жұп болатын байланысты граф Эйлер сызығы болып табылады.
 3. байланысты графта оның барлық қабырғаларын дәл бір реттен қамтитын l(A, B) шынжыры бар болуы үшін А мен В төбелерінен басқа тақ дәрежелі төбелердің болмауы қажетті және жеткілікті.
 Барлық қабырғаларының бағыты көрсетілген граф бағдарланған граф деп аталады. Қабырғаларының бағыты көрсетілмеген графты бағдарланбаған граф дейді. Кей қабырғаларының бағыты бар, ал кей қабырғаларының бағыты көрсетілмеген графты аралас граф дейді.
 Ұштарындағы нүктелері беттесетін қабырғаны тұзақ деп атайды. Графты кескіндеу барысында тұзақ сол төбеге қайтып келетін және басқа төбелерден өтпейтін тұйық доға түрінде болады.



ПРАКТИКАЛЫҚ САБАҚТАР


Практикалық сабақтардың құрылымы:
Практикалық сабақтар 1 (5)

Практикалық сабақтардың мазмұны:

1. Доказать, что {(} [pic]((.
2. Доказать, что {{0,1}, {0, 2}} ({0,1,2}.
3. Доказать, что [pic]
4. Построить пример множеств А и В таких, что АхВ(ВхА.
5. Пусть [0,1], [0,2] - отрезки на числовой прямой. Дать геометрическую интерпретацию множеств [0,1]х[0,2], [0,1]2, [0,2]3.
6. Изобразить отношения Р={(а, 1), (а, 2), (b, 2), (b,3), (с, 1), (с. 4)} и Q = {(1,[pic]), (2,[pic]), [pic](3,а)}. Найти[pic]Q, рQ и Р о Q.
7. Для отношений Р={(х,у) € R2|x =у2} и Q={(х,у)€ R2|ху>0} найти Р о Q, Q о Р, Р о Р и Р-1.
8. Пусть А и В - конечные множества мощности m и n соответственно. Найти:
а) число бинарных отношений между элементами множеств А и В, б) число функций из А в В; в) число инъекций из А в В; г) число биекций из А в В.
9. Доказать следующие эквивалентности:
а)  А х В ~  В х А;      б) (А х В)с ~ Ас х Вс.[pic]
10. Доказать, что:
а) если А - конечное множество, В - подмножество множества А, то множество В конечно;
б) если A1….. Аn - конечные множества, то множества А1U... U Аn и A1х ... хАn конечны.


Практикалық сабақтар 2 (4)

Практикалық сабақтардың мазмұны:


1.По вкусу мороженое бывают ванильные и шоколадные. По размерам они бывают большие, средние и маленькие. Сколько типов мороженных  существуют?
2. На кафедре математики работают 13 преподавателей. Докажите, что найдутся два преподавателя, которые родились в один и тот же месяц.
3. Шахтеры раздобыли 100 брикетов руды, содержащие железо, свинец и олово. Оказалось, что брикеты содержащее железо обязательно содержит и свинец, 60 брикетов содержат олово и 50 брикетов содержат железо и олово. Сколько брикетов содержит железо?
4. Группе из пяти сотрудников выделено три путевки. Сколько существует способов распределения путевок, если:
а) все путевки различны; б) все путевки одинаковы?
5. Сколько различных десятизначных чисел можно написать, используя цифры 0, 1 и 2?
6. Автомобильные номера данного региона состоят из трех цифр (всего 10 цифр) и трех букв алфавита X = {А, В, С, D, Е, Н, К, М, О, Р, Т, X, Y}. Сколько автомобилей может быть занумеровано различными номерами?
7. Докажите, что сумма  кубов n последовательных целых чисел является полным квадратом.
8. Число Фиббоначи делится на 3 тогда и только тогда, когда его номер делится на 4. 

Практикалық сабақтар 3 (4)

Практикалық сабақтардың мазмұны:


1. Составить таблицу истинности формулы
                                  х [pic]→[pic]( х|[pic][pic][pic].
2. Доказать тождественную истинность формулы
[pic] →(х→  у).

[pic]
3. Доказать эквивалентность
x [pic] ( x V z) [pic]  (у V z) ~ (x [pic] у) V (x  [pic] z).

4. Привести к ДНФ, КНФ. СДНФ и СКНФ формулу

                                 ([pic][pic](у V z))→ (х [pic] у)V z.

5. Используя метод Квайна и карты Карно, найти МДНФ и МКНФ формулы

                                [pic]V [pic]у[pic] V [pic]yz V x[pic]z V xy[pic].

6. Найти СДНФ и МДНФ по карте Карно, изображенной на рис. 6.30.

7. Найти СКНФ и МКНФ по карте Карно, изображенной на рис. 6.31.

8. Найти полином Жегалкина для булевой функции ƒ,  заданной вектором значений (1011 0100). Определить, каким классам Поста принадлежит функция ƒ.
9. Проверить с помощью теоремы Поста полноту следующих систем булевых функций:
а) {→,¬}; б) {↔,[pic]}: в) {(}; г) {[pic],→}. Какие из указанных систем образуют базис



Практикалық сабақтар 4 (5)

Практикалық сабақтардың мазмұны:

1. Какие из следующих выражений являются высказываниями:
а) кислород-газ;
б) я живу в городе Саратове;
в) снег белый;
г) белый снег;
д) [pic];
е) [pic]
ж) [pic]

2. Является ли высказыванием следующее предложение:
«Это предложение ложно»?
3. Пусть [pic] и [pic] обозначают высказывания:
[pic] –– я учусь в школе;
[pic] –– я люблю математику.
 Прочтите следующие символические выражения:
а)  [pic]
б) [pic]
в) [pic]
г) [pic]
д) [pic]
е) [pic]
ж) [pic]

4. Следующие сложные предложения расчлените на простые и запишите с помощью логической символики:
а) эта ночь темная и ветреная,
б) эта ночь темная,  но не ветреная,
в) этот четырехугольник квадрат или ромб;
г) Коля и Наташа решили задачу;
д) автором этой книги является Петров или Степанов;
е) или эту книгу написал Петров, или я не знаю, кто ее автор;
ж) это ни необходимо, ни желательно.

5. Какие из следующих импликаций истинны:
а) если [pic] то [pic]
б) если [pic] то [pic]
в) если [pic] то [pic]
г) если [pic] то [pic]

6. Прочтите следующие символические выражения:
а) [pic]
б) [pic]
в) [pic]
г) [pic]
д) [pic]
е) [pic]
ж) [pic]
з) [pic]

7.Проверить следующие тождества:
а) [pic]
б) [pic]
в) [pic]
г) [pic]
д) [pic]
е) [pic]
ж) [pic]
з) [pic]
е) [pic]
з) [pic]
и) [pic]
к) [pic]
л) [pic]
м)  [pic]
н) [pic]
р) [pic]
с) [pic]

8. Упростить выражения:
а) [pic]
б) [pic]
в) [pic]
г) [pic]
д) [pic]

9. Упростить выражения:-
а) [pic];
б) [pic];
в) [pic]
г) [pic]
д) [pic]
е) [pic]

10.Найти [pic] и [pic] из уравнений:
а) [pic]
б) [pic]

11.Доказать, что следующие формулы являются тавтологиями:
а) [pic];
б) [pic];
в) [pic]
г) [pic]
д) [pic]
е) [pic]
ж) [pic]
з) [pic]
и) [pic]
к) [pic]
л) [pic]

12.Проверить, какие из следующих формул являются тавтологиями:
а) [pic]
б) [pic]
в) [pic]
г) [pic]
д) [pic]
е) [pic]
ж) [pic]

13.Привести примеры доказательств, основанных на тавтологиях:
[pic]
[pic]
[pic]
[pic]

14.Привести пример доказательства, основанного на тавтологии:
[pic]

15.Для данной формулы найти более простую равносильную формулу: 
а) [pic]

16.Для следующих пф построить днф  и из них, если возможно, получить сднф: 
а) [pic]  б) [pic]  в) [pic]  
г) [pic] д) [pic] 
е) [pic]

17.Для следующих пф построить кнф и из них, если возможно получить скнф:
а) [pic]  б) [pic]  в) [pic] 
г) [pic]  д)  [pic] 
 е) [pic]  ж) [pic]

18.Упростить следующие нормальные формы:
а) [pic]  б) [pic] 
в) [pic]  г) [pic]
д) [pic]
е)  [pic] 
ж) [pic]
з) [pic]

Практикалық сабақтар 5 (4)

Практикалық сабақтардың мазмұны:

1. Состоялся розыгрыш футбольного кубка между командами "Пламя", "Рекорд", "Стрела" и "Трактор".Было высказано три прогноза: победит "Пламя" или "Рекорд"; не победит "Пламя"; не победит ни "Рекорд", ни "Трактор". Известно, что подтвердился только один прогноз. Какая команда выиграла кубок?
2. Пусть ƒ(1),q(2),h(3) - функциональные, P(1),Q(3) - предикатные символы. Являются ли формулами следующие слова:
а)  P(f(x)) [pic] [pic]x ¬Q(q(y,z),x ,h(z,y,x));
б)  P(Q(x,q(x,y),h(x,y,z)));
в)  h(x,q(x,y),f(x))?
3. Выписать все подформулы формулы:
a) Q(x,q(x,у), h(x, у, z));  
б) ([pic]x ¬Р(x) →¬ [pic]у ([pic]zP(x) [pic]Q(x, у, z))).
4. Перечислить свободные и связанные вхождения в следующих формулах:
а) [pic]x (Р(х,у) (¬[pic]уQ(x,y));
б) (¬[pic]x P(x,y)→Q(f(x,y))).[pic]
Доказать выполнимость формулы
[pic]
Доказать тождественную истинность формулы
[pic]
Привести к ПНФ формулу
[pic]



Практикалық сабақтар 6 (4)

Практикалық сабақтардың мазмұны:

Является ли схема алфавитного кодирования префиксной? разделимой?
(a(0, b(10, c(011, d(1011, e(1111 (
2. Построить оптимальное префиксное алфавитное кодирование для алфавита {a,b,c,d} со следующим распределением вероятностей появления букв:
pa=1/2, pb=1/4, pc=1/8, pd=1/8/



Практикалық сабақтар 7 (4)

Практикалық сабақтардың мазмұны:

1. Представить граф (рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности. 
2. Составить матрицу инцидентности для мультиграфа, изображенного на рис.  4.51. 





3. Найти все неизоморфные подграфы и части графа К3
4. Представить в геометрической и матричной формах графы G1 UG2, G1 ( G2    G1  [pic] С2 (рис. 4.52).
5. Для графов G1 и G2 из  предыдущей задачи найти G1 x G2,G1   [G 2] и G2 [G1].
6. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы достижимости, контрдостижимости и сильных компонент.
7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.
8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа (рис. 4.55).
9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой степенью исхода и с нулевой степенью захода
10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:
а) графа К5; б) графа, изображенного на рис. 4.56.
[pic]

3 СТУДЕНТТІҢ ӨЗДІК ЖҰМЫСЫ

3.1 СОӨЖ
Условия задач
1. Докажите тождества, используя только определения операций над множествами.
2. Докажите методом математической индукции.
3. А={a,b,c}, B={1,2,3,4}, [pic]. Изобразите Р1, Р2 графически. Найдите [pic]. Проверьте с помощью матрицы [P2], является ли отношение Р2 рефлексивным, симметричным, антисимметричным, транзитивным?
4. Найдите область определения, область значений отношения Р. является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным?
5. Проверьте двумя способами, будут ли эквавалентны следующие формулы …
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
6. С помощью эквивалетных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.
7. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f(x,y,z)  двумя способами:
а) методом Квайна; б) с помощью карт Карно.
Каким классам Поста принадлежит эта функция?
8. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ, КНФ булевой функции f(x1, x2, x3, x4), заданной вектором своих значений.
9. Даны графы G1 и G2. Найдите [pic]. Для графа G1[pic]G2 найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.
10. Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?
11. Является ли полной система функций? Образует ли она базис?
12. С помощью алгебры логики проверьте истинность соотношения для любых множеств А, В, С. 
13. С помощью алгебры логики докажите тождества из задания 1.

Вариант 1
1. А [pic](В U С) = (А[pic]В) U (А[pic]С), 
     А х (В U С) = (А х В) U (А х С).
2.  7n- 1 кратно 6 для всех n [pic] 1.
3.    Р1 = {<а,1> <а,2>,,<с,2>,<с,3>,<с,4)},
       Р2 = {<1,1>, <2,1>, <2, 2>, <2,3>, <2,4>, <3,3>, <4, 4>}.
4. Р [pic]R2, <х, у>[pic]Р [pic]x2 + у2 = 1.
5. x →  (у [pic] z) и (x→у) [pic] (х → z).
6. (x( [pic]) →([pic][pic]).
7. ƒ(0,1,0)=ƒ(1,0,0)=ƒ(1,0,1)=0.
8. (1101 1101 0011 0011).
[pic]
11. [pic] = {х( у, [pic] [pic]}.
12. (А U В) \ (С[pic]А) = (В \ С) \ (A U С).

 
Вариант 2
1. AU(В[pic]С) = (A U В)[pic](A U С),
(AUВ) х С = (А х С) U (В х С).
2. n2 + 11 n кратно + 6 для всех n [pic].
3. Р1={<а,1>,<а,2>,<а,3>,<а,4>,,<с,2>}.
    Р2 = {<1,1>, <1,4>, <2,2>, <2,3>, <3,3>, <3,2>, <4,1>, <4,4>}.
Р [pic] R2,  (x, у( € Р [pic] x• у > 1.
5. x|(y→ z) и (x|у) → (x|z).
6. [pic].
7. ƒ(0,1,1) =ƒ(1,0,0) =ƒ(1,1,0) =0.
[pic]
8. (1111 1100 1011 1011).
11. [pic].
12. (A U B) \ (С [pic] B) = (A \ С) U (A \ B).
Вариант 3 
1. А [pic] В = ([pic]),
          А х (В\С) = (А х В)\(А х С).
2. 1·4 + 2·7 + 3·10+ ••• + n(3n + 1) = n(n+ 1)2.
3.   Р1 = {<а, 1>, <а, 2>, <а, 4>, <с, 3>, <с,2>, <с,4>},
      Р2 = {<2,1>, <3,1>, <3,2>, <4,1>, <4,3>}.
4. Р [pic] R2 , (х, у) [pic] Р [pic]у = │х│.
5.  x[pic] и (х [pic]у) [pic] (х [pic]z).
6. ([pic]([pic]) [pic] ([pic]).
7. ƒ(0,0,0) =ƒ(0,0,1) =ƒ (1,0,1) = ƒ(1,1,1) =1
[pic]
8. (1110 0101 0011 0101).

11. [pic] = {х [pic]у,[pic]│[pic]}.
12. (А [pic]С)\(В [pic]А) = (А\В) \ (А [pic] С).


Вариант 4
1.  A\(B [pic] C) = (A\B) [pic](A\C),
     А х (В [pic] С) = (А х В) [pic] (А х С).
2. 10n - 1 кратно 9 для всех n [pic].
3.  Р1 ={<а, 1>, <а, 2>, , , <с, 3>, <с, 2>},
     Р2 = {<1,1>, <1,2>, <2,2>, <3,3>, <4,3>, <4,4>}.
4.  Р [pic] R2 ,(x, у)  [pic] Р [pic]  х2 + х = у2 + у.
5. x [pic] и (х [pic]у) [pic] (х [pic]z).
6. (x ([pic]) → [pic].
7. ƒ(0,0,1) = ƒ(1,1,1)=ƒ(1,1,0)=0.
8. (1101 0011 1101 0011).
[pic]
11. [pic]= {x[pic] у. [pic] (y}.
12. (А [pic] В) [pic]   (А \ С) = А \ (В [pic] С). 

Вариант 5
1. (A [pic]B)\C=(A \ C) [pic] (B\C),
    (А [pic] В) х С = (А х С)[pic] (В х С).
2. 1 • 2 + 2 • 3 + 3 • 4 + ... + n(n+ 1) = [pic]  
3. P1 ={ <[pic],1>,<[pic],4>,,,, },
    Р2 = {<1,1>, <1,4>, <2,1>, <3,4>, <4,3>, <4,1>}.
4. Р [pic] R2 , (x, у) [pic] Р [pic]  х - у [pic] Z.
5. x [pic] (у → z) и (х [pic] у) → (х [pic] z),
6.  [pic].
7. ƒ(0,0,0)=ƒ(1,1.1)=ƒ(1,1,0)=0.
8. (1100 1011 1111 1011).

[pic]
11. [pic] = {[pic] → у, х [pic][pic] }.
12. (А \ В) [pic] (A \ С) = А \ (В [pic] С).
 
Вариант 6
1.([pic][pic] В) = ([pic]),
   (А [pic] (В) х (С [pic]D ) = (А х С) [pic] (В х D).
2.  [pic]
3. P1 = {<α, 1>, <α, 2>, <α, 4>, , , <с, 3>},
    Р2 - {<1,1>, <2,4>, <2,1>, <3,3>, <4,2>, <4,1>}.
4. Р [pic] R2, (x,у) [pic] Р [pic]  x+ y = -2.
5. x[pic](у[pic] z) и (x[pic]у)[pic](x[pic]z).
6. [pic]
7. ƒ(0,0,1) - ƒ(0,1,1) = ƒ(1,1,0) - ƒ(1,1,1) = 1.
8. (0101 0101 1110 0011).

   [pic]
11. [pic]= ([pic]↔ у, х│[pic]}.
12. (А \В )[pic](А\С) = А\(В[pic]С).

Вариант 7.
1. (А \ (В[pic]С) = (А \ В) [pic] (А\С),
    (А \ В) х С=(А х С)\(В хС).
2. [pic][pic] для  n[pic]
3. P1 = {<а, 1>, , , , <с, 3>, <с, 2>},
    Р2 = {<1,3>, <1,4>, <2,2>, <3,3>, <4,3>, <4,4>}.
4. Р[pic] R2,  (x,y( [pic] Р [pic]  x2 + y2 = 4.
5. x[pic](у|z) и (x[pic]y)|(x[pic]z).
6.[pic]
7. ƒ(0,0,0)=ƒ(1,0,1) = ƒ(1,1,1)=0.
8. (0011  0011 1101 1101).

[pic]
11. [pic]={x [pic][pic],[pic]V y}.
12. (А[pic] В) \ (А [pic] С) = А \ (В [pic] С).
 
Вариант 8
1. [pic] = [pic][pic][pic],
    C[pic]D=>A x C [pic]B x D
2. 12 + 22 + 32 + ... + n2 = [pic].
3. Р1 = {<а, 1>, , <с, 1>, <с, 4>, <с, 3>, <с, 2>},
    Р2 = {<1,1>, <1,2>, <1,4>, <2,1>, <2,2>, <2,3> <3,3>,    <3,2>, <3,4>, <4,3>, <4,4>, <4,1>}.

4. Р [pic] R2, (x,у([pic] Р [pic]y < х - 1.
5. x ( (y→z) и (x ( у) → (х (z).
6. (x|[pic]) [pic] ([pic]→x).
7. ƒ(1,0,1) =ƒ(0,1,0) =ƒ(1,1,1) =0.
8. (1011 1011 1100 1111).
[pic]
11. [pic]  = {x →[pic],[pic] [pic]у}.
12. (А \ В) [pic] (A \ С) = А  [pic] (В \ С).

Вариант 9
1. (А∩В)\С = (А\С)∩(В\С),
   (А ×В) U (С × D) С (A U С) × (В U D).
2. [pic]   для  n[pic]2.
3.  Р1 = {(а,1},{а,2),(а,4),(b,3),(с,1),(с,4)}
     Р2 = {(1,3), (1,2), (2,3), (3,2), (3,4), (4,1)}
4. Р [pic] R2, (х, у) [pic]Р [pic] х2 = у. 
5. х ( ( у|z ) и (x( у)|(x(z).
6. ([pic][pic] x ) [pic] (x|у).
7. ƒ (1,0,0) = ƒ(1,1,0) = ƒ (0,1,1) = ƒ(0,1,0) = 1.[pic]
8. (0101 0011 0101 1110).

  [pic]
    
11. [pic]= {х [pic]у, х\у}.
12. (A U В) [pic](A U С) = A U (В [pic] С).

Вариант 10
1. A U (А ∩ В) = А∩ (А U В) = А, 
   (А U В) х (СU D) = (А х С) U (В х С) U (A x D) U (В х D).
2. 1·2 + 2·5 + 3·8 + ...+ n(3n - 1) = n2(n + 1).
3.    Р1 = {(а,3),(а,2),(b,2),(b,3),(с,1},(с,4)},
       Р2 = {(1,1),{1.2),(2,2),(3,3),(4,1),(4,4)}.
4. P [pic] R2, (x,y)[pic]P[pic]x2 [pic]y.
5. х V (у [pic] z) и (х V у) [pic] (х V z).
6. (z [pic]х) [pic] (х|[pic]).
7. ƒ (0,1,1)=ƒ(1.0,0)=ƒ(1,0,1)=0.
8. (0011 1101 0011 1100).

[pic]
11. [pic] = {[pic], xV [pic]}.
12. (А\ В) [pic] (А \ С) = А ∩ (В [pic] С).
 [pic]
Вариант 11
1. (A\B)\C = A \ (B ∩ C),
    А [pic] С , В [pic] D [pic] А х В= (А х D) [pic] (С х В).
2. n2 + 5n  кратно 6 для всех n[pic].
3.  P1={ (а,2),(а,4),(b,3), (с ,1), (с,2)},
     P2 = {(1,1),(1,3),(2,4),(3,1),(3,4),(4,3),(4,2)}.
4. Р [pic] Z2, (х, у) [pic]Р [pic] х2 + у2 = 1.[pic]
5. х [pic]  (у [pic] z) и (х [pic] у) [pic] (х[pic] z).
6.( (х[pic]y)[pic]z )[pic]у.
7. ƒ(0,0.1) = ƒ(1,0,0) = ƒ(1,1,0) = 0.
8. (1011 1111 1011 1100).
[pic]
11. [pic]= {х [pic][pic][pic] у,  х [pic]у}.
12. (А \ В)[pic] (А \ С} = А \ (В [pic] С)

Вариант 12
1. А \ (В \ С) = (А\ В) U (А ∩ С),  
    U2 \ (А х В) = (А х U) U (U х [pic]).
2. 4n - 1 кратно 3 для всех   n > 0.
3. Р1 = {(Ь, 1), (Ь, 3), (с, 1), (с, 2), (с, 3), (с, 4)},
    Р2 = {(1,1), (2,2), (2,3), (2,4), (3,2), (3,3), (3,4), (4,2), (4,3), (4,4)}.
4. Р [pic] Z2, (х, у) [pic] Р [pic] х + у кратно 3.
5.  х [pic] (у [pic] z)  и  ( х [pic] у) [pic] ( х [pic] z).
6.  [pic][pic]y.
7. ƒ(0,0,1)=ƒ(0,1,1) = ƒ(1,1,1)=0.
8. ( 0011  1110  0101  0101).

[pic]
11. [pic] = { [pic]│[pic], [pic] [pic] [pic]}.
12. (A \ B) U (B \ C) = (A U C) \ В.
 [pic]
Вариант 13
1. A U (В \ С) = (A U В) \ (С \ А) ;  А, В ≠ Ø,
   (A [pic]B) U (B [pic]A) = (C [pic]D)=>A = B = C = D.
2. 4n + 15n - 1 кратно 9 для всех натуральных n.
3. Р1 = { [pic], [pic],  [pic],  [pic], [pic], [pic]},
    Р2 = {[pic], [pic], [pic], [pic]}.
4. Р [pic] Z2, (x, y) [pic] Р [pic] х - у кратно 2.
5.  x [pic] (у|z) и (x [pic] у) | (x [pic] z).
6.  [pic][pic]у.
7. ƒ(0,0,0) = ƒ(0.0,1) = ƒ(1,1,0)=0.
[pic]
8. (0011  0011  1100  1111).

11. [pic] = {[pic] [pic]у, [pic] V [pic]}.
12. (А [pic] В) [pic] (В U С) = (А \ В) [pic] С.

Вариант 14
1. А [pic](В \ С) = (А [pic]В) \ (А [pic]С),
    (A x B) [pic](C x D) [pic] (A U C) x (B [pic]D).
2. 11n+1  + 12 2n-1 кратно 133 для всех n > 0.
3.  P1 = {(а, 2), (а. 3), (а, 4), (с, 3), (с, 1), (с, 4)},
     Р2 = { (1,4 ), (2,3), (2,1), (3,4), (4,2)}.
4. Р [pic] Z2, (x , у)  [pic] Р [pic] 2x = 3у.
5.  x[pic](у [pic] z) и ( x[pic]у)[pic]( x[pic]z).
6. ( ( x [pic]у)  [pic] [pic] )  [pic] у.
7.  ƒ(0,0,0)= ƒ(0,1.0) = ƒ(1,1,1)=0.
8. (1100 0101  0011  0011).

[pic]
11. [pic] = {x ٨  у,  x  у}.
12. (A[pic]B) \ (A[pic]C) = A \ (B [pic] С).
 
Вариант 15
1.  [pic]= [pic] [pic] [pic], _ __
     U 2 \ (С [pic] D) = ( [pic] [pic] U)  [pic](U [pic] [pic]).
2. 9n+1  - 8n – 9  кратно 16 для всех  n [pic] 0.
3. P1= [pic], [pic]
    P2 = [pic], 
4. Р [pic] Z2, ( x, у) [pic] Р [pic] х + у  нечетно.
5.  x|(y [pic] z) и ( x │y) [pic] ( x │ z).
6.  [pic]
7.  ƒ (0,0,0) = ƒ (0,0.1) =  ƒ (1,0,0) =  ƒ (1,1,0) = 1.
8. (0010 0111 1010 1101).

[pic]

11. [pic] = {x V y, [pic] [pic]y}.
12. (A \ B) U (B \ С) = (A \ B) U C.

Вариант 16
1. (А [pic] В) [pic] (А [pic]) = (А [pic]В) [pic](А [pic]) = А;
  (A U В) [pic] (С U D) = (A х С) U (В х С) U (A х D) U (B х D).
2. n (2n2 - Зn + 1) кратно 6 для всех натуральных n.
3. P1= { [pic]},
    Р2 = { [pic]}.
4. Р [pic] Z2, (х, у} [pic] Р [pic] х - у четно:
5.  x [pic] ( y | z) и (x[pic] у)|(x[pic]z).
6. [pic][pic] [pic]) [pic]у.
7. ƒ(1,0,1)= ƒ(0)1,1)= ƒ(0,1,0)=0.
8. ( 0011  1111  0011  1100).
[pic]
11. [pic] = {x  [pic] у, x V [pic]}.
12. (А \ В) U (А [pic] С) = А \ (В U С) 

 Вариант  17
1.(А \ В) \ С =(A \ B ) \ ( B \ C);
   A [pic] B, C [pic] D[pic] A [pic] C [pic] B [pic] D
2. [pic] +[pic] +[pic] +... + [pic]= [pic].
3. P1 ={[pic], [pic], [pic],[pic]}.
4. P [pic] Z2 , [pic] [pic] P [pic] 5x = 2y.
5. x[pic](y [pic]z) и (x [pic]y)[pic](x[pic]z).

6. (((x v y) [pic] ([pic][pic]y)).
7. ƒ (1,0,0) = ƒ (0,1,1) = ƒ (0,1,0) =0.[pic]
8. (0101 0011 1100 0011).
[pic]
11. [pic]= [pic], [pic][pic][pic][pic]
12. (A [pic] B) \ ( B [pic] C) = A [pic] (B \ C).

Вариант 18
1.   А [pic] (В [pic]С) = (А [pic] В) [pic] С,
      ( А \ В ) х С = ( А х С ) \ (В х С).
2. n5 – n  кратно 5 для всех натуральных n.
3. P1 = { [pic]},
    Р1 = {[pic] }.       
4. Р [pic] Z2, (x, у) [pic] P [pic]х = - у.
5. xV (у[pic]z) и (xVу)[pic] (xVz).
6. [pic]
7. ƒ (0,0,1) = ƒ (0,1,1) =  ƒ (1,0,0) = ƒ (1,0,1) = 1.
8. (0111 1101 0010 1010).
[pic]
11. [pic] = [pic], [pic] [pic][pic].
12. (A U B) \ (A U С) = A [pic] (В U С).

 
Вариант 19
1. А [pic]В = ([pic] [pic] В)  [pic]А,
   (А [pic] В) [pic] (С [pic] D) = (А х С) [pic] (В [pic] D).
2. 62n-1 +1   кратно 7 для всех n [pic] 1.
3. Р1 = {(а, 1), (b,2), (Ь,3), (с. 1), (с,3), (с, 4)},
    Р2 = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(3,4),(4,1), (4,4)}.
4. Р [pic] Z2,  ( x, у)  [pic] Р  [pic] х + 1 = у.
5. x[pic](у [pic] z ) и (х[pic]у)[pic] (х[pic]z).
6.  [pic] [pic] x .
7. ƒ (1,0,0)= ƒ(0,0,1) = ƒ (0,1,1)=0.
8. (1111 1100  0011  0011).

[pic]
11  [pic]כ = {x [pic] [pic], x V y }.
12. (А  [pic] В) [pic] (A U С) = А  [pic] (В U С).


Вариант 20
1. А [pic] (В [pic] С) = (А [pic] В)  [pic] ( A [pic] С ),
   (А [pic] Б) х С = (А х С) [pic] ( В х С).
2. 13 + 23 + 33 + ... + n3 =  [pic].
3. Р1 = {(а,2),(а,4),(а,3),(с,1),(с,2),(с,3)},
    Р2 = {(1,1), (1,4), (2,3), (3,3), (4,1), (4,3), (4,4)}.
4. Р [pic] Z2,  (х, у)  [pic] Р  [pic] у [pic] x - 2.
5.  x [pic] (у [pic] z) и ( x [pic] у) [pic] (x [pic] z).
6. ([pic]V у)  [pic] ( [pic] ).
7. ƒ(0,0,1) = ƒ(0,1, 1) = ƒ( 1,1,0) =0.
8. (0011  0011  0101 1100).
[pic]
11 [pic]= { x [pic] у,  [pic] [pic]у}.
12 (А \ В) \ (А  [pic] С) = А \ (В [pic]С).
 
Вариант 21
1. А [pic] (А [pic] В) = В,
   А х (В [pic]С) = (А х В)  [pic] (А х С).
2. 8n - 1 кратно 7 для всех натуральных  n[pic]1.
3. P1={[pic], [pic], [pic], [pic], [pic], [pic], [pic],},
    Р2 = {(1,1), (2,2), (2,4), (3,3), (4,4), (3,2), (1,3), (4,1)}.
4. Р [pic] (Z+)2,  ( x, у)  [pic] Р [pic] НОД( x,у) [pic] 1,
     где Z+ = { x [pic]Z │ z > 0}.
5  x [pic] (y  [pic] z) и ( x [pic] у)  [pic] ( x [pic]z ).
6  ([pic]│[pic])[pic] y.
7  ƒ(0,0,0) = ƒ(0,0, 1) = ƒ(1,0,0) = ƒ(1,1,0) =  0.
8 (1110 1001 0111 0001).

[pic]
11. [pic]= { [pic]  [pic] у,  [pic] [pic][pic] }.
12. ( A [pic] B )  [pic] (А  [pic] С) = А \ ( B [pic] С).
 
Вариант 22
1. A U В = А [pic] В [pic] (А [pic] В),
    А х (В \ С) = (А х В) \ (А х С).
2. 12 + 32 + 52 + ... + (2n - 1)2 = [pic].
3.  Р1 = { [pic], [pic], [pic], [pic], [pic], [pic]},
    Р2 = {(1.1), (2,3), (2 , 2), (2,4), (3, 3), (3,4), (4, 2), (4,4)}.
4. P [pic] (Z+)2,  (х,у)  [pic] Р [pic] x [pic]у.
5. x [pic](y| z ) и (х [pic]у)| (х[pic] z).
6. [pic][pic] ( z [pic][pic]).
7. ƒ(0,1,1) = ƒ(1,0,0) = ƒ(1,0,1) = 1.
8. (0001  0011  1100 1110).

[pic]
11. [pic]= { [pic][pic] [pic], [pic] v y}.
12. (A U В)  [pic] (А [pic] С) =  A [pic] (B \ С).
 
Вариант 23
1. А \ В = А [pic] (А [pic] В), (A U В) х С = ( A х С) U (В х С).
2. 4n – 6 n - 1 кратно 9 для всех натуральных n > 0.
3. Р1 = {(а,3),(а,2),(а,4),(Ь,1},(с,2},(с,4},(с,3)},
    Р2={(1,1),(2,2),(2,1),(3,3),(4,4},(4,3),(1,4),(2,4), (3,2),(3,4)}.
4. P [pic](Z+)2, { x,у) [pic]Р [pic]x2 = у,
    где Z+ = { x [pic] Z | x >0}.
5.  x [pic] (у| z) и ( x [pic] у)|( x [pic] z).
6.  [pic]
7. ƒ(0,0,1) = ƒ(1,0,0) =ƒ(1,1,0)==1.
8. (0011 1100  0011  0101).
[pic]
11. [pic] = { [pic],  [pic][pic][pic]}.
12. (А [pic]В) \ (В [pic]С) = (А \ В) [pic](А \ С).
 [pic]
Вариант 24
1. A [pic] В = (А [pic][pic]В) [pic](А [pic]В), 
    Ах (В U С) = (А х В) U (А х С).
2.  [pic] - [pic] +[pic] - [pic] + --- + (-1)n+1 · [pic]= [pic](2 + (-1)n-1 ∙ [pic]).
3.  Р1 = {(b,2), (а, 3), (b,1), (b,4), (с, 1), (с, 2), (с,4)},
     Р2 = {(1,1), (1,2), (1,4), (2,2), (2,4), (3,3), (3,2), (3,4), (4,4)}.
4. Р [pic] (Z+)2, ( x, у)  [pic] Р  [pic] x2 [pic] y,
   где Z+ = { x  [pic] Z| x >0}.
5.  x[pic](у[pic]z) и (x[pic]у)[pic](x[pic]z).

6.  [pic][pic]([pic][pic]y).
7. ƒ(0,1,1) = ƒ(0.1,0) = ƒ(1,0,0)=ƒ(1,0,1)=0.
8. (1010 0010 1101 0111).
[pic]
11. [pic] = { [pic] [pic],  x [pic] у}.
12. (А \ B) U (С \ В) = (В U С) \ A.

 Вариант 25 
1. [pic] U [pic] = А [pic]В;
   А  [pic] С, В [pic] D  [pic]А х В = (А х D) [pic] (С х В).
2.  n7 - n кратно 7 для всех n > 0.
3. Р1 = {(а, 2). (а,3), (а, 4), (b, 3), (с, 1), (с, 4)},
    Р2 = {(1,1),(2,3),(2,2),(3,4),(1,4),(2,4),(4,2)}.
4. Р [pic] (Z+)2, ( x, у) [pic] Р  [pic] x2 > у,
    где Z+ = {х [pic] Z | х > 0}.
5. х[pic] (у  [pic] z ) и ( x [pic] У)  [pic] ( x [pic] z).
6. (( [pic]) [pic][pic])| у) .
7. ( 0011  1101 0010 1100). 

[pic]
8. ƒ(0,1,1) = ƒ (0,1,0) = ƒ(1,0,1) = ƒ(1,1,1) = 1.

11. [pic]= {x V [pic],   [pic] [pic]y}.
12. А \ (В \ С) = (А \ В) \ С.


3.2 СӨЖ


Тестік сұрақтар
$1. Множество А называется … множества В, ели всякий элемент из А является элементом В
A. подмножеством
B. элементом
C. строгим подмножеством
D. собственным множеством

$2. Если А[pic] В и А[pic]В, то А называется …
A. подмножеством
B. элементом
C. строгим подмножеством
D. собственным множеством

$3. Если элементы множеств А и В совпадают, то они называются …
A. бесконечным 
B. равными
C. конечным
D. мощностью

$4. Если А[pic] В и В[pic]А, то они называются …
A. бесконечным 
B. равными
C. конечным
D. мощностью

$5. Множество, состоящее из конечного числа элементов, называется …
A. бесконечным 
B. равными
C. конечным
D. мощностью

$6. Множество, состоящее из бесконечного числа элементов, называется 
A. бесконечным 
B. равными
C. конечным
D. мощностью

$7. Число элементов в конченом множестве М называется его …
A. бесконечным 
B. равными
C. конечным
D. мощностью


$8. Укажите правильное обозначение объединение множеств А и В
A. А[pic]В
B. А[pic]В
C. А[pic]В
D. А[pic]В

$9. Покажите правильное обозначение пересечение множеств А и В
A. А[pic]В
B. А[pic]В
C. А[pic]В
D. А[pic]В

$10. Покажите дополнение множества А
A. [pic]
B. [pic] 
C. U 
D. А\В

$11.Разность множеств А и В
A. [pic]
B. [pic] 
C. U 
D. А\В

$12. Бинарное отношение
A. [pic]
B. R
C. R(a:b) 
D. Q

$13. Геометрические представления множеств – это
A. Диаграммы
B. прямоугольники
C. Диаграммы Венна
D. фигуры

$14. Какие из следующих утверждений справедливы
A. [pic]Ø
B. Ø ={0}
C. / { Ø }/=0
D. / Ø/=0



$15. R – отношение на множестве М. R – рефлексивно, если …
A. a R a
B. a R b и b R a
C. a R b, b R c то a R c  
D. a R b

$16. R – отношение на множестве М. R – симметрично, если …
A. a R a
B. a R b и b R a
C. a R b, b R c то a R c  
D. a R b

$17. R – отношение на множестве М. R – транзитивно, если …
A. a R a
B. a R b и b R a
C. a R b, b R c то a R c  
D. a R b

$18. Объединение бинарных отношений
A. R1 [pic] R2
B. R1 [pic] R2
C. R1 \ R2
D. R-1

$19. Пересечение бинарных отношений
A. R1 [pic] R2
B. R1 [pic] R2
C. R1 \ R2
D. R-1

$20. Разность бинарных отношений
A. R1 [pic] R2
B. R1 [pic] R2
C. R1 \ R2
D. R-1

$21. Обратное отношение 
A. R1 [pic] R2
B. R1 [pic] R2
C. R1 \ R2
D. R-1




$22. Найдите правильную формулу
A)[pic]
B)[pic]
C) [pic]
D) [pic]

$23. Вычислите [pic]
A)80
B)45
C)64
D)50

$24. Вычислите [pic]
A)4725
B)4600
C)4845
D)4800

$25. Вычислите [pic]
A)464
B)470
C)450
D)455

$26. Вычислите [pic]
A)435
B)420
C)415
D)450

$27. найдите формулу подстановки
A)[pic]
B)[pic]
C) [pic]
D) [pic]

$28. Вычислите P5
A)156
B)204
C)120
D)112

$29. Вычислите P7
A)5240
B)5030
C)5120
D)5040

$30. Вычислите P3
A)6
B)10
C)12
D)8

$31. Вычислите P4
A)36
B)24
C)20
D)42

$32. Найдите формулу перестановки
A)[pic]
B)[pic]
C) [pic]
D) [pic]
$33. Вычислите [pic]
A)5150
B)5100
C)5040
D)5025

$34. Вычислите [pic]
A)6670
B)6540
C)6630
D)6720

$35. Вычислите [pic]
A)120
B)160
C)140
D)130

$36. Вычислите [pic]
A)840
B)720
C)820
D)760

$37. Вычислите [pic]
A)3020
B)3024
C)3146
D)3126

$38. найдите правильную формулу?
A)[pic]
B) [pic]
C) [pic]
D) [pic]
$39. Вычислите [pic]
1221
1243
1225
1260

$40. Вычислите [pic]
A) 715
B) 720
C) 780
D) 760




$41. Даны A={1,2,3}; B={1,3,5,6}. Найти А/В
A) 2
B) 3
C) 5
D) 4

$42. Даны B={1,3,5,6}; C={4,5,6}. Найти В/С
A) 3; 6
B) 2; 4
C) 2; 6
D) 1; 3

$43. Даны U={1,2,3,4,5,6}; A={1,2,3}; B={1,3,5,6}. Найти [pic][pic]В
A) 1,2,3,4,6
B) 1,2, ,4,5,6, 2
C) 1,3,4,5,6
D) 1,2,3,4,5,6

$44. Даны U={1,2,3,4,5,6}; A={1,2,3}; B={1,3,5,6}. Найти [pic]
A) 5; 6
B) 2; 4
C) 2; 6
D) 1; 3

$45. Даны A={1,2,3}; C={4,5,6}. Найти [pic]
A) 3; 6; 5
B) 1; 2; 3
C) 2; 6; 1
D) 1; 3; 5

$46. Даны Х={0, 1,}; У={а, в}.  Найти  Х х У
A) {(а; 0), (в; 0), (1; а), (1; в)}
B) {(1; а), (0; в), (0; а), (1; в)}
C) {(1; а), (1; в), (0; а), (0; в)}
D) {(0; а), (0; в), (1; а), (1; в)}

$47.  Найти закон дистрибутивности относительно объединения
A) [pic]
B) [pic]
C) [pic]
D) [pic]



$48.  Найти закон дистрибутивности относительно пересечения
A) [pic]
B) [pic]
C) [pic]
D) [pic]

$49.Покажите правильное свойства множеств U  и Ø 
A. U [pic] А=U
B.  Ø [pic] U =A
C. A \ U=A
D. U -1

$50. Покажите правильное свойства множеств U  и Ø 
A. U [pic] U= Ø
B.  A [pic] U =A
C. A \ U=A
D. U -1

$51. Покажите правильное свойства множеств U  и Ø 
A. U [pic] А= A
B.  A [pic] Ø  = Ø
C. A \ U=A
D. U -1

$52. Покажите правильное свойства множеств U  и Ø 
A. U [pic] А= A
B.  A [pic] Ø  = A
C. A \ U=A
D. A  [pic]Ø  = A

$53. Покажите правильное свойства множеств U  и Ø 
A. U [pic] А= A
B.  [pic]=Ø
C. A \ U=A
D. A  [pic]Ø  = A

$54. Покажите правильное свойства множеств U  и Ø 
A. U [pic] А= A
B.  [pic]=U
C. A \ U=A
D. A  [pic]Ø  = A



$55. Закон отрицание
A. U [pic] А= A
B.  A [pic] [pic]= Ø
C. A \ U=A
D. A  [pic]Ø  = A

$56. покажите правильное утверждение
A. U [pic] А= A
B.  A  [pic][pic]= U
C. A \ U=A
D. A  [pic]Ø  = A

$57. Объединение бинарного отношения
A. R1 [pic] R2={(a,b):(a,b)∈ R1 или (a,b)∈ R2 }
B. R1 [pic] R2={(a,b):(a,b)∈ R1 и (a,b)∈ R2 }
C. R1 \ R2={(a,b):(a,b)∈ R1 и (a,b)∉ R2 }
D. R-1={(a,b):(b,a)∈ R}

$58. Пересечение бинарного отношения
A. R1 [pic] R2={(a,b):(a,b)∈ R1 или (a,b)∈ R2 }
B. R1 [pic] R2={(a,b):(a,b)∈ R1 и (a,b)∈ R2 }
C. R1 \ R2={(a,b):(a,b)∈ R1 и (a,b)∉ R2 }
D. R-1={(a,b):(b,a)∈ R}

$59. Разность бинарного отношения
A. R1 [pic] R2={(a,b):(a,b)∈ R1 или (a,b)∈ R2 }
B. R1 [pic] R2={(a,b):(a,b)∈ R1 и (a,b)∈ R2 }
C. R1 \ R2={(a,b):(a,b)∈ R1 и (a,b)∉ R2 }
D. R-1={(a,b):(b,a)∈ R}

$60. Обратное бинарное отношение
A. R1 [pic] R2={(a,b):(a,b)∈ R1 или (a,b)∈ R2 }
B. R1 [pic] R2={(a,b):(a,b)∈ R1 и (a,b)∈ R2 }
C. R1 \ R2={(a,b):(a,b)∈ R1 и (a,b)∉ R2 }
D. R-1={(a,b):(b,a)∈ R}

$61. Дополнение бинарного отношения
A. R1 [pic] R2={(a,b):(a,b)∈ R1 или (a,b)∈ R2 }
B. [pic]=U/R
C. R1 \ R2={(a,b):(a,b)∈ R1 и (a,b)∉ R2 }
D. R-1={(a,b):(b,a)∈ R}

$62 Композиция бинарного отношения
A. R1 [pic] R2={(a,b):(a,b)∈ R1 или (a,b)∈ R2 }
B. [pic]=U/R
C. R°R={(a,b): (a,c), (с,b)∈ R}
D. R-1={(a,b):(b,a)∈ R}

$63. Транзитивное бинарное отношение
A. R0={(a,b): (a, c1), (с1, c2), …, (ck, b)∈ R}
B. [pic]=U/R
C. R°R={(a,b): (a,c), (с,b)∈ R}
D. R-1={(a,b):(b,a)∈ R}

$64. Рефлексивное бинарное отношение
A. R0={(a,b): (a, c1), (с1, c2), …, (ck, b)∈ R}
B. R*= R°∪Е
C. R°R={(a,b): (a,c), (с,b)∈ R}
D. R-1={(a,b):(b,a)∈ R}

$65. сложение х1  и х2 
A. [pic](х1,х2)=х1[pic]х2;      C. [pic](х1,х2)=х1(х2;
B. [pic](х1,х2)=(х1+х2);      D. [pic](х1,х2)=х1(х2;

$66. эквиваленция х1  и х2
A. [pic](х1,х2)=х1(х2;           C. [pic](х1,х2)=х1[pic]х2;
 B. [pic](х1,х2)=х1[pic]х2;      D. [pic](х1,х2)=(х1+х2);

$67. импликация х1  и х2
A. [pic](х1,х2)=х1[pic]х2;     C. [pic](х1,х2)=х1[pic]х2;
B. [pic](х1,х2)=х1[pic]х2;    D. [pic](х1,х2)=(х1+х2);

$68. штрих Шиффера 
 A.[pic](х1,х2)=х1 ( х2;               C. [pic](х1,х2)=(х1+х2);
B. [pic](х1,х2)=х1[pic]х2;             D. [pic](х1,х2)=х1[pic]х2;


$69. Правила де Морана:
 A. [pic]; [pic]    B. [pic];
 C. [pic];       D. [pic];

$70. Правила де Морана:
A.[pic]; [pic]             B. [pic];
C. [pic];       D. [pic];

$71. найдите неправильную формулу:
A.[pic]; [pic]             B. [pic];
C. [pic];       D. [pic];

$72. Стерлка Пирса
A. [pic](х1,х2)=х1[pic]х2;     C. [pic](х1,х2)=х1[pic]х2;
B. [pic](х1,х2)=х1[pic]х2;    D. [pic](х1,х2)=(х1+х2);

$73. Сложение по модулю 2
A. [pic](х1,х2)=х1[pic]х2;     C. [pic](х1,х2)=х1[pic]х2;
B. [pic](х1,х2)=х1[pic]х2;    D. [pic](х1,х2)=[pic](х[pic]х2);

$74. найдите правильную формулу алгебры логики
A. [pic]и [pic];
B. [pic]и [pic];
C. [pic]и [pic];
D. [pic]и [pic].

$75. найдите правильную формулу логики
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$76. найдите неправильную формулу логики 
A. [pic]
B.[pic]
C. [pic]
D. [pic]

$77.  эквивалентна [pic] 
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$78. эквивалентна [pic]
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$79. эквивалентна [pic]
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$80. [pic]
A. х
B. [pic]
C. 1
D. 0

$81. операция постановки
A)[pic]
B)[pic]
C) [pic]
D) [pic]

$82. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$83. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$84. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$85. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$86. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$87. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$88. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$89. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$90. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$91. Найти правильную тавтологию
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$92. Квантор нахождения
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$93.  Число ребер концом которых является вершина а, называется …
A. степению
B. петля
C. дуга
D. вершина

$94. Число ребер концом которых является вершина а, называется …
A. обходы
B. петля
C. дуга
D. валентность

$95. Обозначение степени вершины а 
A. d(a,b)
B. degGa
C. deg
D. G

$96. Обозначение степени вершины а 
A. d(a,b)
B. dega
C. deg
D. G

$97. Вершина степени 0 – ...
A. висячей
B. изолированый
C. петля
D. степень

$98. Вершина степени 1 – ...
A. висячей
B. изолированый
C. петля
D. степень

$99. Вершина степени 0 – ...
A. дуга
B. изолированый
C. петля
D. степень

$100. Полустепенью исхода deg+a ?
A. число дуг заходящих в вершину а 
B. число вершин
C. называется число дуг исходящих из а
D. число дуг

$101.Полустепенью захода  deg-a ?
A. число дуг заходящих в вершину а 
B. число вершин
C. называется число дуг исходящих из а
D. число дуг

$102. Число степени вершины а ?
A. dega= dega+ dega
B. dega= deg+a+ deg-a
C. dega= deg+a- deg-a
D. dega= deg+a* deg-a

$103. Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер7 как называется это лемма
A. Эйлер
B. Гамильтон
C. мосты Кенингсберга
D. о рукопожатиях

$104.  Как называетсяцикл содержащий все ребра мультиграфа?
A. Эйлер
B. Гамильтон
C. мосты Кенингсберга
D. о рукопожатиях


$105. [pic] 
A. Эйлер
B. Гамильтон
C. Шеннон
D. Буль

$106. [pic]
A. Эйлер
B. Гамильтон
C. Буль
D. Шеннон

$107.формула полного склевания
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$108. формула неполного склевания 
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$109. Формула поглащения
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$110. Объединение графов
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$111. Пересечение графов
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$112. Сложение по модулю два
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$113. Умножение графов
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$114. Сложение графов
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$115. Сложение дуг по модулю два
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$116. Добавление к графу вершины а
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$117. Удаление вершины а из графа
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$118. Добавление дуги [а;b]  к графу
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$119. Удаление дуги [а;b]  из графа
A. [pic]
B. [pic]
C. [pic]
D. [pic]

$120. Найти матрицу смежности
A. [pic]
B. [pic]
C. Wij=║wij║
D. Gij


Сұрақтар
Множество и элементы. Универсальное множество и пустое множество.
Принадлежность множеству. Подмножества. Диаграммы Венна.
Операции над множествами: объединение и пересечение множеств, дополнение и симметрическая разность.
Тождества алгебры множеств: тождество идемпотентности, тождество ассоциативности и коммутативности, тождество дистрибутивности.
Тождества алгебры множеств: тождества единицы и тождество инволютивности, тождество дополнения и тождества Де Моргана.
Дуальность в алгебре множеств.
Конечные множества. Принципы счета. Принцип включения и исключения.
Классы множеств. Булеан.
Математическая индукция.
Декартово произведения множеств.
Отношения. Обратные отношения.
Способы задания отношений (в виде графиков, диаграммы стрелок, матриц отношении и ориентированных графов).
Композиция отношений (интерпретация в виде диаграммы стрелок и в терминах матриц).
Отношение рефлексивности. Отношения симметричности и антисимметричности. Отношение транзитивности.
Замыкание отношений рефлексивности и симметричности и отношения транзитивности.
Отношение эквивалентности и разбиение.
Отношение частичного порядка. Решетка. Диаграмма Хассе.
Рекурсивно определенные функции. Факториал. Последовательность Фиббоначчи. Биномиальные коэффициенты.
Порядок множества. Счетное множество.
Перестановки. Сигнатура перестановки. Произведение перестановок.
Логические операции (конъюнкция, дизъюнкция и отрицание)
Тавтология и противоречие. Алгебра высказываний.
Логические импликации. Условные функции.
Теорема Де Моргана.
Булева алгебра.
Эквивалентность формул. Совершенные дизъюнктивные нормальные формы. Совершенные конъюнктивные нормальные формы.
Переключательные схемы.
Графы. Матрица инцидентности.
Степени вершин. Теорема о рукопожатиях.
Графы Эйлера. Графы Гамильтона. Ориентированные графы.
Формула Кэли для количества деревьев.

• Іс жүргізу
• Автоматтандыру, Техника
• Алғашқы әскери дайындық
• Астрономия
• Ауыл шаруашылығы
• Банк ісі
• Бизнесті бағалау
• Биология
• Бухгалтерлік іс
• Валеология
• Ветеринария
• География
• Геология, Геофизика, Геодезия
• Дін
• Ет, сүт, шарап өнімдері
• Жалпы тарих
• Жер кадастрі, Жылжымайтын мүлік
• Журналистика
• Информатика
• Кеден ісі
• Маркетинг
• Математика, Геометрия
• Медицина
• Мемлекеттік басқару
• Менеджмент
• Мұнай, Газ
• Мұрағат ісі
• Мәдениеттану
• ОБЖ (Основы безопасности жизнедеятельности)
• Педагогика
• Полиграфия
• Психология
• Салық
• Саясаттану
• Сақтандыру
• Сертификаттау, стандарттау
• Социология, Демография
• Спорт
• Статистика
• Тілтану, Филология
• Тарихи тұлғалар
• Тау-кен ісі
• Транспорт
• Туризм
• Физика
• Философия
• Халықаралық қатынастар
• Химия
• Экология, Қоршаған ортаны қорғау
• Экономика
• Экономикалық география
• Электротехника
• Қазақстан тарихы
• Қаржы
• Құрылыс
• Құқық, Криминалистика
• Әдебиет
• Өнер, музыка
• Өнеркәсіп, Өндіріс