![]() Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
![]() Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
![]() |
Дәріс 3 Бульдік функцияларды аналитикалық көрсету. Бульдік функцияларды ықшамдауЛАФ аналитикалық жолмен көрсету. Кез келген логикалық алгебра функциясын базис құратын кейбір элементар функциялардың суперпозициясы арқылы көрсетуге болады. Бұл жерде ЛАФ минималь логикалық өрнек түрінде болуы мүмкін. ЛАФ аналитикалық жолмен өрнектеуге мүмкіндік беретін ең көп таралған дизьюнкция, коньюнкция, логикалық терістеу сияқты элементар функциялардан тұратын базис болып табылады. Бұл базисті бульдік базис ( Логикалық функциялардың ішінен аргументтердің тек бір жиынтығында ғана бірге айналатын, ал барлық қалған (2n-1) жиынтықтарда нольге айналатын функцияларды жеке (бөліп) атауға болады. Мұндай функциялар бірдің конституенті деген атқа ие болады. Элементар функциялар ішінен бұған дизьюнкция функциясы, Пирс (Вебба) функциясы және терістеу функциялары жатады. Бірдің констуенті анықтамасынан бірдің констуенті ретінде аргументтің логикалық функциясын беру үшін функцияны бірге айналдыратын бір ғана аргументтер жиынтығын берсе жеткілікті. Ол үшін коьюнкция белгісімен байланыстырылған тура немесе терістелген х1, х2,..., хn айнымалыларынан коньюнктивтік терм (минтерм) құрастырылған. Терм бірге тек бір ғана жиынтықта айналуға тиіс, ал басқа жиынтықтарда ноль мәнін алуға тиіс. Ол үшін көрсетілген жиынтықта нольге тең болатын айнымалылар терістеу белгісімен алынады. Егер ai жиынтықтағы xi айнымалысының мәні болса, онда функцияның жалпы түрі былай жазылады: f Логикалық функциялары бірге айналатын бірнеше жиынтықтар бар болса,онда олардың әрқайсысы бірдің конституентін (минтерм) түзеді де олар дизьюнкция белгісімен біріктіріледі. Мұның нәтижесінде логикалық өрнек ЛАФ аналитикалық өрнек түрінде алынады: f Бұл формулада Егер логика функциясын нольдің конституенті түрінде беру керек болса, онда дизьюнктивтік термді (макстермді) пайдаланады. Бұл жерде х1, х2,..., хn айнымалыларын тура немесе теріс формада алып, дизьюнкция белгісімен байланыстырады. Терм бір жиынтықта нольге, ал барлық қалған жиынтықтарда бірге айналуы керек. Ол үшін көрсетілген жиынтықтарда бірге тең айнымалылар терістеу белгісімен алынады. Функция жалпы түрде былай жазылады: f Бірнеше жиынтықта ноль мәнін алатын ЛАФ өрнектеу үшін бұл жиынтықтарды нольдің конституенттері (макстермдер) түрінде бере отырып, оларды коньюнкция белгісімен біріктіру қажет. Бұл жағдайда ЛАФ мына түрде жазылады: f 1) функция 1 мәнін қабылдайтын аргументтер жиынтықтарының бәрін белгілейді; 2) әрбір белгіленген жиынтық үшін аргументтер коньюнкциясын жазып алады; егер белгіленген жиынтықта аргумент 1 болса, онда алынған коньюнкция терістелмейді, ал қарсы жағдайда аргумент терістеледі; 3) алынған коньюнкциялар дизьюнкция белгісімен қосылады. Мысал. 2.6-кестеде ЛАФ үш аргументпен берілген. Осы ЛАФ ЖҚДФ алу үшін: 1) f(х1 х2 х3)=1 мәнін қабылдайтын аргументтер жиынтығын белгілейміз; 2) 3) алынған коньюнкцияларды дизьюнкция белгісімен қосамыз; f( Алынған аналитикалық өрнек f(х1, х2, х3) қалыпты деп аталады, өйткені терістеу белгілері аргументтердің функцияларына емес олардың өздеріне оның әрбір коньюнктивтік мүшелері n аргументтерден тұрады. 2.6 – кесте
Аналитикалық жолмен берілген ЛАФ өрнегінен кестелік өрнекке көшу былай орындалады: 1) аргументтердің барлық мүмкін болатын жиынтықтарының кестесі құрылады; 2) әр жиынтықтағы аргументтер мәнді ЛАФ аналитикалық жазылуына тікелей қойылады да элементар ЛАФ анықтамасы негізінде әрбір жиынтықта оның мәні есептеледі; 3) есептелген мән қаралған жиынтықта сәйкес келетін кесте жолына жазылады. Аналитикалық жолмен көрсетілген ЛАФ элементар фнкциялардың қасиеттерін пайдалана отырып түрлендіруге болады. Түрлендіру мақсаты-терм сандарын және термдегі айнымалыларды азайту, басқаша айтқанда минималь қалыпты форма алу. Әрбір айнымалысы бір реттен артық кездеспейтін терм элементар терм деп аталады. Термді құратын айнымалылар саны оның рангі (r) деп аталады. Бірдей айнымалылардан құрылған екі элементар терм бір-бірінентек бір айнымалы терістелуімен өзгеше болса, онда оларды көрші термдер деп атайды. Көрші термге мысал: Рангі r екі көрші терм дизьюнкциясын берілген термдердің ортақ бөлігі болатын рангі r-1 элементар ықшамдалған терммен ауыстыруға болады: Дизьюнктивтік термдерді жапсыру арқылы көрші тұрған екі (рангі) макстермдер коньюнкциясын бастапқы термдердің жалпы бөлігі болып келетін рангі r-1 элементар термдермен алмастыруға болады: y= Біреуі екіншісінің бөлігі болатын әр түрлі рангті екі элементар макстермдер коньюнкциясын рангі кіші макстерммен ауыстыруға болады: y= ЛАФ ықшамды түрін алу үшін оны жетілген қалыпты формада (коньюнктивтік немесе дизьюнктивтік) кескіндеп, оған жапсыру не сіңіру ережелерін қолдану керек. Мысал. 2.6-кестемен берілген функция үшін МҚДФ табу керек. Шешуі. Функцияның ЖҚДФ формасын жазып оны түрлендіреміз: f ( Түрлендіруде жапсыру ережесі тек бірдей сызықтармен сызылған термдерге қолдану арқылы жасалады. Бульдік функцияларды ықшамдау. Квайн-Мак-Класки әдісі. Жетілген қалыпты формалардан (ЖҚДФ және ЖҚКФ) тікелей минималь қалыпты формаларды (МҚДФ және МҚМФ) жапсыру және сіңіру ережелерін қайта-қайта қолдану арқылы алуға болады. Бұл ережелерді қолданғанда термдерді жүйесіз салыстыру кезінде минималь қалыпты формалар қажетті төменгі рангті термдер толық алынбауы мүмкін. Квайн әдісі 1952 жылы термдерді қос-қостан салыстыру операциясын ретке келтіріп, минималь қалыпты форманы алу алгоритмін анықтайды. Квайн әдісімен минимальдау үшін бастапқы функция ЖҚДФ берілген деп ұйғарылады. Оған кіретін барлық термдер қос-қостан салыстырылып, оларға қайсыбір айнымалы бойынша жапсыру операциясын қолданамыз: 1956 жылы Мак-Класки конъюнктивтік термдерді ( Сондықтан олардың жапсырылу ықтималдығы 0-ге тең. Төменде Квайнның Мак-Класки жетілдірген (Квайн-Мак-Класки әдісі) кезеңдерге бөлінген формальді алгоритмі баяндалады. 1-кезең. Бастапқы импликантты табу. ЖҚДФ-ға кіретін барлық {m} термдерді екілік айнымалылар жиынтығы 2-кезең. Импликанттық матрица құру. Матрицаның жолдарын бастапқы импликанттармен, ал бағандарын алғашқы (негізгі) импликанттармен (0-кубтармен) белгілейді. Егер бастапқы импликантта 3-кезең. Мәнді импликанттарды табу. Егер импликанттық матрицаның қайсыбір бағынында тек бір ғана белгі болса, онда осы белгіге сәйкес келетін алғашқы импликантта мәнді болып табылады, өйткені онсыз берілген термдердің барлық жиынтығын {m} алуға болмайды. Мәнді импликанттар міндетті түрде МҚДФ құрамына кіруі керек. Мәнді импликанттармен жабылатын термдерге сәйкес келетін бағандар және мәнді импликантты жолдар матрицадан сызылып тасталады. 4-кезең. Басы артық бастапқы импликанттарды сызып тастау. Алдыңғы кезеңдер орындалған соң, импликанттық матрицада бірде-бір белгісі жоқ жолдар пайда болуы мүмкін. Мұндай жолдарға сәйкес келетін бастапқы импликанттар әрі қарай қаралмайды, өйткені олар матрицадағы қалған алғашқы термдерді жаба алмайды. 5-кезең. Минималь жабын алу. Импликанттық матрицаның жолдары мен бағандарын сызып тастағанмен алынған матрица зерттеледі. Қалған жолдар ішінен қалған алғашқы термдерді тегіс жабатын бастапқы импликанттар жиынтығы іріктелініп алынады. Мұндай импликанттардан әріп сандарын аз жиынтық таңдалынып алынады. Оларға мәнді импликанттарды қосып, мөлшері әр-түрлі куб түрінде жазылған бастапқы импликанттардан рангі әр түрлі конъюнктивтік термдерге көшіріледі. Соңғыларды дизъюнкция белгісімен біріктіріп МҚДФ алынады. Мысал. Квайн-Мак-Класки әдісімен f(x1,x2,x3,x4) логикалық функциясының МҚДФ табу керек: f(x1,x2,x3 x4)= = Шешуі. К0 кешені
мұнда кешентердің төменгі индекстері топқа енетін кубтардағы бірліктер санын көрсетеді. 1-кезең. Бастапқы импликанттарды табу (* белгісімен жапсыру амалына қатысатын термдер белгіленеді). а)
салыстырылады, жапсыру нәтижесінде
салыстырылады, жапсыру амалынан кейін мынадай нәтижеге ие боламыз:
салыстырылады, жапсыру амалын орындай отырып мынадай нәтиже аламыз: Барлық 0-кубтар 1-кубтарды алуға қатысады, сондықтан олардың ешқайсысы бастапқы импликант болмайды. ә) Әрі қарай
б) 2-кезең. Импликанттық матрица құру. Импликанттық матрица 7 жолдан және 10 бағанадан тұрады. 2.7-кесте белгілері бар матрица келтірілген. 2.7 – кесте
3-кезең. Мәнді импликанттарды табу. Импликанттық матрицада бір белгілі тек бір ғана баған бар. Бұл белгіге 10ХХ мәнді импликантта сәйкес келеді. 2.7-кестеден мәнді 10ХХ импликантпен жабылатын баған –термдер және ол импликантқа сәйкес келетін жол сызылып тасталады. Соның нәтижесінде 2.8-кесте алынады. 4-кезең. Басы артық бастапқы импликанттарды сызып тастау. 2.8 – кесте
2.8-кестеде мұндай импликанттар жоқ. 5-кезең. Минималь жабу алу. 2.8-кестеден 4-рангті алты термдерді жабатын бастапқы импликанттар жиынтығы таңдалынып алынады: 1Х1Х,01Х1,Х100. Бұл жинақты мәнді импликантпен қоса конъюнктивтік термдерге өтіп МҚДФ алынады: f(x1,x2,x3,x4)= Ең соңғы бесінші кезеңде бастапқы импликанттардың басқа жиынтығын таңдауға болады: 1ХХ0,Х111,010Х. Мұндай жиынтықта f(x1,x2,x3,x4)= Табылған бірінші және екінші жазылуларда сан жағынан бірдей әріптер қолданылып отырғандықтан олардың екеуі де МҚДФ болып табылады. Қаралған әдісті МҚКФ үшін де қолдануға болады. Ол үшін мәні және осы мәнге сәйкес термдер қаралады. Минимумдаушы карталар әдісі. Аса көрнекі және қарапайым әдіс – Вейч-Карно картасын пайдаланып минимумдау әдісі. Сонда ЛАФ-ты көрсету үшін графиктік өрнектеу әдісі қолданылады. Жапсыру және сіңіру операциясы графиктік (көзбен шолу) жолмен орындалады. Сонда 0-кубтарға сәйкес келетін барынша көп “1” мәндерін жабыстыруға тырысады. Екі көрші “1” өз мәнін өзгертетін айнымалылары жоқ айнымалылар конъюнкциялармен белгіленетін 1-куб құрайды. Төрт көрші “1” белгіленуінде екі айнымалы жоқ болатын 2-куб құрайды. Сегіз көрші “1” 3-куб құрады. Оның айнымалылар конъюнкицясында үш айнымалы болмайды. Мысалы, 4 айнымалыдан тәуелді ЛАФ ЖҚДФ түрінде берілсін: f(x1,x2,x3,x4) 2.3-суретте берілген ЛАФ графиктік түрде көрсетілген. Көрші төрт “1” 2-куб құрайды. Демек, f Жалпы түрде Вейч-Карно картасын пайдалана минимумдау ережесін мына түрде тұжырымдауға болады: саны Вейч-Карно картасы әдетте айнымалылар аз (n-1,2,3,4,5) болатын Бульдік функцияларды минимумдауға қолданылады. Егер n>4 болса Вейч-Карно картасы қарапайым карталардан (n-4) құрастырылады; мысалы n-5 болса, төрт айнымалы екі карта пайдаланылады. Ал n-6 болса, онда мұндай төрт карта пайдаланылады және т.с.с. Минимудау алдымен осы қарапайым карталардың ішінде жүргізіледі, одан барып қарапайым карталар арасындағы көрші торлар іздестіреді. Көрші торлар деп қарапайым карталарды
Мысал. ЛАФ Нәтиже бірмүшелік түрінде болғандықтан квадрат дәрежеге шығарылады. Қарастырылған базистерде бульдік функцияларды минимумдау мәселесін, ҚДФ пен ҚКФ өрнектеріне өтудің белгілі қатыстарын пайдаланып сәйкес ҚДФ пен ҚКФ функцияларын минимумдау мәселесіне келтіруге болатынын атап өтейік.
|