Автор: Пользователь скрыл имя, 12 Ноября 2011 в 09:20, реферат
Жалпы алғанда буль функцияларының жалған және елеулі айнымалыларының дискреттік математикада ойнайтын рөлі өте зор. Бірінші оларды теориялық тұрғыдан қарастырайық. Буль функцияларының жалған және елеулі айнымалылары деп .............. атайды.
Бұл айнымалылардың маңызы өте зор. Мысалы, функция көп айнымалы болса, кейбір айнымалыларын (жалған айнымалыларды) алып тастауға болады. Ол бізге барлық параметрлер бойынша үнемдеуге мүмкіндік береді. Сондықтан осы үнемдеуді жүзеге асыратын программдық пакет құру актуалды мәселе. Бұл жұмыста қойылған мақсат бойынша бірінші теориялық, одан кейін программалық жүзеге асыру жүргізілді.
Кіріспе..................................................................................3
Мазмұны 1
Кіріспе 2
Буль функцияларының жалған және елеулі айнымалылары 10
Есеп шығару мысалы 10
Буль функцияларының жалған және елеулі 12
айнымалыларын программада жүзеге асыру 12
ƒ (х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 жиынындағы функциялар ішжиыны болсын. М-нің тұйықтауы деп М жиынының функциялары арқылы формула түрінде беріле алатын барлық буль функцияларының жиыны аталады, [М] арқылы белгіленеді.
Мысал.
1)М = Р2. Бұл жағдайда [М] = Р2 .
2) М = {1,х1+х2} . [М] - L барлық сызықты функциялар сыныбы:
f(х1,...,хв) = с0+с1х1+...+сnxn, мұндағы с= 0,1(i =0,..,n), маңызды айнымалылар коэффициенті бірге тең де, жалған айнымалылар коэффициенті нөлге тең.
Тұйъқтаудыц қасиеттері
1)MÍ[M].
2)[[M]]=[M].
3) егер М1ÍМ2 , онда [М1]Í[М2] .
4) [M1ÈМ2] Ê[М1]È[М2] .
Анықтама.М сыныбы (жиыны) тұйық деп аталады, егер [М] = М.
Мысал.
1) М =Р2 сыныбы түйық сынып.
2) М = {1,x1+ х2} сыныбы тұйық емес.
Толықтық
анықтамасы бастапқыға эквивалентті :
М - толық жүйе, егер [M]=
Р2.
7.Маңызды жабық сыныптар. Толықтық туралы теорема.
Р2 жиыньшдағы маңызды түйық сыныптарды қарастырайық.
1. T0 арқылы барлық f (x1,…,xn) буль функцияларының тұрақты нөлді сақтайтын сыныбын белгілейік, яғни f(0,...,0) = 0 орындалатын функцияларды.
0,х,x1&х2, х1vх2,x1Åx2ÎT0,
1, ÏT0.
Т0- тұйық сынып.
T1 арқылы тұрақты бірді сақтайтын барлық буль функцияларының сыныбын белгілейміз, яғни f(1,...,1)=1 теңдігі орындалатын функциялар сыныбы:
1,x,x1&x2,x1vx2ÎT1,
0,
ÏT1.
T1 сыныбы T2 сыныбына қосалқы.
T1 сыныбы тұйық сынып
3.
S арқылы барлық өзіндік қосалқы
функциялар сыныбын
4. Жинақтардың векторлы жазылуын қолдана отырып:
=(a1,…, an), =(b1,…, bn), f (a1,…, an)=f ( ) екендігін аламыз.
Анықтама. Егер a1£ b1,...,an£bn шарты орындалса, онда = (a1,...,an) және =(b1,..., bn) екі жинағы үшін алдын алу қатынасы орындалады дейді.
Мысалы, (0,1,0,1) £ (1,1,0,1). Егер £ және £ , онда £ .