Комбинаториканың негізгі принциптері

Қатынастар. Арнайы бинарлық қатынастар. Бинарлық қатынастарға қолданылатын амалдар. Бинарлық қатынастардың графтары. Эквиваленттік қатынас және бөліктеу туралы теорема. Арнайы бинарлық қатынастар.

2). Комбинаториканың негізгі принциптері. Алмастырулар, орналастырулар және терулер. Ньютон биномы.

Комбинаторика ықтималдықтар теориясының кіріспесі ретінде қарастырылады, себебі комбинаторика әдістерінің ықтималдықтар теориясында барлық мҥмкін болатын жағдайлар саны мен қолайлы жағдайлар санын есептеуге кӛп септігі тиеді. Комбинаториканың негізгі ҥш тҥрін қарастырайық. Орналастырулар. Бір-бірінен айырмашылығы орналасу ретінде немесе қҧрамында болатын n элементтің k элементінен жасалған комбинацияларын орналастырулар деп атайды. Орналастырулар санын табу үшін

формуласын қолданады.

Алмастырулар деп бір-бірінен айырмашылығы орналасу

ретінде ғана болатын n элементтің n элементінен жасалған комбинацияларын

айтады және алмастырулар санын келесі формуламен есептейді:

Терулер. Бір-бірінен айырмашылығы тек қҧрамында болатын n элементтің

k элементінен жасалған комбинацияларын терулер деп атайды және терулер

санын

формуласымен есептейді.

Ньютон биномы – екі қосылғыштың (биномның) қосындысының кез келген бүтін оң дәрежесін сол қосылғыштардың дәрежелері арқылы өрнектейтін формула:

,

мұндағы  — биномдық коэффициенттер,  — теріс емес бүтін сан.

Екі қосылғыштың қосындысының квадраты (n=2) мен кубы (n=3) Ньютон биномының дербес жағдайы болып есептеледі: (a+b)2=a2+2ab+b2; (a+b)3=a3+3a2b+3ab2+b3. Ньютон биномы формуласының коэффиценттері биномдық коэффициенттер деп аталады. Биномдық коэффиценттің бірнеше қасиеттері бар:

еолардың барлығы бүтін оң сандар;

ешеткі коэффиценттері 1-ге тең;

екі шеткі мүшелерінен бірдей қашықтықта тұрған мүшелерінің коэффиценттері бірдей болады, т.б.

Ньютон биномының бүтін оң көрсеткішті биномдарға арналған формуласы И.Ньютонға дейін үнді және Ислам математиктеріне белгілі болған, алайда Ньютон бөлшек немесе теріс көрсеткішті биномдар үшін де жіктелудің мүмкіндігін көрсеткен (1664 – 65).

3).Бүтін сандар сақинасы. Жай және құрама сандар. Арифметиканың негізгі теоремасы. Өзара жай сандар және олардың қасиеттері.

Жай сандар. Анықтыма. Егер  натурал санының 1 және өзі екі бөлгіші ғана болса, онда ол сан жай деп аталады. Егер , онда  және  сандары өзара жай деп аталады.  Құрама сандар. Анықтыма. Егер  натурал саны жай сан болмаса, онда ол құрама сан деп аталады.  Теорема (арифметиканың негізгі теоремасы).  әрбір натурал саны не жай, не жай сандардың көбейтіндісі түрінде көрсетіледі, және сол көрсету жалғыз болады. - жай сандар  натурал санының осындай көрсетуі канондық деп аталады. Өзара жай сандар

Бүтін сандардың ±1-ден басқа ешқандай ортақ бөлгіштері болмаса оларды өзара жай сандар деп атайды. Мсыалы: 14 пен 25 өзара жай, ал 15 пен 25 өзара жай емес(олардың ортақ бөлгіші 5).

Басқаша сипаттама: егер жазықта бүтін санды координаттарда жуандығы нөл болатындай «ағаш» отырғызып «орман» салса, онда координаттар бас нүктесінен координаттра өзара жай болатын ағаштар ғана көрінеді.

Белгіленуі

 мен  сандарының өзара жай екендігін көрсету үшін былай: жазады. Бірақ бұндай белгленумен көп математиктер келіспей көбінесе  деп жазады, ол деген сөз: "a мен b сандарының Ең Үлкен Ортақ Бөлгіші 1-ге тең".

Қасиеттері a мен b сандары сонда тек сонда, егер Ең Үлкен Ортақ Бөлгіштері бірге тең болса ғана өзара жай болады, немесе, басқаша айтқанда, егер бүтін x пен y болатындай табылса (қараңыз Безу қатынасы). 1)Кез келген бір біріне теі емес жай сандар өзара жай. 2)Егер  —  бөлгіші болса, және  мен  өзара жай болса, онда  —  бөлгіші болады. 3)Егер a1,…, an сандары — жұп жұбымен өзара жай болса, онда Ең Кіші Ортақ Еселік(a1,…, an) = |a1·…·an|.

4).Салыстырулар және олардың қасиеттері. Эйлер теоремасы. Ферманың кіші теоремасы. Қалдықтар туралы қытай теоремасы. Салыстыру теориясы

Анықтама. а, b Z , N. Егер а және b сандарын m-ге бөлгенде, олардың қалдықтары бірдей болса, онда а және b сандарын модулі бойынша салыстырымды деп айтып, бұл ұғымды арқылы белгілейміз. Бұл бинарлық қатынас рефлексивті, симметриялы және транзитивті, яғни модуль бойынша салыстыру қатынасы эквиваленттік қатынас болады. Бүтін сандар сақинасында, бұл қатынас бойынша табиғи жолмен фактор-сақина анықталады. Оны модулі бойынша қалындылар сақинасы деп атап, Z m арқылы белгілейміз. Жоғарыдағы анықтамадан салыстыру қатынасының келесі қажетті және жеткілікті шарты шығады:

Демек, болуы үшін a=b+mt теңдігі орындалатындай t бүтін санының табылуы қажетті және жеткілікті.

Қасиет 1. Берілген модул бойынша салыстыруларды мүшелеп қосуға болады.

Қасиет 2. Салыстырудың кез келген жағындағы қосылғышты, оның екінші жағына таңбасын өзгертіп көшіруге болады.

Қасиет 3. Салыстырудың кез келген жағына модулге еселі санды қосуға болады.

Қасиет 4. Берілген модул бойынша екі салыстыруды мүшелеп көбейтуге болады, яғни .

Қасиет 5. Салыстырудың екі жағын да бірдей дәрежеге шығаруға болады, яғни

Қасиет 6. Егер a0 b0 (modm), a1 b1 (modm),..., an bn (modm), x y(modm), онда a0 xn +a1 xn-1 +...+an b0 yn +b1 yn-1 +...+bn (modm).

Қасиет 7. Салыстырудың екі жағын да модулмен өзара жай болатын олардың ортақ бөлгішіне қысқартуға болады.

Қасиет 8. Салыстырудың екі жағы мен модулді бірдей санға көбейтуге және олардың ортақ бөлгішіне бөлуге болады.

Қасиет 9. Егер a b салыстыруы бірнеше әртүрлі модул бойынша орындалса, онда бұл салыстыру аталған модулдердің ең кіші ортақ еселігі үшін де орындалады.

Қасиет 10. Егер салыстыру m модулі бойынша орындалса, онда ол осы m саныны кез келген бөлгіші d модулі үшін де орындалады.

Қасиет 11. Егер салыстырудың бір жағы мен модулі қандай да бір санға бөлінсе,

Эйлер және Ферма теоремалары. Эйлер функциясы. . Эйлер функциясы -  санынан кіші және онымен өзара жай болатын сандарының саны. Эйлер функциясы мультипликативті:  өзара жай  сандар үшін. санының канондық жазылуы берілсінОнда Эйлер функциясының мәнін  формуласы бойынша есептеуге болады.Эйлер функциясы үшін  Гаусс тепетеңдігі дұрыс болады. Эйлер теоремасы. Егер  онда . Ферма теоремасы. Егер жай сан және болатындай бүтін сан болса, онда  

Қалдықтар туралы қытай теоремасы.

Лемма 1 Егер сандары санымен өзара жай болса, онда саны да санымен өзара жай болады.

Лемма 2 Егер сандары () – санының бөлгіші болсын, онда саны да санының бөлгіші болады.

Теорема (Қалдықтар туралы қытай теоремасы). m1 ,m2 ,...,mk өзара жай сандар және кез келген бүтін сандары үшін салыстырулар жүйесінің аралығында бір ғана шешімі болады.

5).Туындатушы функциялар. Негізгі элементар функциялар және оларға қолданылатын амалдар.

a0, a1, a2, . . . көбейткіш сандардың тізбегі болсын,осы тізбек үшін туындатушы функция келесі түрде болады

немесе

Егер тізбектің кейбір мүшелерінен басқа мүшелері 0-ге тең болса,онда туындатушы функция көпмүшелердің көбейтіндісі түрінде болады.

6.Пікірлер логикасы. Олардың формулалары. Ақиқаттық кестелер. МДНФ және МКНФ. Логика заңдары.

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

Анықтама. Ақиқат немесе жалған мәндердің бірін ғана қабылдайтын хабарлас сөйлемді пікір деп атаймыз. Пікірлерді Σ1 жиынынан алынған әріптермен белгілейміз.

Анықтама:

Σ1 жиынындағы әрбір әріп формула болады.

Егер φ,ψ формулалар болса, онда ˥φ,(φ∧ψ), (φ∨ψ), (φ→ψ) және (φ↔ψ) сөздері де формулалар болады.

Кез келген формула 1-ші және 2-ші ережелерді ақырғы рет қолдану арқылы ғана құрылады.

Формулаларды кіші грек әріптерімен φ,ψ,θ,.... белгілейміз.

Мысал:

Төмендегі өрнектер пікірлер логикасының сөздері болады.

→˥А 1) ∧ А → А1

(˥А4→)

˥(( А2∨˥ А2)→ А1

Мұндағы алғашқы екі сөз формула болмайды, ал үшіншісі пікірлер лог-ң формуласы.

Формуланың анықтамасы – олардың құрылуы бойынша индукциялық анықтама, сондықтан бұл анықтама формулалардың қасиеттерін формуланың күрделілігі бойынша индукцияны қолдану жолымен дәлелеуге мүмкіндік береді.

Формуладағы жақшалар санын кеміту мақсатымен, логикалық амалдардың орындалу реттерін тағайындайық. Алдымен (терістеу), екінші ретте (коньюкция) және (дизьюнкция), үшінші ретте (импликация), ең соңынан (эквиваленттілік) орындалады деп келіселік. Кәдімгі алгебрадағы сияқты, бұл келісім формулаларды жазуды анықтаумен бірге, үйрене келе оның ұғымдылығын да арттырады. Мысалы, формуласын немесе шатасуға жол бермеу үшін кейбір жақшаларды сақтасақ, оны түрінде жазуға болады. Анықтама. Өзі де формула болатын берілген форм-ң ішкі сөзін ішкі формула дейміз

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

АНЫҚТАМА. әріптері берілсін. Кез келген функциясы ақиқаттық функция деп аталады. әріптерінің функцисы бойынша бейнелерінің тізбегін ақиқаттық мәндердің орналасуы деп атаймыз .

АНЫҚТАМА. формуласында кездесетін әріптер болғанда, кез келген функциясын ақиқаттық функция (немесе интерпретация) деп айттық.Осы функцияға сәйкес формуласының ақиқаттық мәнін ( Белгілеуі: ) келесі тәртіппен анықтаймыз.

1. болса, онда () (A1)

2.Егер , онда () а () = а және () = а

3.Егер болса, онда () а () ж

4.Егер , онда () ж () = ж немесе () = ж

5.Егер , онда () ж () = а және () = ж

Осы анықтаманы төмендегідей кестеге жинақтауға болады.

А

В

А

АВ

АВ

АВ

А

а

Ж

а

а

а

А

ж

Ж

ж

А

ж

Ж

а

А

ж

А

а

Ж

ж

А

ж

ж

а

МЫСАЛ. (((АВ)В)А) формуласының ақиқаттық кестесін құрайық.

А

В

(АВ)

(АВ)

(АВ)В

((АВ)В)А

А

А

ж

А

А

а

А

Ж

а

Ж

Ж

а

Ж

А

ж

А

А

ж

Ж

Ж

ж

А

Ж

а

ФОРМУЛАЛАРДЫ АҚИҚАТТЫҚ КЕСТЕ АРҚЫЛЫ ҚҰРУ.

АНЫҚТАМА. формуласында кездесетін әріптер болғанда, кез келген функциясын ақиқаттық функция (немесе интерпретация) деп айттық. Осы функцияға сәйкес формуласының ақиқаттық мәнін ( Белгілеуі: ) келесі тәртіппен анықтаймыз.

болса, онда () (A1)

Егер , онда () а () = а және () = а

Егер болса, онда () а () ж

Егер , онда () ж () = ж немесе () = ж

Егер , онда () ж () = а және () = ж

Осы анықтаманы төмендегідей кестеге жинақтауға болады.

А

В

А

АВ

АВ

АВ

А

а

Ж

а

а

а

А

ж

Ж

ж

а

ж

Ж

а

А

ж

а

а

Ж

ж

А

ж

ж

а

І.Коньюнкция ережесі. Коньюнкция ақиқат болуы үшін,ондағы әрбір коньюнкция мүшесі (конъюнкт ) ақиқат болуы қажет және жеткілікті.

ІІ.Дизьюнкция ережесі.Дизьюнкция жалған болуы үшін,ондағы әрбір дизьюнкция мүшесі (дизъюнкт) жалған болуы қажетті және жеткілікті.

импликациясындағы формуласы импликацияның себебі,ал формуласы салдары деп аталады.

ІІІ.Импликация ережесі.Импликация жалған болуы үшін оның себебі ақиқат,салдары жалған болуы қажетті және жеткілікті. Бұл ережені басқаша жолмен тағайындауға болады. Импликация ақиқат болуы үшін себебі жалған немесе салдары ақиқат болуы қажетті және жеткілікті.

Бізге 9-ға бөлінетін натурал санның 3 – ке бөлінетіні белгілі. Яғни,

(x саны 9-ға бөлінеді) (x саны 3-ке бөлінеді)

пікірі кез келген x саны үшін ақиқат. Егер бұл пікірде x = 8 деп алсақ, импликацияның салдары мен себебі де жалған, бірақ (1) пікірі әрқашан ақиқат болатынын айттық. Ал x = 6 деп алсақ, импликацияның себебі жалған, ал салдары ақиқат болады, бірақ жоғарыда айтқанымыздай импликация тұтасымен ақиқат болады. Енді импликацияның себебі мен салдарын ауыстырсақ, пайда болған ( саны 3 – ке бөлінеді) ( саны 9– ға бөлінеді)пікірі саны қалауымызша алынған натурал сандар болғанда жалған пікір. Егер =12 десек, онда (2) импликацияның себебі ақиқат, ал салдары жалған болады. Бұл нәтиже импликацияның ақиқаттық кестесінің екінші жолы да біздің қорыту туралы табиғи түсінігімізге сай болатынын көрсетеді.

( Мінсіз дизъюнктивті қалыпты форма туралы). Кез келген нөлден өзге логика алгебрасының функциясы үшін келесі теңдік орындалады

(МДНФ)

Мысал. функциясына сәйкес МДНФ құрайық. Ол үшін берілген функцияға сәйкес ақиқаттық кесте құрамыз. Формуладағы конъюнкция дизъюнкциядан бұрын орындалатынын ескеру керек.

0

0

0

0

0

1

0

1

1

0

0

0

1

0

1

0

1

1

0

0

1

0

1

1

1

1

1

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

1

1

1

1

1

0

1

0

1

0

1

0

1

1

1

0

0

1

0

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

1

0

0

0

0

0

1

1

1

1

1

1

1

1

1

0

1

1

0

0

0

1

1

1

1

0

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

0

1

0

1

1

МДНФ:

.

( Мінсіз конъюнктивті қалыпты форма туралы). Бірден өзге кез келген логика алгебрасының функциясы үшін келесі теңдік орындалады:

(МКНФ).

Мысал. функциясына сәйкес МКНФ құрайық. Ол үшін берілген функцияға сәйкес ақиқаттық кесте құрамыз. Формуладағы конъюнкция дизъюнкциядан бұрын орындалатынын ескеру керек.

0

0

0

0

0

1

0

1

1

0

0

0

1

0

1

0

1

1

0

0

1

0

1

1

1

1

1

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

1

1

1

1

1

0

1

0

1

0

1

0

1

1

1

0

0

1

0

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

1

0

0

0

0

0

1

1

1

1

1

1

1

1

1

0

1

1

0

0

0

1

1

1

1

0

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

0

1

0

1

1

МКНФ: .

АНЫҚТАМА. Құрамындағы әріптердің кез келген ақиқаттық мәндерінің орналасуында ақиқаттық мәндері бірдей болатын (ақиқаттық кестелеріндегі соңғы бағандары бірдей) және формулалары логикалық эквивалентті( парапар ) формулалар деп аталады. Белгілеуі: .

Логикалық эквиваленттіліктердің ең маңыздыларын логика заңдары деп атайды.Пікірлер логикасының алгебрасында логика заңдары елеулі қызмет атқарады. Енді осы аталған ұғымдардың дәл анықтамасын берейік.

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

Төмендегі эквиваленттіліктерді логика заңдары деп атаймыз.

( ) ~ (идемпотенттілік заңы);

(идемпотенттілік заңы );

( ) ( ) (ауыстырымдылық заңы ) ;

( ) ( ) (ауыстырымдылық заңы ) ;

(терімділік заңы ) ;

(терімділік заңы ) ;

( ) (үлестірімділік заңы ) ;

( ( ) (үлестірімділік заңы ) ;

, (сіңіру заңдары) ;

(қос терістеу заңы) ;

( ) ,( ) (Де Морган заңдары);

() (тепе-теңдік немесе тавтология заңы) ;

() (қайшылық заңы).

Соңғы екі эквиваленттілікті былайша баяндауға болады: Конъюнкцияда тавтологияны, қайшылықты дизъюнкцияда ескермеуге болады.

Логикалық эквиваленттіліктер пікірлер логикасының көптеген формулаларын қарапайым түрге келтіруге мүмкіндік береді.Эквиваленттіліктердің осы қасиеті контактылы реле схемаларын-осы схемаларға эквивалентті қарапайым схемалармен ауыстыруда қолданылады.

7.Пікірлер есептеуі. Аксиомалар нұсқалары мен қорыту ережелері. Дедукция теоремасы және оның салдарлары.

ПІКІРЛЕР ЕСЕПТЕУІНІҢ АКСИОМАСЫ.АНЫҚТАМА.

Пікірлер есептеуінің классикалық аксиомалар жүйесі келесі 10 аксиомалар нұсқаларынан тұрады.

φ→(Ψ→φ)

(φ→Ψ)→((φ→Ψ→θ)→(φ→θ))

(φ⩓Ψ)→φ

(φ⩓Ψ)→Ψ

(φ⩓Ψ)→(φ→θ→φ→Ψ⩓θ)

φ→(φ⩔Ψ)

Ψ→(φ⩔Ψ)

φ→θ→(Ψ→θ→φ⩓Ψ→θ)

φ→┐Ψ→(Ψ→┐φ)

┐┐φ→φ

Анықтама. Қандай да бір аксиома нұсқасында кездесетін φ, Ψ және θ символдарын кез келген пікірлер логикаоһсының формулаларымен бір мезгілде ауыстыру арқылы пайда болған формуланы ПЕ-нің аксиомасы д.а.

Мысалдар.

Г1 аксиомалар нұсқасындағы φ және