Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған



бет75/214
Дата13.02.2017
өлшемі21,8 Mb.
#9109
түріМазмұндама
1   ...   71   72   73   74   75   76   77   78   ...   214

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

Мысалы.


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

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



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



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

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

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

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

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

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

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

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

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


9-дәріс тақырыбы: Комбинаторика. Орналастыру және теру.

(2 сағат)



Дәріс конспектісі.

Комбинаториканың негізгі есебі–қайта санау және ақырлы жиын элементтерін тізбектеу.

Егер берілген ақырлы жиын элементтерінің қаншасының берілген бір қасиетке ие екендігін анықтау қажет болса бұл қайта санау есебі, ал берілген қасиетке ие барлық элементтерді анықтау керек болса, бұл тізімдеу есебі Комбиторика есебін дәлелдеуде екі ереже жиі қолданылады. Олар: қосу және көбейту ережелері.

Егер Х n элементтерден тұратын ақырлы жиын болса, Х объектісін Х тен n тәсілмен алуға болады дейді және Х=n болып белгіленеді.



Егер Х1,…,Хn–қос қостан қиылыспайтын жиындар болса, яғни ХiХj= (ij), онда

-қосу ережесі. (1)

Бұл ережені k=2 үшін былай жазуға болады: Егер х объектісі m тәсілмен таңдалса, ал у басқа n тәсілмен таңдалса, онда "не х, не у" таңдау m+n тәсілмен іске асырылады (х және у элементтерін бір уақытта таңдау болмайды).

Көбейту ережесі. Егер х объектісін m тәсілмен таңдауға болса, және осындай таңдаудан кейін у объектісін өз кезегінде n тәсілмен таңдауға болса, онда реттелген (х, у) жұбын mn тәсілмен таңдауға болады.(х, у – таңдаулары тәуелсіз).

Жалпы жағдайда, егер х1 объектілері n1 тәсілмен таңдалса, одан кейін х2 n2 тәсілмен таңдалса және кез келген 2im-1 үшін х1, х2,…,хi объектілерін таңдағаннан кейін хi+1 объектісін ni+1 тәсілмен таңдауға боллатын болса, онда m объектіден құралған (х1, х2, …, хm) реттелген тізбегі n1  n2 … nm тәсілмен таңдалады.

Х={х1, …, хn} жиынынан алынған хi1, …, хir элементтерінің жиынтығы n элементтен алынған r көлемді таңдама деп аталады.

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

Таңдамаларда элементтердің қайталануы да, қайталанбауы да мүмкін.

Элементтері қайталануы мүмкін (n, r) - таңдамасы (n, r)-қайталама таңдамасы деп аталады. Ал егер реттелген (n, r) таңдаманың элементтері қос қостап әр түрлі болса, (n, r) қайталанбайтын таңдама немесе жай ғана (n, r)-орналасу деп аталады.

(n, n)-қайталанбайтын орналасу Х жиынын алмастыру деп аталады.

Элементтері қайталануы мүмкін реттелмеген (n, r)-таңдама, қайталанба (n, r)-теру деп аталады. Егер реттелмеген (n, r) таңдаманың элементтері қос қостан әр түрлі болса, онда ол қайталанбайтын (n, r)-теруі немесе жай ғана (n, r) теруі деп аталады. Кез келген (n, r)-теруін n-элементті жиынның r-элементті ішкі жиыны деп қарауға болады.

Мысал, айталық Х={1, 2, 3} болсын.

1) (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) - (3, 2)-қайталама орналастырулар.

2) (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) - (3, 2)-қайталама орналасу;

3) (1, 2, 3), (1, 3, 2), (3, 2, 1), (2, 1, 3), (3, 1, 2), (2, 3, 1) – Х жиынын алмастыру;



4) {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3} - (3, 2)-қайталама теру;

5) {1, 2}, {1, 3}, {2, 3} - (3, 2)-қайталанбайтын теру. Қайталама теру саны (n, r)-ді , қайталанбайтын теру-. n-элементті теру саны Pn (яғни Pn=) болып белгіленеді. Қайталама теру (n, r)-саны ,ал қайталанбайтын теру-.


Достарыңызбен бөлісу:
1   ...   71   72   73   74   75   76   77   78   ...   214




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет