Лекция конспектісі «6В06103 Есептеу техникасы және бағдарламалық қамтамасыз ету» мамандығы үшін Шымкент 2023 «Деректер қорын құру және басқару»
жүктеу/скачать 2.71 Mb.
|
| Минимумдаушы карталар əдісі. Аса көрнекі жəне қарапайым əдіс – Вейч- Карно картасын пайдаланып минимумдау əдісі. Сонда ЛАФ-ты көрсету үшін графиктік өрнектеу əдісі қолданылады. Жапсыру жəне сіңіру операциясы графиктік (көзбен шолу) жолмен орындалады. Сонда 0-кубтарға сəйкес келетін
барынша көп “1” мəндерін жабыстыруға тырысады. Екі көрші “1” өз мəнін өзгертетін айнымалылары жоқ айнымалылар конъюнкциялармен белгіленетін 1-куб құрайды. Төрт көрші “1” белгіленуінде екі айнымалы жоқ болатын 2-куб құрайды. Сегіз көрші “1” 3-куб құрады. Оның айнымалылар конъюнкицясында үш айнымалы болмайды. Мысалы, 4 айнымалыдан тəуелді ЛАФ ЖҚДФ түрінде берілсін: f(x1,x2 ,x3 ,x4) = c 1c 2 c 3 c 4 Ú c 1 c 2 c 3 c 4 Ú c 1 c2 c3 c 4 Ú c1 c 2 c 3 c 4 2.3-суретте берілген ЛАФ графиктік түрде көрсетілген. Көрші төрт “1” 2- куб құрайды. Демек, f (c1c 2 c 3 c 4 ) = c1c 2 . Жалпы түрде Вейч-Карно картасын пайдалана минимумдау ережесін мына түрде тұжырымдауға болады: саны 2t (t = 1,2...) болатын көршілес “1” (0-кубтар) біріктіріліп, алғашқы 0-кубтарда əртүрлі мəн қабылдайтын айнымалылар орнына t бос компоненттері бар бір t-куб құрады. ЛАФ минималь өрнектеу үшін барлық 0-кубтар (біліктер) неғұрлым көп көлемді, бірақ аз мөлшерлі кубтармен жабылуы керек. Сонда бір ғана 0-куб бірнеше кубтар құрғанда пайдаланылуы мүмкін. Алынған кубтар дизъюнкция белгісімен біріктіріледі. Вейч-Карно картасы əдетте айнымалылар аз (n-1,2,3,4,5) болатын Бульдік функцияларды минимумдауға қолданылады. Егер n>4 болса Вейч-Карно картасы қарапайым карталардан (n-4) құрастырылады; мысалы n-5 болса, төрт айнымалы екі карта пайдаланылады. Ал n-6 болса, онда мұндай төрт карта пайдаланылады жəне т.с.с. Минимудау алдымен осы қарапайым карталардың ішінде жүргізіледі, одан барып қарапайым карталар арасындағы көрші торлар іздестіреді. Көрші торлар деп қарапайым карталарды бірінің үстіне бірін салғанда бір-біріне дəл келетін торларды айтады. x1 x2 x3 x4 00 01 11 10 00 01
11 1 1 1 1 10
Мысал. ЛАФ 2.3 – сурет. f (c1, c2 , c3 ) 0 мəнін үшінші (011) жəне жетінші (111) жиынтықтарда қабылдайды. Функцияны Пирс базисінде минимумдау үшін ЛАФ-ты ЖҚПФ түрінде жазып, жапсыру операциясын қолдану керек. f (c , c , c ) = (c ¯ c 2 ¯ c 2 ) ¯ (c 2 ¯ c 2 ¯ c 2 ) = (c 2 ¯ c 2 ). 1 2 3 1 2 3 1 2 3 2 3 Нəтиже бірмүшелік түрінде болғандықтан квадрат дəрежеге шығарылады. Қарастырылған базистерде бульдік функцияларды минимумдау мəселесін, ҚДФ пен ҚКФ өрнектеріне өтудің белгілі қатыстарын пайдаланып сəйкес ҚДФ пен ҚКФ функцияларын минимумдау мəселесіне келтіруге болатынын атап өтейік. жүктеу/скачать 2.71 Mb. Достарыңызбен бөлісу:
|