Бульдік функцияларды минимизациялау
Автор: ballzhan • Апрель 24, 2022 • Контрольная работа • 2,360 Слов (10 Страниц) • 316 Просмотры
7-лекция
Бульдік функцияларды минимизациялау
мәселелері
- Негізгі анықтамалар және ұғымдар.
- Тұйықты дизъюнктивті қалыпты формалар.
- Минимизация мәселесінің геометрикалық анықтамасы.
- Синтез мәселесін шешудің элементар әдістері.
______________________________________________________________
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(η)-η д.қ.ф. да қатысатын э.к. саны. Lk(η1)=5, Lk(η2)=2 .
3. Lo(η)- ¬ функцияның η д.қ.ф. дағы саны. Lo(η1)=7, Lo(η2)=2.
...