1 Бинарлық қатынастар. Бинарлық қатынастардың негізгі қасиеттері

Математикада берілген жиынның элементтері арасындағы әртүрлі қатынастар зерттеледі. А жиынының әртүрлі қос элементтерін байланыстыратын қатынастарға тоқталамыз.

1 анықтама. Кез келген А және В жиындары үшін α АВ ішкі жиыны А және В жиындарының элементтері арасындағы бинарлық қатынас деп аталады.

Егер А=В, онда α А² А жиынында берілген бинарлық қатынас деп аталады.

Егер реттелген қосы <а, в> α болса, онда а және в α қатынасы арқылы байланысқан деп атайды, немесе, а элементі в элементімен α қатынасында деп айтады және а α в деп жазылады.

Мысал. А<в, а в, М нүктесі а түзуіне тиісті.

2 анықтама. Α бинарлық қкатынасының элементтерінің барлық бірінші координаталарының жиыны α қатынасының анықталу облысы деп аталады және деп белгіленеді. Ал барлық екінші координаталарының жиыны α қатынасының мәндер жиыны деп аталады және деп белгіленеді.

А жиыны- нақты сандар жиыны болған жағдайға аса назар аударамыз. Яғни А- R² – кәдімгі жазықтық. Кез келген бинарлық қатынатар жазықтықтағы нүктелердің ішкі жиыны ретінде қарастырылады. Бұл сәйкес қатынастың көрнекі геометриялық сипаттамасын береді.

Мысал. Х<у қатынасы үшін орындалатын реттелген қостар жиыны у=х түзуінің жоғарғы бөлігінде орналасқан нүктелер жиыны.

Жиындағы бинарлық қатынастардың қасиеттері

3 анықтама. А жиынындағы бинарлық қатынас:

а) рефлексивті деп аталады, егер А жиынының әрбір элементі өзімен - өзі қатынаста болса.

- рефлексивті  а А а а.

Мысалдар: =, қатынастары

б) симметриялы деп аталады, егер А жиынына тиісті кез келген а,в элементтері үшін а в=>в а орындалса.

- симметриялы  а, в А а в=>в а.

Мысалдар: =, қатынастары

в) транзитивт деп аталадыі, егер А жиынына тиісті кез келген а,в,с элементтері үшін а в в с => а с

- транзитивті  а, в, с А а в в с => а с.

Мысалдар: <, қатынастары

г) антирефлексивті деп аталады, егер А жиынындағы бірде бір элемент өзімен-өзі қатынасында болмаса.

- антирефлексивті  а А а а.

д) антисимметриялы деп аталады, егер А жиынына бірмезгілде <а, в> және <в, а> қостары тиісті болмаса.

- антисимметриялы  а,в А а в в а => а = в немесе а в а в => в а.

Мысалдар: қатынастары

е) Байланысты деп аталады,егерА жиынының құрамына , әртүрлі а және в элементтері үшін немесе <а, в> қосы <в, а> болса.

- байланысты  а,в А а в => а в в а.

Мысалдар: <, қатынастары

2. Эквивалентті қатынас және кластарға бөлшектеу

4. анықтама. А жиынында берілген бинарлық қатынас рефлексивті, симметриялы және транзитивті болса, онда қатынасы А жиынында эквивалентті қатынас деп аталады.

Белгіленуі ~.

Мысалдар: = ,

Кез келген жиында эквивалентті қатынастың берілуі кластарға бөлшектеу түсінігімен байланысты.

6. анықтама. А жиыныда оның А_i ішкі жиындарына бөлшектеу берілген дейміз, егер

1. барлық ішкі жиындар бос емес жиындар болса: А_i Ø _i I;

2. Әртүрлі екі ішкі жиын қиылыспаса

А_i A_j => A_i A_j = Ø _i,_j I;

3. Барлық осындай ішкі жиындардың бірігуі А жиынын берсе :

UA_i = A, _i I.

- А жиынындағы бинарлық қатынас болсын.

{х | а х} = ā жиыны а элеметі тудыратын эквивалентті класс деп аталады.

Мысалдар. А – үшбұрыштар жиыны, .

4. анықтама. - А жиынындағы эквивалентті қатынас болсын, онда - ға қатысты барлық эквивалентті кластар жиыны А жиынының қатынасы бойынша фактор жиыны деп аталады және А/ деп белгіленеді.

4-дәрістің тақырыбы: Комбинаторика элементтері.

Жоспары:

1. Математикалық индукция әдісі.

2. Комбинаториканың негізгі ережесі.

3. Алмастырулар, орналастырулар және терулер. Қайталамалы орналастырулар және терулер. Ньютон биномы.

Математикалық индукция әдісі.

Толық емес индукция жиі қате қорытынды әкеліп соғады. Толық индукция әдісі тек қана шектеулі түрде қолданылады. Көптеген қызықты математикалық тұжырымдар шексіз дербес жағдайлардан тұрады, ал шексіз дербес жағдайлардың бәрін тексеріп шығу мүмкін емес. Сондықтан да ерекше әдіс – математикалық индукция әдісіне тоқталамыз.

Математикалық индукция принципі (аксиомасы).

Егер келесі екі шарт орындалса, n натурал санға тәуелді тұжырым, кез келген n үшін тура болады:

а) n=1 үшін тұжырым тура;

б) кез келген натурал k үшін, n=k боғандағы тұжырымның дұрыстығынан n=k+1 үшін тура екендігі шығады.

Математикалық индукция әдісі бойынша дәлелдеудің мысалы.

1 мысал. Кез келген үшін теңдіктің тура екенін дәлелдеу керек.

Шешуі.

а) , демек, n=1 үшін тұжырым тура.

б) k – кез келген натурал сан болсын және тұжырым n=k үшін орындалсын,

яғни

.

n=k+1 үшін тұжырымның дұрыстығын дәлелдейміз, яғни

.

Расында, да

.

Сонымен математикалық индукция принципі бойынша кез келген n натурал мән үшін тұжырым дәлелденді.

Комбинаториканың элементтері.

Ықтималдықтарды есептеу тәсілдері

Кез келген А оқиғасының ықтималдығын классикалық анықтама бойынша есептеу үшін А-ға тиісті нүктелердің (А оқиғасына «қолайлы жағыдайлардың») санын барлық нүктелер (барлық «жағыдайлар») санына бөлуіміз керек. Бұл коьбинаторика ережелерін қолдану арқылы жеңіл жүргізіледі.

Комбинаторика – математика тарауларының бірі. Мұнда шекті жиын элементтерінің түрлі қосылыстары, басқаша айтқанда, әр қилы конфигуралары қарастырлып, олардың сандары салалары саналарды жәнеде есептеледі.Теориялық зерттеу тұрғысынан алғанда комбинаторика алғаш рет XVII ғасырдағы Паскаль, Ферма, Леибнис, және XVIII ғасырдағы Я.Бернулли, Эйлер еңбектерінде қарастырлған. Ұлы математиктердің бұл шығармаларында комбинаторикалардың бір жағынан алғанда тұрмыстың сан алуан мұқтаждарына байланысты болса, ал екінші жағынан алғанда, математиканың өз ішіндегі дамуларымен шектесіп жатыр.

Казіргі кезде комбинаторика математика саласының ішінде өте жедел дамып отырған бөлігіне айналды. Бұған себеп болып отырған бұл теорияның электрондық есептегіш машиналарға, информасия мен ықтималдықтар теорияларына кеңінен қолдануы. Дискерттік деп аталып жүрген математиканың өзінде де көп ықпалын тигізген, міне, осы қосылыстар теориясы.

1. Элементерінің парлары.r және s элементтерден тұратын А={α ₁,...,α _r} мен В={b ₁,...,b _s} жиындарының әрқайсысынан бір–бірден элемент алып жасалған және де бірінші орында a_i А элементі, ал екінші орында b_j B элементі жазылған (a_i, b_j) қосылыстарын парлар деп атайды. Мұндай барлық парлардың саны rs көбейтіндісіне тең.

Шынында да, А және В жиындарының элементтерінен жасалған (a_i, b_j) пары i- ші жатық жол мен j-ші тік жолдың тіктөртбұрышты таблица құрамыз. Мұндай таблицада парлардың әрқайсысы бір-ақ рет кездеседі, бұдан келіп барлық парлардың саны rs көбеитіндісіне тең болатындығы шығады.

Мысалдар.

1. Екі ойын сүиегін лақтырғанда барлық жағыдайлардың саны қанша?

Шешуі. Екі ойын сүйегін лақтырғанда бірінші сүйекте түскен ұпай i, екінші сүйекте түскен ұпай j болсын. Сонда тажирбенің нәтижесі (i ,j) парлары болады, мүндағы i де, j де 1, 2, 3, 4, 5 ,6 мәндерінің бірін қабылдайды. Сөйтіп, барлық жағыдайлардың саны парлардың принципі бойынша n = 6 · 6 = 36.

2. Ұтысқа қатынасатын ақшалай –заттай лотерея билеттерінің бір-бірінен

айырмашылығы серия және билет нөмірлерінде. Серия нөмірлерінің саны n₁-ге, билет нөмірінің саны n₂-ге тең болса, онда ұтысқа қатысатын лотерея билетінің саны n= n₁ n₂ көбейтіндісіне тең.

Ескерте кетелік, егер А жиынының әрбір элементіне В жиынының барлық элементері сәйкес келетіндей қосылыс жасалса, онда бұндай қосылыстар саны n(А) · n(В) көбейтіндісіне тең. Парлар принсипі есеп шығарғанда, міне, осылай қолданлады. Бұл жерде n(А) және n(В) арқылы А және В жиындарының элементтерінің санын белгілеп отырмыз. Шекті А жиынының элементтерінің санын бұдан былай n(А) арқылы белгілейміз.

2. Конбинаториканың негізгі принсипі. Әр қайысы шеткі А₁,А₂,...,А_r жиындары берілсін. Осы жиындардың жазылу нөмірлеріне қарап, бұл міндетті түрде, бір-бірлеп a_n1 А₁, a_n2 А₂,..., a_{n r} А_r элементтерін алалық. Осындай тартіппен алынған a_n1 , a_n2 ,..., a_{n r} элементерін кортеж деп атайды және оны былай жазады. .

Теорема. (Көбейтіндінің теорамасы). А₁,А₂,...,Аr ;жиындарының элементерінен жасалған барлық кортеждердің саны n(A₁) n(A₂)…n(A_r) көбейтіндісіне тең.

Дәлелдеу; Толық математикалық индукция әдісін қолданамыз. Индукцияны r бойынша жүргіземіз. r = 2 болсын. А₁₌{а₁,а₂,…, } және А₁₌{b₁,b₂,…, } деп белгілейік. А_1, b А₂ элементерінен кортежін құрайық. Сонда кортеж парға айналады. Сөйтіп мұндай кортеждердің саны п(А₁)·п(А₂) көбейтіндісіне тең. Сонымен, r = 2 үшін теорема дәлелденді. Енді теореманы r = 1 үшін орынды деп ұйғаралық. Сонда А₁,А₂,...,А_r-1 жиындарының барлық элементтерінен жасалған кортеждердің саны n(A₁) · (A₂)…n(A_r-1) көбейтіндісіне тең болады. Енді (A₁), (A₂),…,(A_r-1) және А_r жиындарының элементтерінен кортежді былай жасаймыз: ((а ,а ,...,а ),а ). Парлар принципі бойынша мұндай кортеждер саны үшін n(A₁) п(A₂)…n(A_r-1) п(А_r)= =n(A_r-1) п(А_r) теңдігі келіп шығады. Теорема толық дәлелденді.

Мысалдар.

1. Бірде-бір цифры қайталанбайтын төрторынды сандардың саны қанша?

Шешуі. Төрторынды санды (i, j, r, l) кортежі деп қарастырамыз. i-дің орныда 1,2,3,4,5,6,7,8,9 цифрларының бірі тұра алады. j-дің орынында қалған 9 цифрлардың біреуі тұра алады, өйткені бұл жерде нольде болуы мұнкін. Сондай ақ r және I-дің орынында тұра алатын цифрлардың саны -8 және 7. Сөйтіп, көбейтіді теоремасы бойынша әр түрлі және цифрлары қайталанбайтын төрторынды сандардың саны n=9·9·8·7= 4536.

2. Телефон станциясы төрт цифрдан тұратын номері бар телефон аппараттарын қамтамасыз етеді. Станция жабдықтайтын барлық аппараттар саны қанша ?

Шешуі. Әрбір аппараттар номерін (i, j, r, l) кортежі деп қарастыруға болады. i, j, r, l элементері цифрлардың қайсын болса да қабылдай алады. Демек, барлық телефон аппараттарының саны n=10·10·10·10=10000.

Кейбір оқулықтарда «кортеж» дегеннің орнына «бір-бірлеп алынған комбинатция» деп те атайды.

3.Терулер. n элементтерден тұратын М жиынын қарастыралық. n

элементтен r-дан жасалған теру деп М жиынының r элементен тұратын ішкі жиынын айтады. Бұл анықтама бойынша, сөйтіп, теру бір-бірінен өзгеше болу үшін оларды жасап тұратын элементтерінің ең болмағанда біреуінде өгешелік болу керек. Мәселен, {1,2,3} және {1, 3, 2} бір ғана теру, өйткені бұлардың элементтерінің арасында ешбір айырмашылық жоқ. n элементен k-дан жасалған терулердің саны үшін белгілеуі қолданлады. Бұны оқиғада «n элементен r-дан жасалған теру саны» деп оқиды.

1-ден бастап n-ге дейін натурал сандардың көбейтіндісі үшін n! (эн факториал) белгілеуі енгізледі. Сөйтіп, n!=1·2·...·n.

Дәлелдеуін келтірмей-ақ терулердің сандарын есептейтін формулаларды берелік.

= немесе = (4)

мұндағы 0 < r ≤ n.

Мысалдары.

1. n бұрышты көпбұрыштың диагональдарының санын табу керек.

Шешуі. Көпбүрыштың төбелерінің саны n-ге тең. Төбелердің кез келген үшеуі бір түзудің бойында жатпайды. Ал, кез-келген екі нүктені кесінділермен қосуға болады. Сол кесінділердің ішінде n кесінді көп бұрыштың қабырғалары болады да, қалғандары диагональдар жасайды. Сондықтанда диагональдар саны

- n = - n =

2. Спортлото (49-дан 6) ойынына қатысушы бір билетті сатып алып,

ұтысқа қатысу үшін оны толтырған. Сонда әр түрлі жағдайлардың саны қашан?

Шешуі. Спортлото ойының ережесі бойынша билеттегі 1- ден 49- ға

дейін жазылған натурал сандардың алтауын сызу керек. Ұтысқа қатысу үшін бұл алты санды қандай тәртіппен сызса да бәрібір. Содықтан ізделінді сан .

Математикада С = 1 теңдігін қабылдауға келісілген.

Теру сандарын есептеу барысында оны жеңілдететін бір формуланы келтірелік: (5)

Мүны дәлелдеп алу (4) формулалар арқылы қиын емес. (5) формуланы пайдаланғанда r > болғаны жөн, әйтпегенде есептеуді ауырлатады.

теру сандарын биномдық коффиценттер деп атайды. Барлық биномдық коффиценттердің қосындысы -не тең. Бұл Ньютон биномының

жіктеуіндегі а мен b-ның орындарына 1-ді қойғаннан келіп шығады.

Сонымен, мынандай қортындыға да келейіе; n элементтерден тұратын жиыннның барлық ішкі жиындарының саны -не тең.

4. Орналастырулар. Түрлі комбинаторикалардың ұғымын енгізудің бірнеше жолы бар. Орналастырулар үшін де осылай жазуға болады. Ықтималдықтарды есептеуге қолайлылығын пайдаланып, орналасулар ұғымын кортеждер арқылы берелік.

n элеиенттен тұратын М={a₁,a₂,…,a_n } жиынынан r көлемді кортеж құралық. Бұл жерде «r көлемді кортеж» деп отырғанымыз кортежге енетін элементтердің саны r-ға тең болатындығын көрсетеді. М жиынынан ( ) кортежі екі түрлі әдіспен жасауы мүнкін; бірі-кортежге М жиынының бір элементі бірнеше рет кіруі мүнкін. Бірінші жағыдайда кортеждерді n элементтен r-дан жасалған орналасулар деп, екінші жағыдайда кортеждерді n элементтен r-дан жасалған қайталамалы орналасулар деп атайды.

Теорема. n элементтен r-дан жасалған орналастырулар саны n(n-1)(n-2)…(n-r+1) көбейтіндісінде, ал қайталамалы орналастырулар саны n^r-не тең.

Дәлелдеу. Былай орналастыруларды былай жасап шығайық; алдымен М жиынынан элнментін аламыз; содан кейін қалған n-1 элементтердің ішінен элементін аламыз. Кортеж элементерін тағы да сол сияқты біртіндеп ала отырып, ақырында қалған n-(r-1) элементтің ішінен элементін аламыз. Сөйтіп,( , ..., ) кортежі шығады. Сонда, көбейтіндінің теорамасы бойынша, барлық кортеждердің саны n(n-1)…(n-r+1) көбейтіндісіне тең болады. Теораманың бірінші бөлігі дәлелденді. Енді, қайталамалы орналастыруларды жасап шығалық; алдымен М жиынынан элементін аламыз да, оны тіркеп болғаннан кейін М жиынын қайта оралтамыз; содан кейін М жиынынан тағы да элементін аламыз және оны тіркелгеннен кейін қайтарамыз; Міне, осы процесті қайталай отырып, ( , ..., ) кортежін жасап шығарамыз. Сонда, көбейтіндінің теорамасы бойынша мұндай кортеждердің саны n·n·…n=n^r-не тең болады. Теорема толық дәлелденді. п элементтен r-дан жасалған орналастырулар саны үшін , ал қайталамалы орналастырулар үшін белгілеулерін енгізсек:

=n(n-1)…(n-r+1)= , (6)

(7)

Мысалдар.

1. Үш ойын сүйегін лақтырғанда қанша жағыдайлар болады?

Шешуі. Үш ойын сүйегін лақтырғанда пайда болатын ұпайлардан (i,j,r)

кортежін жасалық, мұндағы i,j,r 1,2,3,4,5,6 сандардың біреуін қабылдай алады. Сондықтан, ізделінді сан (7) формула бойынша 6³=216-ға тең, өйткені мұнда п = 6 және r = 3.

Бұл есепті жалпылауға болады. Егер s ойын сүйегін лақтырсақ онда

барлық жағыдайдың саны -не тең болар еді. Сол сияқты r теңгелы ні лақтырғанда барлық жағыдайлар саны -не тең.

2. 7 жолаушы бар лифт 10 этаждың әрқайысына тоқтап өтеді. Әрбір

жолаушы қай этаждан түсіп қалам десе бәрі бір. Әрбір этажда бірден артық жолаушы түсіп қалу ықтималдығы қандай?

Шешуі. Тәжирбедегі барлық жағыдайлардың, яғни элементтар оқыйғалардың санын есептеу үшін 7 адамның қайысысы болса да біреуі i-ші этажда түсіп қалуын а арқылы белгілейік. Сода бір жағыдай деп отырғанымыз (а₁,a₂,…,a_n) кортежі болады. Ал бұл қайталамалы орналастыру. (7) формуланы қолданып барлық жағыдайлардың санын табамыз: п = = 10⁷

А арқылы «әр етажда бірден артық жолаушы түсіп қалмайды» оқыиғасын белгілейік. А оқйғасына қолайлы кортеж (а₁,a_2,…,a₁₀) болады, бірақ ол орналастырудың өзі. Демек, (6) формуланы қолданып, қолайлы жағыдайлар санын табамыз: Енді (1) формула бойынша А-ның ықтималдығын есептейміз.

Р(А)= ·10·9·8·7·6·5·4 0.06.

Ықтималдықтар теориясының оқулықтарында «орналастырулар» деген терминнің орынына «таңдамалар» (орысшасы-выборки ) деп те алады.

5. Алмастырулар. n элементен n-нен жасалған орналастыруларды алмастырулар деп атайды. п элементен жасалған алмастырулар санын Р_п арқы белгілейді. Сонымен,

Р_п=n!=1·2·3·…·n. (8)

Орта мектепке арналған оқу құралдарында алмастыруды шекті жиынның элементтерін реттеу әдісі есебінде анықайды. Сонда екі әр түрлі алмастыру дегеніміз-жиынды реттеп шығудың екі түрлі әдісі. Кортеж арқылы анықтағанымызда алмастыру ұғымы осы мағнада қалып қоятындығын түсіну қиын емес.

Мысалдар.

1. Жас бала кубиктерді қатар қойып ойнап отырған, ал кубиктерде

А,А,М,Л әріптері жазылған. Сонда АЛМА сөзінің шығу ықтималдығы қандай?

Шешуі. Есептегі тажирбенің элементар нәтижелері оқйға болатындығы

«жас бала» деген сөздермен берілген (сауаты жоқ деген мағнада, басқа жағыдайда тәжирибе нәтижесі қалай болса солай бола алмайды). Тәжирбе нәтижесін төрт әріптен тұрған кортеждер деп қарастыруға болады жане олардың бір-бірінен айырмашылығы әріптердің алыну ретінде. Олай болса, тәжирбенің әрбір натижесі алмастырулар болады. Демек, п = 4! = 24. В арқылы АЛМА сөзінің шығуын белгілелік. Екі «А» әріпінің орынын алмастырғаннан АЛМА сөзі өзгермей қалады. Сондықтан В-ға қолайлы жағыдайлардың саны т = 2! = 2. (1) формула бойынша

Р(В) = = .

2. 0,1,2,3,4 цифрларынан әр түрлі қанша сан жасап шығуға болады?

Шешуі. Берілген цифрлардан көлемі 5-ге тең кортеждер жасалық, бүлардың саны 5! болады. Бұл кортеждер бес орынды сан бола алмайды, өйткені бірінші орында 0 тұрғанда, ол бес орынды сан болмайды. Ал мұндайлардың саны 4!-ге тең. Сөйтіп, ізделінді сандардың саны n = 5!-4! = 120-24 = 96.

(4), (6) және (8) формулалардан теру, орналастыру және алмастыру сандарының арасында =

Байланысы келіп шығады.

6. Жиындарды топтарға жіктеу. Қайталамалы алмастырулар. Алдымен шекті жиындарга байланысты анықтама беріп, бір теорема дәлелдейік.

Анықтама. Егер Е жиынын өзара қиылыспайтын B₁,B₂,…,B_m жиындарының қосын дысы түрінде жазуға болса, яғни

Е = B₁ B₂ … B_m, B_i,B_j = Ǿ, i ≠ j

болса, онда Е жиыны B₁,B₂,…,B_m жиынына жіктеледі.

Теорема. r₁, r₂,…,r_m теріс емес бүтін сандары үшін r₁+ r₂+…+r_m = n болсын. Сонда п элементтен тұратын Е жиынын r₁ элементтен тұратын В₁,r₂ элементтен В₂, тағы сол сияқты r_m элементтен түратын В_m жиындарға жіктеудің барлық тәсілі мынаған тең:

Дәлелдеу. Алдымен Е жиынының r₁ элементті бар В₁ жиынын құрамыз, мұны тәсілімен жасауға болады. Содан кейін қалған n-r₁ элементтердің ішінен r₂ элементті бар В₂ жиынын құрамыз, мұны әдістерімен орындауға болады. Міне осы процестерді жүргізе отырып, ақырында, n-r₁-…-r_m-1 элементтерден r_m элементі бар B_m жиынын жасаймыз. Сонда, көбетіндінің теорамасы бойынша, Е жиынын B₁,B₂,…,B_m жиындарына жіктеу саны

көбейтіндісіне тең. Бұл санды С_п(r₁,r₂,…r_m) арқылы белгілейік (бұдан былай да осы белгілеуді қолданамыз). Сөйтіп,

С_п(r₁,r₂,…r_m)= = · ·…· = (9)

Теорема дәлелденді.

Жиынды жоғарыда көрсеткендей топтарға бөлуге сәйкес камбинаторикалардың бір-қайталамалы алмастырулар анықталады.

Анықтама. а₁ элементі r₁ рет, a₂ элементі r₂ рет, a_m элементі r_m рет кездесетін п = r₁+r₂ +…+ r_m көлемді кортежді n-ші ретті қайталамалы алмастыру деп атайды.

Қайталамалы мұндай алмастырулардың саны үшін С_п (r₁,…,r_m) белгілеуін қолданамыз. Сонда, мына формуланың орынды болуын дәлелдеп алу қиын емес: С_п(r₁,r₂,…r_m)= (9)

С_п(r₁,r₂,…r_m) сандардың полиномдық коэффициенттер деп атайды, өйткені бұл коэффициенттер полиномдық жіктеуге қатынасады, атап айтқанда

(х₁+х₂+…+х_m)ⁿ =

Мысалдар.

1. «Математика» сөзіндегі әріптерді алмастыра отырып, қанша «сөз» жасап шығуға болады?

Шешуі. Әріптерді алмастыра отырып «математйка» сөзіндегі 10 әріптен 10! сөз шығарып алуға болады. Ал, бұл сөздердегі 3 «а», 2 «м», 2 «т» әріптердің орындарын өздеріне сәйкес ауыстырсақ, онда бұл сөздер ешбір өзгермес еді. Сөйтіп, ізделінді сан тең:

С₁₀(3,2,2,1,1,1) = =151200.

2. 9студентті екі, үш және төрторындық 3 бөлмелерге қанша әдіспен орналастыруға болады?

Шешуі. Ізделінді санды былай табамыз:

С₉(2,3,4) = =1260.!!

7. Қайталамалы терулер. п элементтен r-дан жасалған қайталамалы терулер деп әрқайсысы r элементтен тұратын топтарды айтады және де әрбір элемент осы п топтардың біреуіне тиісті. Барлық қайламалы терулер санын арқылы белгілейміз.

Теорема. п элементтен r-дан жасалған қайталамалы терулер саны мына формуламен анықталады:

(10)

Дәлелдеу: Әрбір қайталамалы теруге бір және тек қана бір қайталамалы алмастыру сәйкестіруге болады. Міне осы сәйкестікті қалай орнатуға болатындығын көрсетелік. a, b, c және d элементтерінен aaabbcdddd және abbbbbbbbd терулерін жасалық. Қандай да болмасын бір элемент қанша рет қайталанса, сонша рет I жазамыз, әр түрлі екі элементке сәйкес бірлердің арасында 0 жазамыз; егер белгелі бір элемент теруге қатыспаса, онда 0 жазамыз. Сонда 0 мен 1-лерден жасалған n+k-1 ретті қайталамалы алмастырулары шығады, ал бұларда 0 цифры n -1 рет және 1 цифры k рет кездеседі. aaabbcddd теруіне 111011010111 алмастыруы, abbbbbbbd теруіне 101111111001 алмастыруы сәйкес келеді.

Сонымен ізделінді саны 0 цифры n -1 рет және 1 цифры r рет кездесетін қайталамалы алмастыру санына тең, яғни

=

Енді (4) формуланы ескерсек,

Соңғы екі теңдіктерден (10) шығады.

Мысал: f(x₁, x₂,…, x_n) аналитикалық функциясының r-шы ретті дербес туындылары дифференциалдаудың реттеріне байланысты емес, тек әрбір айнымалы бойынша қанша дифференциалдауға байланысты. Сондықтан, (10) формуланы қолданып, әр түрлі r-шы ретті дербес туындылардың саны болатындығын көреміз. (5) формуланы пайдаланып, бұл санды түрінде де жазуға бола ды.

Қайталамалы терулерді анықырақ түсіну үшін бір ескерту жасалық. n элементтен r-дан жасалған қайталамалы теруде белгілі бір элемент қанша рет енетіндігін ғана еске алынады. Мысалы, a, b, c, d төрт элементінен 8-ден жасалған aaabbcdd, abadcdd, dcbdabaa терулерінің бәрі бірдей, өйткені бұлардың бәрінде де «a» әрпі үш рет, «b» әрпі екі рет, «c» әрпі бір рет, «d» әрпі екі рет еніп тұр.

ІІ Модуль БУЛЬ ФУНКЦИЯЛАРЫ

5-дәрістің тақырыбы: Буль функциялары

Жаспары:

1.Буль функциялары. П-айнымалыдан тұратын буль функцияларының саны.

2.Елеулі және елеусіз айнымалылар

3. Буль функцияларының суперпозициясы. Элементарлық Бульдік функциялар және олардың қасиеттері. Берілген сигнатураның буль формулалары.

4. Айтылымдар алгебрасының формуласын буль функцияларының көмегімен беру.

Буль функцияларының түйіндестік принципі.

Тұжырымдар логикасының әрбір формуласына ақиқат кесте құруға болатынын білеміз. Керісінше қалай? Керісінше де яғни ақиқат кесте бойынша формула құруға болатынын көреміз.

Айталық n айнымалыдан тәуелді буль функциясы ақиқат кестемен берілсін. Буль функциясының кесте түрінен формулаға көшудің алгоритмі. 1.Кестеден функцияны 1-ге айналдыратын аргументтерге сәйкес құрамалар алынады (асты сызылады).

2. Осы құрамаларға сәйкес конъюнкция жазамыз. Егер х_і аргументінің құрамадағы мәні 1-ге тең болса ол конъюнкцияға өзгеріссіз енеді,ал х_і=0, болса конъюнкцияға оның терістеуі алынады.

3. Алынған барлық конъюнкциялардың дизъюнкциясы іздеген формула болады және ол құрылған функцияның МДҚФ-ы болады.

Мысалы, f (x₁ ,x₂,x₃ )= (3,4,6) f (x₁ ,x₂,x₃ )= (0,2,5,7)

3,4,6-құрамалардың нөмірлері 0,2,5,7- құрамалардың нөмірлері

1 2 3 f (x1 ,x2,x3) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 F= )

x1 x2 x3 f(x1,x2,x3 ) 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 F=( )

Ақиқаттық кесте бойынша МКҚФ құрудың алгоритмі.

Алгоритмді f (x₁ ,x₂,x₃ )= (0,3,7)

функциясына МКҚФ құруға қолданайық.

1.Кестеден функцияны 0-ге айналдыратын аргументтерге сәйкес құрамалар алынады(асты сызылады). 2. Осы құрамаларға сәйкес дизъюнкция жазамыз. Егер хі аргументінің құрамадағы мәні 0-ге тең болса ол конъюнкцияға өзгеріссіз енеді, ал хі=1, болса конъюнкцияға оның терістеуі алынады. 3. Алынған барлық дизъюнкциялар конъюнкциямен жалғастырылады.

x1 x2 x3 f(x1 ,x2,x3) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0

Анықтама Егер f^* (x₁,x₂,…,x_n) = онда f*(x₁,x₂,…,x_n) функциясы f(x₁,x₂,…,x_n) функциясына түйіндес функция деп аталады. f(x₁,x₂,…,x_n) функциясына түйіндес функцияны анықтау үшін, барлық айнымалылар және функцияның өзін оның қарама-қарсы мәндеріне ауыстыру керек.

мысал. Үш айнымалыдан тәуелді функциясын буль формуласы яғни МДҚФ- түрінде өрнектеу керек.

0	0	0	1	0	0	0	1
0	0	1	1	0	1	0	1
0	1	0	0	1	0	0	0
0	1	1	0	1	1	1	1
1	0	0	1	1	1	0	0
1	0	1	1	1	1	0	0
1	1	0	0	0	1	1	1
1	1	1	0	0	1	1	1

Іздеп отырған МДҚФ =

Түйіндестік принципі: Егер f функциясын өрнектейтін F формуласындағы барлық операция белгілерін түйіндес функцияның операция белгілеріне алмастырғаннан алынған F* формуласы берілген f функциясының түйіндес функциясын өрнектейтін болады.

Тек , , а, ж символдарымен ғана байланысқан формулаларды қарастырамыз. , , а, ж символдары бір біріне түйіндес деп аталады.

Мысалдар: ақиқат– формуласының түйіндесі - жалған;

1: х  ж; : х  а;

f2 : х  ж  ж; : х а  а;

3 = ;

; ;

Егер f₁, f₂ функциялары тең болса, онда оларға сәйкес түйіндес формулалар да тең болады. онда . Түйіндестік принцип дизъюнкция, конъюнкция, терістеу арқылы байланысқан формулалармен берілген функциялардың түйіндестерін табу үшін ыңғайлы. Бұл жағдайда берілген формулада конъюнкция дизъюнкцияға, дизюнкция конъюнкцияға ауысады. Сөйтіп ДҚФ – КҚФ, КҚФ- ДҚФ, МДҚФ – МКҚФ немесе керісінше.

Мысалы: (

Егер  формуласы  - ге эквивалент болса:    онда оларға сәйкес түйіндес формулалар да эквивалентті болады ,яғни *  * болады.Егер f* (x₁,x₂,…,x_n) = f(x₁,x₂,…,x_n) онда f(x₁,x₂,…,x_n) функциясы өзіне-өзі түйіндес функция деп аталады.Мысалы,   xy  xz  yz функциясы өзіне өзі түйіндес функцияны кескіндейді. Оған (б₁,б₂,б₃) және (1-б₁, 1-б₂ , 1-б₃) жиынтықтарының қарама-қарсы мәндерінде функция да қарама қарсы мән қабылдайтындығына көз жеткізуге болады. Ол үшін ақиқаттық кесте құрып:

X	0	0	0	0	1	1	1	1
Y	0	0	1	1	0	0	1	1
Z	0	1	0	1	0	1	0	1
	0	0	0	0	0	1	1	1

= ; ; ; ;

екендігін көреміз

Мысал: Түйідестік принципіне сүйене отыра, буль алгебрасындағы түйідестік принципінің дұрыстығын дәлелдеу керек. Буль алгебрасында үш амал бар: ;

Буль алгебрасының әр бір амалына түйіндес амалдарды анықтайық.

а) Айталық, болсын. Олай болса ;

б) Айталық, ; Олай болса ;

в) Айталық, ; Олай болса ;

Сонымен конъюнкция дизъюнкцияға, дизъюнкция конъюнкцияға түйіндес, ал терістеу өзіне өзі түйіндес.

Негізгі әдебиет: 1[49-54]; 2[192-197].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

1. Қандай функциялар бір-біріне түйіндес деп аталады? Мысал келтіріңіз.

2. Ақикаттық кесте бойынша формула құру ережелері

3. Буль функцияларының толық жүйелері.Кез келген логикалық функция өрнектелетін логикалық операциялардың жиынтықтары болады. Мұндай операциялар жиыны функционалды толық жүйелер немесе базис деп аталады. Функционапды толық жүйелерге немесе базистерге мысалдар.

{  , ,  }; {  ,  }; { ,  }; { }; { }; {  , , 1 }; { ,  }; {  , ,  }; {  , ,  }; т.б

Бұлардың ішінде көбірек зерттелгені {  , ,  }- базис; Бұлар буль формулалары деп аталады.

Анықтама. Логикалық функциялар жиыны Р₂ - негізгі жиыны , ал операциялары -дизъюнкция, конъюнкция, терістеу болатын {Р₂; , ,  } алгебрасы логикалық функциялардың бульдік алгебрасы деп аталады.

1-Теорема Кез келген логикалық функция буль формуласы түрінде кескінделеді яғни дизъюнкция, конъюнкция, терістеудің суперпозициясы. Бұдан буль формулаларының жүйесі   {  , ,  }; функциональды толық жүйе.Бұл кесте түрінде берілген кез келген функцияны буль алгебрасының формуласы түрінде кескіндеуге болатындығын көрсетеді.

2-Теорема. Егер функционалды толық * жүйенің барлық функциялары  -жүйенің формулалары арқылы өрнектелетін болса,онда  - жүйе де функционалды толық жүйе болады.

Кез келген жүйенің толықтығы туралы сұраққа Пост теоремасы жауап береді:

Пост кластарының анықтамасы.

1. Р₀ – класы. Бұл 0- ді сақтайтын буль функциялары класы, яғни f (0,0,…,0) = 0 болатын функциялар. Р₀ f  f (0,0,…,0) = 0}.

2. Р₁ –класы. 1- ді сақтайтын функциялар класы, яғни f (1,1,…,1) =1 болатын функциялар. Р₁ f  f (1,1,…,1) = 1}

3. S - өзіне өзі түйіндес функциялар класы. S={f  f - өзіне өзі түйіндес функция}

4. М – монотонды функциялар класы. Кез келген (₁, ...,_n) және (₁, ₂,...,_n) нөлдер мен бірлер жиынтығында ₁ ₁,..., _n _n шарттың орындалуынан

f (₁,…,_n) f (₁,…,_n) орындалса f (х₁,х₂,…,х_п) функциясы монотонды деп аталады. М  { f  f – монотонды функциялар }.

5. L- сызықты функциялар класы.

Егер буль сақинасында < {0,1},  ,  > f- функциясы f (х₁,х₂,…,х_п) = c₀  c₁x₁  c₂x₂ …  c_nx_n түрінде өрнектелетін болса, мұндағы с₁,с₂,...,с_n {0,1} онда Буль функция сызықты деп аталады. c₀ с₁с₂,...,с_п коефициенттері төмендегідей анықталады.

с₀= f (0,0,…,0), c₀  c₁= f (1,0,…,0), c₀  c₂= f (0,1,…,0) ,..., c₀  c_n= f (0,0,…,1) яғни с₀ = f (0,0,…,0), c₁= c₀  f (1,…,0) ,…, с_n = c₀  f (0,0,…,1)

Сонымен f – функциясының сызықтығын тексеру деген с_i коэфициенттерінін тауып, берілген формуланың ақиқаттық кестесімен табылған c₀  с₁х₁ ...  c_п х_п формуланың ақиқат кестесін салыстыру болып табылады Мысалы. x  y функциясы сызықты ма ?

Тексеру: c₀ = o  o = o; c₁ = c₀  f(1,0) = 0  (1  0) = 1; c₂ = o  (f (0,1)) = 0  (0 1) = 1;

Сонымен c₀  c₁ х  c₂y  x  y; x v y пен x  y ақиқат кестесі бірдей емес. Ендеше x v y – cызықты емес. Егер функцияның МДҚФ тұріндегі V – операциясының орнына  қойылса онда сызықты функцияның мүлтіксіз полиномды қалыпты түрін аламыз. (МПҚФ) (дизъюнкция белгісінің орнына  ). Бұл Жегалкин полиномы деп аталады. Мысалы,

F(x₁,x₂,x₃)= (x₂  x₃)  (x₁  x₂)

функциясын 2 модулі бойынша қосу полиномы түрінде жазу керек. f(x₁,x₂,x₃)= (  x₃)  (x₁  x₂)  (x₂,  x₃, 1) (x₁  x₂, x₁x₂)  (x₂,  x₃, 1)  (x₁  x₂ x₁x₂  1)  (x₂,  x₃, 1)   x₁  x₂ x₁x₂  1 (x₂,  x₃, 1)  (x₁  x₂ x₁x₂  1) = x₁  x₃ x₁x₂  x₁x₂  x₂  x₁x₂  x₂  x₁x₃  x₂x₃  x₁x₂ x₃  x₃  x₁  x₂  x₁x₂  1=  x₂  x₁x₃  x₂x₃  x₁x₂ x₃  1

(P₂,  ,,1) – Жегалкин алгебрасы деп аталады.  ={ ,,1} болып белгіленеді: сигнатура деп аталады.

Анықтама. Егер Жегалкин көпмүшелігінің құрамында айнымалылардың көбейтіндісі бар болса, онда көпмүшелік сызықты емес деп аталады, жоқ болса сызықты деп аталады.

Буль функциясының сызықтылығы Жегалкин көп мүшелігінің сызықтылығымен эквивалентті яғни Жегалкин көпмүшелігі сызықты болса оған сәйкес буль функкциясы да сызықты болады.

Мысал. f(x₁y) = xy функциясы Пост класстарының қайсысына жататынын анықтау керек.

f (0,0) = 1; f (1,1) = 0, f(x₁y)  P_o және f(x₁y)  P₁

f (1,0)  f (0,1) болғандықтан f(x ,y)  S;

f (0,0)  f (1,1) болғандықтан f(x ,y)  M;

f(x ,y) функциясы үшін Жегалкин көпмүшелігі f(x ,y) = x y =

= (x  1)  (y  1) = сызықты емес. Мынадай кесте қүруға болады:

Пост теоремасы Буль функциялар жүйесі Ғ толық жүйе болады тек сонда ғана, егер әрбір P0, P,S,M,L кластары үшін Ғ жүйесінен осы класқа жатпайтын функция табылса.

функция кластар o 1 S M L оқ оқ оқ оқ оқ

Бұл теоремадан жоғарыдағы функция толық жүйе құрады, яғни Шеффер функциясы арқылы кез келген буль функциясын алуға болады:

х  x  x, x  y   (x  y) (x  y)

Буль функциялар жүйесі толық болса базис деп аталады, ал жүйеден кез келген функция алынып тасталса жүйе толық емес болады.

Теорема. Әрбір базис 4-тен артық емес буль функциясынан тұрады. Мысалы,

{, }, {, }, {, }, { }, { }, { , v, 0 },{ , , , } базистер.

1-мысал. (P₂,  ,,1) – Жегалкин алгебрасындағы  = { ,,1}сигнатурасы функционалды толық жүйе. Бұл кез келген логикалық функция  сигнатурамен кескінделетіндігін,яғни кез келген логикалық функция айнымалылар мен { ,,1} операция символдары арқылы өрнектелетіндігін көрсетеді.. { ,,1} – функцияналдың толықтығын дәлелдеу үшін.

а) = x  1 б) x  0 = 1

в) x1(x2  x3) = x1x2  x1x3 г) x1  x2 = x1x2  x1  x2

е) x  = 1

қатынастары қолданылады. Формулалардың эквиваленттігін дәлелдеудің стандартты әдісін қолданып,бұл қатынастардың дұрыстығына көз жеткізуге болады.

х		1
0	1	1	1
1	0	1	0

 *       * 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1

Бірінші теоремадан Буль функцияларының жиыны *  {  , ,  }-функционалды толық. 2-теорема бойынша  = { ,,1} жүйесінің толықтығын дәлелдеу үшін *  {  , ,  }-базистің операцияларын  = { ,,1}-базистің операциялары арқылы өрнектеуге болатындығын көрсету жеткілікті. Конъюнкция () операциясы екі жүйеге де ортақ . Енді қалған операциялардың (дизъюнкция (), терістеу( ) ) { ,,1}-символдары арқылы өрнектелетіндігін көрсетсек жеткілікті. Бұл жоғарыдағы а),г) қатынастарынан көрініп тұр.

Негізгі әдебиет: 1[49-54]; 2[192-197].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

2. Пост кластарының әрқайсысына анықтама беріңіз.

3. Логикалық функциялардың қандай жүйелері толық деп аталады?

4. Функционалдық толықтығы туралы Пост теоремасы қандай?

5. Қандай логикалық функциялар сызықты деп аталады ?

6. Жегалкин алгебрасына қандай логикалық функциялар кіреді?

6- дәрістің тақырыбы: Жегалкин полиномдары.

Жаспары:

4. Жегалкин полиномдарын буль функцияларының көмегімен беру.

5. Буль функцияларының тұйық кластары.

6. Монотонды функциялар. Сызықтық функциялар. Қосжақты және өзіне қосжақты функциялар. Функциялардың толық жүйелері. Пост теоремасы.

5-теорема. Р₂ – ден алынѓан кез келген функция mod2 полиномы(полином Жегалкина ) бойынша жазылуы мүмкін.

Дєлел: ол толыќ жүйе.

Енді (х₁, х₂,…, х_n ) айнымалыѓа байланысты Жегалкин полиномыныњ, яѓни

а_{j1…j s} x_j1 ... x_{j s} көрінісіндегі өрнектер санын табамыз. бұл жерде x_j1 ... x_{j s} ќосындылар саны n санынан (1,...,n) ќұралған ( і₁,...,і_s ) ішкі жиынедар санына , яѓни 2ⁿ ге тењ.

Ал б±л жерде а_і1,...,іs тек ќана 0 немесе 1 ді ќабылдаѓан үшін ізделген полиномдар саны 2²ⁿ яѓни барлыќ буль формулалар санына тењ.