Логика алгебрасының функциялары



                                                                                                                                             

Мазмұны

 

Кіріспе..................................................................................3

 

Кіріспе

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

Бұл айнымалылардың маңызы өте зор. Мысалы, функция көп айнымалы болса, кейбір айнымалыларын (жалған айнымалыларды) алып тастауға болады. Ол бізге барлық параметрлер бойынша үнемдеуге  мүмкіндік береді. Сондықтан осы үнемдеуді жүзеге асыратын программдық пакет құру актуалды мәселе. Бұл жұмыста қойылған мақсат бойынша бірінші теориялық, одан кейін программалық жүзеге асыру жүргізілді.

 

 

ЛОГИКА АЛГЕБРАСЫ

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 -ге тең.                                                             

Логика алгебрасы функцияларың мысалдары: 

  1. ƒ1(x) =0 -тұрақты 0
  2. ƒ2(x) =1-тұрақты 1;                                       
  3. ƒ3(x)=x –тепе-тең функция;
  4. ƒ4(x)= - х -ті жоққа шығару;
  5. ƒ5(x1,x2)= (x1&x2) - x1 мен x2 –нің конъюнкциясы (логикалық көбейту);
  6. ƒ6(x1,x2)= (x1∨x2) - x1 мен x2 –нің дизъюнкциясы (логикальщ қосу);
  7. ƒ6(x1,x2)=Бұл функциялардың мәні.

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)

функциясына қосалқы функция деп аталады.

  • 0 функциясы 1 функцияға қосалқы,                  
  • 1 функциясы 0 функциясына қосалқы,
  • x функциясы х функциясына қосалқы,
  • функциясы функциясына қосалқы,
  • х&х2 функциясы х1vх2 функциясына қосалқы,

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. Барлық айньмалылар бойынша жіктеу:

ƒ (х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,…},                                                                                  (I)

D={g1,g2,…},                                                                                (II)

олар туралы мына жағдай белгілі: (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 арқылы барлық өзіндік  қосалқы функциялар сыныбын белгілейміз,  яғни P2 жиынындағы f * = f шарты орындалатын функциялар сыныбы.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). Егер £ және £ , онда £ .

Анықтама. Егер £ шарты орындалатын кез-келген және жинақтары үшін f ( )£f ( ) теңсіздігі орындалса, онда     f (х1,...,хп) функциясы монотонды деп аталады.

М арқылы барлық монотонды  функциялар жиынын белгілейік. 0,1, х, x1 & х2, х1 v х2 Î М. М сыныбы тұйық.

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

0,1,x, ,x1Åx2ÎL ,x1&x2, х1 v х2ÏL. L сыныбы тұйық.

Алгебра логикасының  негізгі есептерінің бірі- толықтылықтың қажетті және жеткілікті шарттарын қарастырайық.

Айталық G={f1,f2,..,f5,...} - Р2 жиынындағы кез-келген функциялар жүйесі болсын.

Осы жүйенің толықтылығын калай анықтауға болатынына келесі теорема береді.

Теорема (функционалды толықтық туралы).

G функциялар жүйесі толық болуы үшін оның келесі бес тұйық сыныптың T0,T1,S,M және L бірде біреуінде толығымен   жатпауы   қажетті де жеткілікті.

 

8.Пост нәтижелері

Р2 жиынындағы тұйық сыныптарды американ математигі Э. Пост терең зерттеген. Ол Р2 жиынындағы барлық түйық сыныптардың құрылымы сипатталған.

Анықтама. М тұйық сыныбындағы {f1,f2,…,fs,…} функциялар жүйесі толық деп аталады, егер оның тұйықтауы М сыныбымен беттеседі.

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

Анықтама. Егер ол  М сыныбында толық , ал оның кез-келген өзіндік ішжиыны     М сыныбында толық болмаса, онда М тұйық сыныбындағы функциялар жүйесі {f1,f2,...,fs,...} оньщ базисі деп аталады. Мысалдар.

1)f1=x1x2, f2=0, f3=1, f4=x1Åx2Åx3  функциялар жүйесі Р2  жиынының базисі боып табылады. Дәлелдеу:

 { x1x2,0,1,x1Åx2Åx3}- Р2 жиынында толық.

{ x1x2,0,1}- Р2 жиынында толық емес.

2)  {0,1,x1&x2, х1 v х2} функциялар жүйесі М сыныбының базисі болып табылады.

1 Пост теоремасы. Р2 жиынындағы әрбір тұйық сынып ақырлы базиске ие.

2 Пост теоремасы. Р2 жиынындағы тұйық сыныптар жиынындағы қуаты санаулы.

Буль  функцияларының жалған және елеулі айнымалылары

Анықтама. Егер і-ші құрамдас бөлік бойынша көршілес және жинақтары табылатын болса, онда f (x1,…,xi-1,xi,xi+1,…,xn) функциясының xi (1£i£n) айнымалысы елеулі деп аталады (яғни

f ( )¹f ( ) қатынасы орындалатындай =(a1,...,ai-1,0,ai+1,…,an) және =(a1,...,ai-1,1,ai+1,…,an)  табылса). Кері жағдайда xi (1£i£n) айнымалысы f (x1,…,xi-1,xi,xi+1,…,xn) функциясының жалған айнымалысы деп аталады.

Анықтама. Егер f ( ) және g( ) функциялардың маңызды айнымалылар жиыны бетессе және кез келген және  жинақтарда функциялардың мәндері бірдей болса:

f ( )=g( ),онда  f ( ) және g( ) функциялары тең деп аталады. Егер f ( ) және g( ) функциялары тең болса, онда олардың біреуін екіншісінен жалған айнымалыларды қосу немесе алып тастау арқылы алуға болады.

Есеп шығару мысалы

f( ) =(11110011) функциясының барлық жалған және елеулі айнымалыларын табу керек:

ШЕШІМІ: Бұл функция үшін келесі кестені сызамыз:

 

 

x1   x2   x3

f( ) =( x1, x2, x3)

0   0   0

       0

0   0   1

       0

0   1   0

       1

0   1   1

       1

1   0   0

       1

1   0   1

       1

1   1   0

       0

1   1   1

       0


x1: f(0,0,0)¹f(1,0,0) яғни, берілген функцияның мәндері сәйкес келмейтін жинақты табуға болады. Қорытынды  - x1айнымалысы f( ) функциясының елеулі аргументі.

x2: f(1,0,0)¹ f(1,1,0), яғни x2 айнымалысы f( ) функциясының елеулі аргументі.

x3: f(0,0,0)=f(0,0,1)=0, f(0,1,0)=f(0,1,1)=1, f(1,0,0)=f(1,0,1)=1, f(1,1,0)=f(1,1,1,)=0, яғни берілген функцияның мәндері барлық көршілес жинақтарда бірдей.

 

Буль  функцияларының жалған және елеулі

айнымалыларын программада жүзеге асыру

 

Программалық жүзеге асыру негізінен Delphi  ортасында орындалды.Ол төменде  көрсетілген:

 

unit Finder;

 

interface

 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls, Grids;

 

type

  TForm1 = class(TForm)

    ComboBox1: TComboBox;

    RadioGroup1: TRadioGroup;

    Button1: TButton;

    Edit1: TEdit;

    StringGrid1: TStringGrid;

    Button2: TButton;

    Button3: TButton;

    Label1: TLabel;

    Label2: TLabel;

    procedure Button1Click(Sender: TObject);

    procedure Edit1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

Type IntType = LongInt;

    Mas = Array [1..10000] Of IntType;

var

  Form1     : TForm1;

  intVar    : IntType;

  mT        : Mas;

 

implementation

 

{$R *.dfm}

 

FUNCTION Power(X : IntType; P : IntType) : IntType;

Var Ret : IntType;

    i  :IntType;

Begin

  If (p=0)or(x=1) then

  Begin

    Power:=1;

    Exit;

  End;

  Ret:=1;

  For i:=1 to P do

  Begin

    Ret:=Ret*X;

  End;

  Power:=Ret;

End;

 

FUNCTION Meaning(X,Y : IntType) : IntType;

Var j, Ret : IntType;

Begin

  If X=1 then

  Begin

    Meaning:=0;

    Exit;

  End;

  Ret:=0;

  x:=x-1;

  For j:=1 to Y do

  Begin

    Ret:=X mod 2;

    X:=X div 2;

  End;

  Meaning:=Ret;

End;

 

procedure TForm1.Button1Click(Sender: TObject);

Var i, j : IntType;

begin

  If RadioGroup1.ItemIndex=-1 then

  Begin

    ShowMessage('Выберите функцию');

    Exit;

  End Else

  If RadioGroup1.ItemIndex=0 then

  Begin

    Try

      intVar:=StrToInt(Edit1.Text);

    Except

      ShowMessage('Ввведите, все-таки, кол-во переменных');

      Exit;

    End;

  //Строим  таблицу для удобства

    StringGrid1.Visible:=True;

    StringGrid1.ColCount:=intVar+1;

    StringGrid1.RowCount:=Power(2,intVar)+1;

    For i:=1 to StringGrid1.ColCount-1 do

      StringGrid1.Cells[i,0]:='x'+IntToStr(i);

    For i:=1 to StringGrid1.RowCount-1 do

      StringGrid1.Cells[0,i]:=IntToStr(i)+')';

    StringGrid1.ColCount:=StringGrid1.ColCount+1;

    StringGrid1.Cells[StringGrid1.ColCount-1,0]:='Function Value';

    Button2.Visible:=True;

    For i:=1 to StringGrid1.RowCount-1 do

      For j:=1 to StringGrid1.ColCount-2 do

        StringGrid1.Cells[j,i]:=IntToStr(Meaning(i,StringGrid1.ColCount-2-j+1));

  End

  Else

  If RadioGroup1.ItemIndex=1 then

  Begin

    StringGrid1.Visible:=True;

    Button3.Visible:=True;

    StringGrid1.EditorMode:=True;

    Try

      intVar:=StrToInt(Edit1.Text);

    Except

      ShowMessage('Ввведите, все-таки, кол-во переменных');

      Exit;

    End;

    StringGrid1.Visible:=True;

    StringGrid1.ColCount:=intVar+1;

    StringGrid1.RowCount:=Power(2,intVar)+1;

    For i:=1 to StringGrid1.ColCount-1 do

      StringGrid1.Cells[i,0]:='x'+IntToStr(i);

    For i:=1 to StringGrid1.RowCount-1 do

      StringGrid1.Cells[0,i]:=IntToStr(i)+')';

    StringGrid1.ColCount:=StringGrid1.ColCount+1;

    StringGrid1.Cells[StringGrid1.ColCount-1,0]:='Function Value';

    Button2.Visible:=True;

    For i:=1 to StringGrid1.RowCount-1 do

      For j:=1 to StringGrid1.ColCount-2 do

        StringGrid1.Cells[j,i]:=IntToStr(Meaning(i,StringGrid1.ColCount-2-j+1));

    StringGrid1.Options:=[goEditing];

  End;

  RadioGroup1.Visible:=False;

  Button1.Visible:=False;

  ComboBox1.Enabled:=True;

end;

 

procedure TForm1.Edit1Click(Sender: TObject);

begin

  Edit1.SelectAll;

end;

 

procedure TForm1.Button2Click(Sender: TObject);

Var Ret, i, j, N, M, p, k: IntType;

   Bol : Boolean;

   mT1 : Mas;

begin

  //Main Algorythm Block

  If ComboBox1.ItemIndex=-1 then

  Begin

    ShowMessage('Выберите функцию');

    Exit;

  End;

 

  If ComboBox1.ItemIndex=0 then

  Begin

    For i:=1 to StringGrid1.RowCount-1 do

    Begin

      Ret:=0;

      For j:=1 to StringGrid1.ColCount-2 do

        Ret:=Ret or StrToInt(StringGrid1.Cells[j,i]);

      StringGrid1.Cells[StringGrid1.ColCount-1,i]:=IntToStr(Ret);

    End;

  End;

 

  If ComboBox1.ItemIndex=1 then

  Begin

    For i:=1 to StringGrid1.RowCount-1 do

    Begin

      Ret:=1;

      For j:=1 to StringGrid1.ColCount-2 do

        Ret:=Ret and StrToInt(StringGrid1.Cells[j,i]);

      StringGrid1.Cells[StringGrid1.ColCount-1,i]:=IntToStr(Ret);

    End;

  End;

 

  //Finding Fictive Vars

 

  M:=StringGrid1.ColCount-2;

  N:=StringGrid1.RowCount-1;

 

  For i:=1 to N do

    mT[i]:=StrToInt(StringGrid1.Cells[M+1,i]);

  k:=0;

  For i:=1 to M do

  Begin

    FillChar(mT1, SizeOf(mT1), 0);

    For j:=1 to N do

    Begin

      p:=Power(2,i-1);

      If ((j=1)or(mT1[j]<>-1))and(j+p<=N) then

      Begin

        Bol:=(mT[j]=mT[j+p]);

        If not Bol then

        Begin

          Label1.Caption:=Label1.Caption+' x'+IntToStr(M-i+1);

          k:=1;

          mT1[j]:=-1;

          mT1[j+p]:=-1;

          Break;

        End;

      End;

    End;

    If k=0 then

    Begin

      Label2.Caption:=Label2.Caption+' x'+IntToStr(M-i+1);

    End

    Else

      k:=0;

  End;

 

  // End Of Finding Fictive Vars

end;

 

procedure TForm1.Button3Click(Sender: TObject);

Var j, i, n, m, p, k : IntType;

     Bol : Boolean;

     mT1 : Mas;

begin

  ComboBox1.Enabled:=False;

 

   //Finding Fictive Vars

 

  M:=StringGrid1.ColCount-2;

  N:=StringGrid1.RowCount-1;

 

  For i:=1 to N do

    mT[i]:=StrToInt(StringGrid1.Cells[M+1,i]);

   

  k:=0;

  Label1.Caption:='Vulnerable:';

  Label2.Caption:='Fictive:';

  For i:=1 to M do

  Begin

    FillChar(mT1, SizeOf(mT1), 0);

    For j:=1 to N do

    Begin

      p:=Power(2,i-1);

      If ((j=1)or(mT1[j]<>-1))and(j+p<=N) then

      Begin

        Bol:=(mT[j]=mT[j+p]);

        If not Bol then

        Begin

          Label1.Caption:=Label1.Caption+' x'+IntToStr(M-i+1);

          k:=1;

          Break;

        End;

        mT1[j]:=-1;

        mT1[j+p]:=-1;

      End;

    End;

    If k=0 then

    Begin

      Label2.Caption:=Label2.Caption+' x'+IntToStr(M-i+1);

    End

    Else

      k:=0;

  End;

 

  // End Of Finding Fictive Vars

 

end;


end.

 

 

 

 

Қорытынды

 

Қорытындылай келе жасалған жұмыстың нәтижелерін белгілейік:

  1. Алынған тақырып бойынша толық теориялық талдау жүргізілді.
  2. Талдау бойынша жалған және елеулі айнымалыларды табу алгоритмі толықтай, өзге қосымша алгоритмдерді қолдана отырып, жүзеге асырылды.

Авторлармен жұмыс барысында  келесі ескертулер енгізілді:

  1. Программа қолданысы кезіндегі кейбір шектеулер.
  2. Көп айнмалылармен жұмыс істегендегі програма орындалуының тездігі.

 

Қолданылған әдебиеттер тізімі:

 

  1. Яблонский С.В., “Введение в дискретную математику”, М., Высшая школа, 2002
  2. Акимов О.Е., Дикретная математика, М., Лаборатория базовых знаний, 2001
  3. Новиков, Дискретная математика для программистов, Питер, 2003
  4. Тірек конспект,КБТУ, 2003,

 


Логика алгебрасының функциялары 📙 Реферат → 🆔 138543

Логика алгебрасының функциялары 📙 Реферат → 🆔 138543

Логика алгебрасының функциялары