Автор работы: Пользователь скрыл имя, 01 Ноября 2012 в 19:30, реферат
Бұл айнымалылардың маңызы өте зор. Мысалы, функция көп айнымалы болса, кейбір айнымалыларын (жалған айнымалыларды) алып тастауға болады. Ол бізге барлық параметрлер бойынша үнемдеуге мүмкіндік береді. Сондықтан осы үнемдеуді жүзеге асыратын программдық пакет құру актуалды мәселе. Бұл жұмыста қойылған мақсат бойынша бірінші теориялық, одан кейін программалық жүзеге асыру жүргізілді.
Кіріспе.......................
Жалпы алғанда буль функцияларының жалған және елеулі айнымалыларының дискреттік математикада ойнайтын рөлі өте зор. Бірінші оларды теориялық тұрғыдан қарастырайық. Буль функцияларының жалған және елеулі айнымалылары деп .............. атайды.
Бұл айнымалылардың маңызы өте зор. Мысалы, функция көп айнымалы болса, кейбір айнымалыларын (жалған айнымалыларды) алып тастауға болады. Ол бізге барлық параметрлер бойынша үнемдеуге мүмкіндік береді. Сондықтан осы үнемдеуді жүзеге асыратын программдық пакет құру актуалды мәселе. Бұл жұмыста қойылған мақсат бойынша бірінші теориялық, одан кейін программалық жүзеге асыру жүргізілді.
1. Логика алгебрасының функциялары
A
йталық U-{u1,и2,...,иm,...} - айнымалылардың бастапқы алфавиті болсын. Аргументтері E2={О,1} жиынында анықталған және аiÎЕ2(і = 1,2,...,n), егер аiÎЕ2(і = 1,2,...,п) шартын қанағаттандыратын ƒ(u ,u ,…,u ) функциялары қарастырылады.
Бұл функциялар логика алгебрасыныц функциялары немесе буль фунщиялары деп аталады. Р2 арқылы U алфавитінде берілген, сондай-ақ 0 және 1 тұрақтыларын қамтитын барлық логика алгебрасының функциялар жүйесін белгілейміз.
Теорема. х1,х2,...,хn п айнымалыға тәуелді Р2 жиынындағы барлық
функциялар саны P2 (n) - 22
-ге тең.
Логика алгебрасы функцияларың мысалдары:
xx |
0 0 |
11 |
xx |
|
|
00 |
00 |
11 |
00 |
11 |
11 |
00 |
11 |
11 |
00 |
x1 x2 |
(х1&х2) |
(x1∨x2) |
(х1→х2) |
(x1Åx2) |
(x1\x2) |
(x1 ~x2) |
(х1↓x2) |
0 0 0 1 |
0 0 |
0 1 |
1 1 |
0 1 |
1 1 |
1 0 |
1 0 |
0 1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
2. Формулалар. Формулаларды функциялармен жузеге асыру
Анықтама. Айталық b- Р2 жиынындағы функциялар ішжиыны
болсын.
а) Индукция базисі. b ішжиынындағы әрбір ƒ (x1,…,xm) функция b-ғы формула деп аталады.
b) Индуктивті өту. Айталық ƒ (x1,…,xm) - b жиынындағы функция болсын және A1,…,Am-b жиынындағы формула немесе U жиынындағы айнымалылар символы болатын өрнек болсын. Онда ƒ (A1,..., Аm) өрнегі b жиынындагы формула деп аталады.
с) Формуланың индуктивті анықтамасына сүйене отырып, b-дағы әрбір F(х1,...,xn) функциясына Р2 жиынындағы ƒ (х1,...,xn) функциясын сәйкес қоямыз.
d) Индукция базисі. Егер. F(х1,...,xn) = ƒ (х1,...,xn), мүндағы ƒ Îb, онда F(х1,...,хn) формуласына ƒ (х1,...,xn) функциясын сәйкес қоямыз.
e) Индуктиві өту. Айталық F(х1,...,xn)=ƒ (х1,...,xn) мұндағы Аi(і = 1,...,m) b-дағы формула немесе хj(i) айнымалысыньщ белгісі.
Онда индуктивті болжам бойьнша Аi-ге Рг жиынындағы ƒi
функциясы немесе ƒ =хj(i) тепе-тең функция сәйкес қойылған.
F(х1,...,xn) формуласына ƒ (х1,...,xn)= ƒ0 (ƒ 1,..., ƒ m) функциясын сәйкес қоямыз.
Егер ƒ функциясы F формуласына сәйкес келсе , онда F формуласы ƒ функциясын жүзеге асырады дейді.
F формуласына сәйкес келетін ƒ функциясы b-дағы функциялардың суперпозициясы деп, ал ƒ функциясын b -дан алу үрдісі суперпозиция операциясы деп аталады.
3.Формулалардың эквиваленттігі. Қосалқылык принципі
Анықтама. F және G формулалары b жиынында эквивалентті деп аталады, егер оларға сәйкес функциялар тең болса: ƒF= ƒG.
(х1◦х2) арқылы (x1&x2), (x1∨x2), (х1+х2) функцияларының кез-келгенін белгілейік.
Логика алгебрасы
1) (x1◦х2) функциясы ассоциативтілік қасиетке ие:
((x1◦x2) ◦ x3 ) = (x1◦(x2◦x3)).
2) (х1◦х2) функциясы коммутативтілік қасиетке ие :
(x1◦x2)=(x2◦x1)
3) Конъюнкция және дизъюнкция
үшін дистрибутивтілік заң
((x1∨x2) & x3) = ((x1&x3) ∨(x2&x3))
((x1&x2) ∨ x3)=((x1∨x2) &(x2∨x3)
4) =x , =( ∨ ), =( & )
5) (x& )=0, (x∨ )=1,
(x&0)=0, (x∨0)=x,
(x&1)=0, (x∨1)=x.
Анықтама. [ƒ (х1,...,xn)]*= ( ,…, ) функциясы ƒ (х1,...,xn)
функциясына қосалқы функция деп аталады.
x1vх2 функциясы х1&х2 функциясына қосалқы.
Қосалқылықтың анықтамасынан ƒ ** =( ƒ *)* = ƒ екендігі шығады, яғни функция ƒ * функциясына қосалқы.
Қосалқылық принципі. Егер F=С[ƒ1,..., ƒ s] формуласы ƒ (х1,...,xn)
функциясын жүзеге асырса, онда F формуласынан ƒ1,..., ƒ s функциясын
ƒ1*,..., ƒs* функциясына ауыстыру аркылы алынған С[ƒ1*,..., ƒs*] формуласы , ƒ* (х,,...,хn) функциясын жүзеге асырады.
Бұл формуланы F формуласына қосалқы формула деп атайды және F* арқылы белгілейді. Егер Ғ = С[0,1, ,х1&х2, (x1∨x2), онда F* =С[0,1, , (x1∨x2),x1&х2].
4.Буль функцияларын
х =хσ∨хσ белгілеуін енгізейік, мұндағы σ - нөлге немесе бірге тең параметр.
xσ =
хσ = 1 тек сол жағдайда, егер х = σ болса екендігіне оңай көз жеткізуге болады.
Теорема (Буль функцияларын айнымалыларға жіктеу туралы). Әрбір ƒ(х1,...,xn) логика алгебрасының функциясын кез-келген т(1 т п) үшін келесі түрде беруге болады :
ƒ (х1,...,xm,xm+1,…,xn)= x1 σ1 &…& xmσm ƒ(σ1,…,σm,xm+1,…,xn),
(*)
мұнда дизъюнкция х1,...,хm айньмалыларының барлық мүмкін болатын мәндері бойынша алынады.
Бұл көрініс функцияның х1,...,хm айнымалылары бойынша жіктелінуі деп аталады.
Салдар ретінде жіктеудің арнайы екі түрін аламыз.
Айнымалы бойынша жіктелу:
ƒ (х1,...,хn-1,хn) = хn & ƒ (x1,…,xn-1,1)v & ƒ(x1,…,xn-1,0).
ƒ (х1,..,хn-1,0) және ƒ(х1,...,xn-1,1) функциялары жіктеудің құрамдас бөліктері деп аталады.
ƒ (х1,...,xn)= x1 σ1 &…& xnσn ƒ(σ1,…,σn).
ƒ (х1,...,xn)≡0 орындалғанда жіктеу келесі түрге айналады
x1 σ1 &…& xnσn ƒ(σ1,…,σn) = x1 σ1 &…& xnσn
Нәтижесінде
ƒ (х1,...,xn)= x1 σ1 &…& xnσn
(**)
екендігін аламыз.
Мұндай жіктелу кемел дизъюнктивті нормалъ қалып деп аталады (кемел д.н.ф.).
Теорема. Логика алгебрасының әрбір функциясы жоққа шығару, конъюнция және дизъюнкция арқылы формула түрінде өрнектеле алады. Мысал. x1v х2 функциясының кемел д.н.ф.-ін табу керек болсын.
Функцияның мәні бірге тең болатын үш жинақ бар: (0,1), (1,0), (1,1). Сондықтан
x1 v x2 = x10 & x21 v x11& x20v x11& x21= & x1 v x1& v x1& x2.
Конъюнктивті нормаль қалып деп аталатын жіктеуді аламыз (кемел к.н.ф.):
ƒ (х1,...,xn)=
конъюнктивті нормаль калып деп аталатын жіктеуді аламыз (кемел к.н.ф.)
5.Толықтық және тұйықтық
Анықтама. Егер кез-келген Буль функциясы осы жүйенің функциялары арқылы формула түрінде жазылатын болса, онда Р2 жиынындағы {f1,f2,…,fs,…}функциялар жүйесі толық деп аталады.
Толық жүйелердің мысалдары:
1. Р2 жүйесі- барлық Буль функцияларынын жиыны -толық жүйе болып табылады.
2. G = { ,x1& х2,x1vx2 } жүйесі толық жүйе.
Кез-келген жүйе толық бола бермейді, мысалы G = {0,1} жүйесі толық емес. Келесі теорема бір жүйенің толықтығын негізге ала отырып екінші жүйенің толықтығын анықтауға мүмкіндік береді.
Теорема. Айталық Р2 жиынында екі функциялар жүйесі берілсін:
G={f1,f2,…},
D={g1,g2,…},
олар туралы мына жағдай белгілі: (I) жүйе толық және оның әрбір функциясы (II) жүйенің функциялары арқылы формула түрінде өрнектелген. Онда (II) жүйе толық.
Мысал:
D ={ ,x1&x2 } жүйесінің толық екендігін дәлелдеңіз.
Дәлелдеу: (I) жүйе ретінде
2 мысалдағы жүйені
{ ,x1& х2,x1vx2 }, ал (II) жүйе ретінде - D жүйесін аламыз.
x1vx2= тепе-теңдігін пайдаланамыз (элементар функциялардың касиетінен).
Сонымен, (I) жүйенің әрбір функциясы (II) жүйенің функциялары арқылы формула түрінде өрнектеледі. Яғни, (II) жүйе: { ,х1&х2} толық жүйе болып табылады.
6.Жегалкин теоремасы.
Р2 жиынындағы әрбір функция mod 2 бойынша көпмүшенің көмегімен өрнектеле алады (Жегалкин көпмүшесі бойынша) :
Мысал: (х1vх2) функциясын Жегалкин көпмүшесі түрінде өрнектеңіз.
(x1vx2)=ax1x2+bx1+cx2+d.
(0,0) жинағында: x1=x2=0Þ0=a·0+b·0+c·0+dÞd=0.
(0,1): x1=0,x1=1Þ1=a·0+b·0+c·1+dÞc=1.
(1,0): x1=1,x2=0Þ1=a·0+b·1+c·0+dÞb=1.
(1,1): x1=1,x2=1Þ1=a·1+b·1+c·1+dÞa=1.
(x1vx2)=x1x2+x1+x2
Толықтық ұғымымен тұйықтау және тұйык сыныптар ұғымдары тығыз байланысты.
Анықтама. Айталық М- Р2 жиынындағы функциялар ішжиыны болсын. М-нің тұйықтауы деп М жиынының функциялары арқылы формула түрінде беріле алатын барлық буль функцияларының жиыны аталады, [М] арқылы белгіленеді.