Бульдік функцияларды минимизациялау

7-лекция

Бульдік функцияларды минимизациялау

мәселелері

1. Негізгі анықтамалар және ұғымдар.
2. Тұйықты дизъюнктивті қалыпты формалар.
3. Минимизация мәселесінің геометрикалық анықтамасы.
4. Синтез мәселесін шешудің элементар әдістері.

______________________________________________________________

                 1.  Негізгі анықтамалар және ұғымдар.

Айталық  {x1,x2,…,xn} айнымалылар алфавиті берілген болсын.

1-анықтама.      

                        Κ=Xi1σ1 & Xi2σ2& …& Xirσr  (iμ ≠ jω,  μ≠ω болғанда)

өрнек элементар конъюнкция (э.к.) деп айтылады, бұл жерде r саны элементар конъюнкцияның  рангі (дәрежесі) деп қабылданған.

Анықтама бойынша 1 тұрақтының рангі 0 ге тең.

2-анықтама.      s

                             η    =  V  Кi        (Кi≠ Кj , i≠j )

                               i=1 

өрнек дизъюнктивті қалыпты форма (д.қ.ф.)  деп айтылады, мунда  Кi (i=1,2,…,s)  рангі  ri  ге тең болған элементар конъюнкция.

Алдын қарастырылған тақырыптардан η  д.қ.ф. өзіне сәйкес болған ƒ(x1,…,xn) буль функциясын іске асыратындығын білеміз, яғни ƒ(x1,x2,…,xn)=η.  Осындай д.қ.ф. ретінде кемел д.қ.ф. ны  қарастыруымыз  мүмкін:  

                           η    =      V     x1σ1 & x2σ2   &…&xnσn 

                               (σ1σ2…σn)

                                ƒ(σ1σ2…σn)=1

Мысал.  ƒ(x1,x2,x3) функция төмендегі 1-кесте арқылы берілген болсын.

                                                                                        1-кесте.

Оны кемел д. қ.ф. ретінде жазамыз:

       η1= ¬x1¬x2 ¬x3 v  x1¬x2¬x3 v x1¬ x2x3 v x1x2¬x3 v x1x2x3 

Сонымен кестедегі функцияны тағыда бір д.қ.ф. іске асыратындығын талдау арқылы көруіміз мүмкін:  η2= ¬x2¬x3 v x1 .

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

Соның үшін осыған байланысты болған д.қ.ф. лардың “күрделігін” бейнелейтін L(η) қолайлық индексі еңгіземіз:

1. Lә(η)-η  д.қ.ф. да  қатысатын айнымалы әріптер саны.

Қаралған мысалда  Lә(η1)=15, Lә(η2)=3,  яғни қолайлық жағынан η2 д.қ.ф.  η1 д.қ.ф. ға салыстырғанда өте жәй формула екендігі көрінеді.

2. Lk(η)-η д.қ.ф. да қатысатын э.к. саны.  Lk(η1)=5, Lk(η2)=2 .

3. Lo(η)- ¬ функцияның  η д.қ.ф. дағы саны.  Lo(η1)=7,  Lo(η2)=2.