Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Апрель 24, 2022  •  Контрольная работа  •  2,360 Слов (10 Страниц)  •  324 Просмотры

Страница 1 из 10

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-кесте.

x1x2x3

ƒ(x1,x2,x3)

 х1x2x3

ƒ(x1,x2,x3)

000

001

010

011

1

0

0

0

100

101

110

111

1

1

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(η)-η д.қ.ф. да қатысатын э.к. саны.  Lk1)=5, Lk2)=2 .

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

...

Скачать:   txt (17.9 Kb)   pdf (206.8 Kb)   docx (641.7 Kb)  
Продолжить читать еще 9 страниц(ы) »
Доступно только на Essays.club