Лекция конспектісі «6В06103 Есептеу техникасы және бағдарламалық қамтамасыз ету» мамандығы үшін Шымкент 2023 «Деректер қорын құру және басқару»
жүктеу/скачать 2.71 Mb.
|
- Бұл бет үшін навигация:
- Бульдік функцияларды ықшамдау. Квайн-Мак-Класки
| n
= c a1 Ú ca2 Ú ...Ú ca n = Ú cai , бұл жерде c i ai ìï=c ai ,a = í i i = 0üï ý 1 2 n 1 2 n i=1 i ïîc i ,ai = 1 ïþ Бірнеше жиынтықта ноль мəнін алатын ЛАФ өрнектеу үшін бұл жиынтықтарды нольдің конституенттері (макстермдер) түрінде бере отырып, оларды коньюнкция белгісімен біріктіру қажет. Бұл жағдайда ЛАФ мына түрде жазылады: f (c , c ,..., c ) = &(c a1 Ú c a2 Ú ...Ú c an ), формулада & -коньюнкция 1 2 n 0 1 2 n 0 функция ноль мəнін алатын жиынтықтардан құрылатындығын көрсететін белгі. Логика алгебрасы функциясын нольдің конституенттері коньюнкциясы түрінде өрнектеу қалыпты коньюктивті форма (ҚКФ) деп аталады. Егер барлық макстермдерде n айнымалылардың бəрі бар болса, онда ҚКФ жетілген (ЖҚКФ) деп аталады. Кез келген ЛАФ ЖҚКФ немесе ЖҚДФ түрінде жазылады. Кесте түрінде берілген логикалық алгебра функциясының ЖҚДФ алу үшін: функция 1 мəнін қабылдайтын аргументтер жиынтықтарының бəрін белгілейді; əрбір белгіленген жиынтық үшін аргументтер коньюнкциясын жазып алады; егер белгіленген жиынтықта аргумент 1 болса, онда алынған коньюнкция терістелмейді, ал қарсы жағдайда аргумент терістеледі; алынған коньюнкциялар дизьюнкция белгісімен қосылады. Мысал. 2.6-кестеде ЛАФ үш аргументпен берілген. Осы ЛАФ ЖҚДФ алу үшін: 1) f(х1 х2 х3)=1 мəнін қабылдайтын аргументтер жиынтығын белгілейміз; 2) c1 c 2 c 3 , c1 c 2 c3 , c1 c 2 c 3 , c1c 2 c 3 коньюнкцияларын жазып аламыз; 3) алынған коньюнкцияларды дизьюнкция белгісімен қосамыз; f( c1 , c 2 , c 3 )= c1 c 2 c3 Ú c1 c 2 c3 Ú c1 c 2 c 3 Ú c1c 2 c3 . Алынған аналитикалық өрнек f(х1, х2, х3 ) қалыпты деп аталады, өйткені терістеу белгілері аргументтердің функцияларына емес олардың өздеріне оның əрбір коньюнктивтік мүшелері n аргументтерден тұрады. – кесте
Аналитикалық жолмен берілген ЛАФ өрнегінен кестелік өрнекке көшу былай орындалады: аргументтердің барлық мүмкін болатын жиынтықтарының кестесі құрылады; əр жиынтықтағы аргументтер мəнді ЛАФ аналитикалық жазылуына тікелей қойылады да элементар ЛАФ анықтамасы негізінде əрбір жиынтықта оның мəні есептеледі; есептелген мəн қаралған жиынтықта сəйкес келетін кесте жолына жазылады. Аналитикалық жолмен көрсетілген ЛАФ элементар фнкциялардың қасиеттерін пайдалана отырып түрлендіруге болады. Түрлендіру мақсаты-терм сандарын жəне термдегі айнымалыларды азайту, басқаша айтқанда минималь қалыпты форма алу. Əрбір айнымалысы бір реттен артық кездеспейтін терм элементар терм деп аталады. Термді құратын айнымалылар саны оның рангі (r) деп аталады. Бірдей айнымалылардан құрылған екі элементар терм бір-бірінентек бір айнымалы терістелуімен өзгеше болса, онда оларды көрші термдер деп атайды. Көрші термге мысал : c1c2 c3 Ú c1c2 c3 . Рангі r екі көрші терм дизьюнкциясын берілген термдердің ортақ бөлігі болатын рангі r-1 элементар ықшамдалған терммен ауыстыруға болады: c1c2 c3 Ú c1c2 c 3 = c1c2 . Біреуі екіншісінің бөлігі болатын, рангтері əр түрлі екі элементар минтермдердің дизьюнкциясын кіші рангті минтерммен ауыстыруға болады: y = c1c2 c3 Ú c1c2 = c1c2 Дизьюнктивтік термдерді жапсыру арқылы көрші тұрған екі (рангі) макстермдер коньюнкциясын бастапқы термдердің жалпы бөлігі болып келетін рангі r-1 элементар термдермен алмастыруға болады: y= (c 1 Ú c2 Ú c3 )(c1 Ú c 2 Ú c3 ) = (c1 Ú c3 ) Біреуі екіншісінің бөлігі болатын əр түрлі рангті екі элементар макстермдер коньюнкциясын рангі кіші макстерммен ауыстыруға болады: y= (c 1 Ú c2 Ú c3 )(c1 Ú c3 ) = (c1 Ú c3 ) ЛАФ ықшамды түрін алу үшін оны жетілген қалыпты формада (коньюнктивтік немесе дизьюнктивтік) кескіндеп, оған жапсыру не сіңіру ережелерін қолдану керек. Мысал. 2.6-кестемен берілген функция үшін МҚДФ табу керек. Шешуі. Функцияның ЖҚДФ формасын жазып оны түрлендіреміз: f ( c1, c2 , c3 )= c1 c 2 c3 Ú c1 c 2 c 3 Ú c1 c 2 c3 Ú c1c2 c3 = c 2 c3 Ú c1 c 2 Ú c1c3 Түрлендіруде жапсыру ережесі тек бірдей сызықтармен сызылған термдерге қолдану арқылы жасалады. Бульдік функцияларды ықшамдау. Квайн-Мак-Класки əдісі. Жетілген қалыпты формалардан (ЖҚДФ жəне ЖҚКФ) тікелей минималь қалыпты формаларды (МҚДФ жəне МҚМФ) жапсыру жəне сіңіру ережелерін қайта- қайта қолдану арқылы алуға болады. Бұл ережелерді қолданғанда термдерді жүйесіз салыстыру кезінде минималь қалыпты формалар қажетті төменгі рангті термдер толық алынбауы мүмкін. Квайн əдісі 1952 жылы термдерді қос-қостан салыстыру операциясын ретке келтіріп, минималь қалыпты форманы алу алгоритмін анықтайды. Квайн əдісімен минимальдау үшін бастапқы функция ЖҚДФ берілген деп ұйғарылады. Оған кіретін барлық термдер қос-қостан салыстырылып, оларға қайсыбір айнымалы бойынша жапсыру операциясын қолданамыз: Fc1 Ú F c1 = F . Мұнда F-r=(n-1) рангті терм. Сонымен терм рангін r=n -нен r=n-1 -ге дейін төмендетіледі. Бұл операция қажетінше қайталанады. Жапсыру операциясына қатыспайтын термдерді бастапқы импликанттар деп атайды. Дизъюнкция белгісімен байланысқа бастапқы импликанттар жиыны МҚДФ түрінде бола бермейді. Сондықтан алынған импликанттар жиыны кейбір бастапқы импликанттарды алып тастау жолымен ықшамдалады. Алып тасталған имплианттар функцияның тепе-теңдігін бұзбауы керек. Квайн əдісінің елеулі кемістігі жапсыру амалын қолдану үшін барлық термдерді қос- қостан салыстыру керектігінде. 1956 жылы Мак-Класки конъюнктивтік термдерді ( c a1 , c a 2 ,..., c a n ) екілік 1 2 n айнымалылар жиынтығы түрінде жазуды ұсынды. Мұнда термге t-куб сəйекстендіріледі. Бұл термдердің епетейсіз жазылуынан айырып, жапсыру операциясын қолдану үстінде термдерді қос-қосап салыстыру санын қысқартуға мүмкіндік береді. Өйкені барлық a1,a2 ,...,aп айнымалылар жиынтықтарын олардағы бірліктер санымен қиылыспайтын топтарға бөлуге болады, і-топқа і-бірліктері бар барлық жиынтықтар кіреді. Бұл жағдайда тек көршілес топтағы жиынтықтар бір-бірімен салыстырылады. (i-1) топ пен і топ; і топпен і+1 топ жəне т.с.с. көршілес емес топтарға кіретін жиынтықтар бір- бірімен кем дегенде екі бірліктермен өзгеше болады. Сондықтан олардың жапсырылу ықтималдығы 0-ге тең. Төменде Квайнның Мак-Класки жетілдірген (Квайн-Мак-Класки əдісі) кезеңдерге бөлінген формальді алгоритмі баяндалады. -кезең. Бастапқы импликантты табу. ЖҚДФ-ға кіретін барлық {m} 0 термдерді екілік айнымалылар жиынтығы a1,a2 ,...,aп түрінде (0-кубтар К кешені) топтап олардағы бірліктер санына қарай жазып алады. Көршілес екі жиынтыққа жапсыру амалы қолданылады. Нəтижелерді топтап 1-кубтар К1 кешені түрінде жазылады. Көршілес топтарға (К1) кіретін 1-кубтар бір-бірімен салыстырып 2-кубтар түзіледі. Бұл салыстыру жəне жапсыру амалдары t кубтардың Kt кешентерін алғанша орындалады. Олар бір-бірімен жапсырылуы тиісті емес. Жапсыру амалдарына қатыспаған кубтар бастапқы импликанттар {l} жиынтығын құрады. -кезең. Импликанттық матрица құру. Матрицаның жолдарын бастапқы импликанттармен, ал бағандарын алғашқы (негізгі) импликанттармен (0- кубтармен) белгілейді. Егер бастапқы импликантта l i j i m j терміне енсе(l кубын 0 - куб m жабады)онда і жолымен j баған қиылысқан жеріне белгі қойылады. -кезең. Мəнді импликанттарды табу. Егер импликанттық матрицаның қайсыбір бағынында тек бір ғана белгі болса, онда осы белгіге сəйкес келетін алғашқы импликантта мəнді болып табылады, өйткені онсыз берілген термдердің барлық жиынтығын {m} алуға болмайды. Мəнді импликанттар міндетті түрде МҚДФ құрамына кіруі керек. Мəнді импликанттармен жабылатын термдерге сəйкес келетін бағандар жəне мəнді импликантты жолдар матрицадан сызылып тасталады. -кезең. Басы артық бастапқы импликанттарды сызып тастау. Алдыңғы кезеңдер орындалған соң, импликанттық матрицада бірде-бір белгісі жоқ жолдар пайда болуы мүмкін. Мұндай жолдарға сəйкес келетін бастапқы импликанттар əрі қарай қаралмайды, өйткені олар матрицадағы қалған алғашқы термдерді жаба алмайды. -кезең. Минималь жабын алу. Импликанттық матрицаның жолдары мен бағандарын сызып тастағанмен алынған матрица зерттеледі. Қалған жолдар ішінен қалған алғашқы термдерді тегіс жабатын бастапқы импликанттар жиынтығы іріктелініп алынады. Мұндай импликанттардан əріп сандарын аз жиынтық таңдалынып алынады. Оларға мəнді импликанттарды қосып, мөлшері əр-түрлі куб түрінде жазылған бастапқы импликанттардан рангі əр түрлі конъюнктивтік термдерге көшіріледі. Соңғыларды дизъюнкция белгісімен біріктіріп МҚДФ алынады. Мысал. Квайн-Мак-Класки əдісімен f(x1,x2 ,x3 ,x4) логикалық функциясының МҚДФ табу керек: f(x1,x2,x3 x4)= Ú F (4,5,6,8,9,10,11,12,14,15) = c1c2 c 3 c 4 Ú c1c2 c 3 c4 Ú c1c2 c3 c 4 Ú c1 c 2 c 3 c 4 Ú = 1 Ú c1 c 2 c 3 c4 Ú c1 c 2 c3 c 4 Ú c1 c 2 c3 c4 Ú c1 c2 c 3 c 4 Ú c1c2 c3 c 4 Ú c1c2 c3 c4 Шешуі. К0 кешені {0100,0101,0110,1000,1001,1010,1011,1100,1110,1111} топқа бөлінеді: бірнеше ì0101ü ï ï ì0111ü K 0 = ì0100ü 0 = ï1001ï 0 = ï ï 0 1 í ý. K2 í ý K3 í1011ý K4 = {1111}. î1000 þ ï1010ï ï1110ï ïî1100ïþ î þ мұнда кешентердің төменгі индекстері топқа енетін кубтардағы бірліктер санын көрсетеді. 1-кезең. Бастапқы импликанттарды табу (* белгісімен жапсыру амалына қатысатын термдер белгіленеді). ì0101ü ï ï 0 ì0100ü 0 ï1001ï 1 а) K1 = í ý , K2 = í ý салыстырылады, жапсыру нəтижесінде K1 алынады: î1000 þ ï1010ï ïî1100ïþ ì010 X ü ì0101*ü ï100 X ï ï ï ì0111*ü 1 ï ï 0 ï1001*ï 0 ï ï K1 = í10 X 0 ý K2 = í ý K3 = í1011*ý салыстырылады, жапсыру ïX100 ï ï1010 *ï ï1110 *ï ï ï ïî1100 *ïþ î þ ïî1X 00 ïþ амалынан кейін мынадай нəтижеге ие боламыз: ì01X 1ü ï10 X1ï ì0111*ü 1 ï ï 0 ï ï 0 K2 = í101X ý ï1X10 ï K3 = í1011*ý ï1110 *ï K4 = {1111*} салыстырылады, жапсыру ï ï î þ ïî11X 0ïþ амалын орындай отырып мынадай нəтиже аламыз: ì
X 111ü K Барлық 0-кубтар 1-кубтарды алуға қатысады, сондықтан олардың ешқайсысы бастапқы импликант болмайды. ə) Əрі қарай К 1 жəне К 1 салыстырылады да, К 2 нəтижесі алынады: 1 ì010 X ü 2 1 ì01X 1 ü ï100 X *ï ï10 X1*ï ï 2 ï ï 1 1 ï ì10 XX ü K1 = í10 X 0 *ý K2 = í101X *ý K1 = í 0 ý ïX100 ï ï1X10 *ï î1XX þ ï ï ï ï ïî1X 00 *ïþ ïî11X 0 *ïþ K 1 2 мен K 1 салыстырып, K 2 нəтижесі алынады: ì 2 3 01X 1 ü ï10 X1*ï ìX111 ü 1 ï ï 1 ï ï 2 1 ì010X ü 1 K2 = í101X *ý K3 = í1X 11* ý K2 = {1X1X } K1 кубында í ý , K2 кубында ï1X10 *ï ï111X *ï îX 100 þ ï ï î þ ï K î11X 0 *ïþ {01X1} 1 кубында {Х111} термдер бірде –бір * символымен белгіленбеген. С 3 ондықтан олар 3 рангті бастапқы импликанттар болып табылады: К = {010Х , Х 100,01Х 1, Х111} б 1 К 2 ) К 2 мен 2 кешентерін салыстыра отырып оларды құратын 2-кубтар үлкен кубтар құрамайтынын байқауға болады (жапсырылмайды). Сондықтан барлықалынған 2-кубтар бастапқы импликанттар болып табылады: l11 = {10ХХ ,1ХХ 0,1Х1Х } 2-кезең. Импликанттық матрица құру. Импликанттық матрица 7 жолдан жəне 10 бағанадан тұрады. 2.7-кесте белгілері бар матрица келтірілген. – кесте
-кезең. Мəнді импликанттарды табу. Импликанттық матрицада бір белгілі тек бір ғана баған бар. Бұл белгіге 10ХХ мəнді импликантта сəйкес келеді. 2.7- кестеден мəнді 10ХХ импликантпен жабылатын баған –термдер жəне ол импликантқа сəйкес келетін жол сызылып тасталады. Соның нəтижесінде 2.8- кесте алынады. -кезең. Басы артық бастапқы импликанттарды сызып тастау. – кесте
2.8-кестеде мұндай импликанттар жоқ. 5-кезең. Минималь жабу алу. 2.8-кестеден 4-рангті алты термдерді жабатын бастапқы импликанттар жиынтығы таңдалынып алынады: 1Х1Х,01Х1,Х100. Бұл жинақты мəнді импликантпен қоса конъюнктивтік термдерге өтіп МҚДФ алынады: f(x1,x2 ,x3 ,x4)= c1 c 2 Ú c1c3 Ú c 1c2 c 4 Ú c2 c 3 c 4 Ең соңғы бесінші кезеңде бастапқы импликанттардың басқа жиынтығын таңдауға болады: 1ХХ0,Х111,010Х. Мұндай жиынтықта f(x1,x2 ,x3 ,x4)= c1 c 2 Ú c1 c 4 Ú c 2 c3 c4 Ú c 1c 2 c 3 Табылған бірінші жəне екінші жазылуларда сан жағынан бірдей əріптер қолданылып отырғандықтан олардың екеуі де МҚДФ болып табылады. Қаралған əдісті МҚКФ үшін де қолдануға болады. Ол үшін мəні жəне осы мəнге сəйкес термдер қаралады. жүктеу/скачать 2.71 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||