загрузка...
Бульдік функцияларды аналитикалық көрсету, Бульдік функцияларды ықшамдау. ЛАФ аналитикалық жолмен көрсету. Кез келген логикалық алгебра функциясын базис құратын кейбір элементар функциялардың супер - позициясы арқылы көрсетуге болады. Бұл жерде ЛАФ минималь логикалық өрнек түрінде болуы мүмкін. ЛАФ аналитикалық жолмен өрнектеуге мүмкіндік беретін ең көп таралған дизьюнкция, коньюнкция, логикалық терістеу сияқты элементар функциялардан тұратын базис болып табылады. Квайн -Мак -Класки әдісі. Жетілген қалыпты формалардан (ЖҚДФ және ЖҚКФ) тікелей минималь қалыпты формаларды (МҚДФ және МҚМФ) жапсыру және сіңіру ережелерін қайта -қайта қолдану арқылы алуға болады
АЛФ-ны Квайна-Мак-Класки әдісімен минимизациялау.
Жалпы жағдайда құрылғы n кірістен және m шығыстан тұруы мүмкін. m=1 жағдайында біршығысты схема орын алады, қарсы жағдайда көп шығысты схема қалыптасады.
Құрылғы кірісіне {Х}кіріс алфавитінен тұратын кіріс сөздері келіп түседі, ал шығыста {У}шығыс алфавитінен тұратын шығыс сөздері болады. n кіріс және m шығыс кезінде, кіріс сөзі n шамасын құраса, шығыс сөзі m шамасын құрайды.
Егер құрылғы жұмысы ti моментте толығымен ti уақыт мезетінде келіп түскен кіріс сөзбен анықталатын болса, онда мұндай құрылғыны комбинациялық схема немесе жады құрылғысы жоқ ақырғы автомат деп атайды. Жадысы жоқ ақырғы автомат қарапайым логикалық құрылғы болып табылады, және олардың жұмысы бульдік өрнектермен баяндалады.
Комбинациялық схемаларды жобалау кезінде оларды синтездеу және анализдеу есептерін қарастыруға тура келеді. Комбинациялық схемаларды синтездеу этаптары:
- физикалық баяндамасы бойынша математикалық баяндамасы жасалынады (бульдік теңдеулер жүйесі);
- математикалық баяндалуы бойынша алдын ала минимизация есептерін шеше отырып, логикалық схеманы құрайды;
- логикалық схема бойынша функционалдық схема құрайды.
Комбинациялық схемаларды анализдеу барысында синтездеу процесіне қарама қарсы есептер орындалады, яғни қолда бар комбинациялық схема бойынша оның математикалық моделін жасау керек. Сонымен комбинациялық схемаларды синтездеу мәселесін шеше отырып, бульдік функцияларды шешу мәселесі де шешіледі. Бульдік функцияларды іске асырудың негізі болып логикалық элементтер саналады. Екі тұрақты күйі бар элементтер логикалық элементтер ( немесе ауыспалы элементтер) деп аталады, «0» - ауыспалы элементтің (триггердің, реленің, магниттік жүрекшенің) бір күйі, «1» - екінші күйі.
Бульдік айнымалылар және функциялар логикалық элементтердің кіріс және шығыс сигналдарының мәнін бейнелейді.
Бульдік өрнектерге сәйкес біріккен олар логикалық ауыспалы схемаларды құрайды. Минимальді бульдік өрнектер кезінде минимальді комбинациялық схемалар алынады. Минимальді комбинациялық схема жоғары сенімділікпен, минимальді бағамен, жоғары жылдамдықпен сипатталады. Сондықтан комбинациялық схемаларды синтездеу мәселесін шешу барысында алгебра логика функцияларын минимизациялау мәселесін назар аудару керек. АЛФ минимизациялаудың бірнеше әдістері бар: Квайна Мак-Класки, Вейча – Карно және т.б. бірақ бұл аталған әдістер негізінде элементарлы және көршілес конъюнкцияларды жабыстыру және жұту әдістерін қолданып, бастапқы ДЖҚФ функциясы бойынша оның минимальді ДМҚФ алу болып табылады.
х11х22... хnn конъюнкциясы элементарлы болып саналады, егер ондағы әрбір айнымалы бір реттен артық кездеспейді, мұнда
i, егер i=0
xii =
xi, егер i=1
Конъюнкцияны қалыптастыратын әріптер саны (r) ранг деп аталады. Бірдей рангілі екі элементарлы конъюнкция көршілес деп аталады, егер олар бір аргументтің функциялары болып саналса және аргументтердің біреуі тек терістеу (инверсия) таңбасымен ғана өзгешеленсе.
r рангілі көршілес конъюнкциялардың дизъюнкциясын бастапқы конъюнкцияның ортақ бөлігі болып табылатын элементарлы r-1 рангті конъюнкциямен алмастыруға болады (жабыстыру ережесі). Мысалы, У=х1х2 х1х2x3=х1x2.
Бульдік функцияларды ықшамдау. Квайн-Мак-Класки әдісі. Жетілген қалыпты формалардан (ЖҚДФ және ЖҚКФ) тікелей минималь қалыпты формаларды (МҚДФ және МҚМФ) жапсыру және сіңіру ережелерін қайта-қайта қолдану арқылы алуға болады. Бұл ережелерді қолданғанда термдерді жүйесіз салыстыру кезінде минималь қалыпты формалар қажетті төменгі рангті термдер толық алынбауы мүмкін. Квайн әдісі 1952 жылы термдерді қос-қостан салыстыру операциясын ретке келтіріп, минималь қалыпты форманы алу алгоритмін анықтайды. Квайн әдісімен минимальдау үшін бастапқы функция ЖҚДФ берілген деп ұйғарылады. Оған кіретін барлық термдер қос-қостан салыстырылып, оларға қайсыбір айнымалы бойынша жапсыру операциясын қолданамыз:. Мұнда F-r=(n-1) рангті терм. Сонымен терм рангін r=n -нен r=n-1 -ге дейін төмендетіледі. Бұл операция қажетінше қайталанады. Жапсыру операциясына қатыспайтын термдерді бастапқы импликанттар деп атайды. Дизъюнкция белгісімен байланысқа бастапқы импликанттар жиыны МҚДФ түрінде бола бермейді. Сондықтан алынған импликанттар жиыны кейбір бастапқы импликанттарды алып тастау жолымен ықшамдалады. Алып тасталған имплианттар функцияның тепе-теңдігін бұзбауы керек. Квайн әдісінің елеулі кемістігі жапсыру амалын қолдану үшін барлық термдерді қос-қостан салыстыру керектігінде. 1956 жылы Мак-Класки конъюнктивтік термдерді () екілік айнымалылар жиынтығы түрінде жазуды ұсынды. Мұнда термге t-куб сәйекстендіріледі. Бұл термдердің епетейсіз жазылуынан айырып, жапсыру операциясын қолдану үстінде термдерді қос-қосап салыстыру санын қысқартуға мүмкіндік береді. Өйкені барлық айнымалылар жиынтықтарын олардағы бірліктер санымен қиылыспайтын топтарға бөлуге болады, і-топқа і-бірліктері бар барлық жиынтықтар кіреді. Бұл жағдайда тек көршілес топтағы жиынтықтар бір-бірімен салыстырылады. (i-1) топ пен і топ; і топпен і+1 топ және т.с.с. көршілес емес топтарға кіретін жиынтықтар бір-бірімен кем дегенде екі бірліктермен өзгеше болады. Сондықтан олардың жапсырылу ықтималдығы 0-ге тең. Төменде Квайнның Мак-Класки жетілдірген (Квайн-Мак-Класки әдісі) кезеңдерге бөлінген формальді алгоритмі баяндалады. 1-кезең. Бастапқы импликантты табу. ЖҚДФ-ға кіретін барлық {m} термдерді екілік айнымалылар жиынтығы түрінде (0-кубтар К0 кешені) топтап олардағы бірліктер санына қарай жазып алады. Көршілес екі жиынтыққа жапсыру амалы қолданылады. Нәтижелерді топтап 1-кубтар К1 кешені түрінде жазылады. Көршілес топтарға (К1) кіретін 1-кубтар бір-бірімен салыстырып 2-кубтар түзіледі. Бұл салыстыру және жапсыру амалдары t кубтардың Kt кешентерін алғанша орындалады. Олар бір-бірімен жапсырылуы тиісті емес. Жапсыру амалдарына қатыспаған кубтар бастапқы импликанттар {} жиынтығын құрады. 2-кезең. Импликанттық матрица құру. Матрицаның жолдарын бастапқы импликанттармен, ал бағандарын алғашқы (негізгі) импликанттармен (0-кубтармен) белгілейді. Егер бастапқы импликантта терміне енсе онда і жолымен j баған қиылысқан жеріне белгі қойылады. 3-кезең. Мәнді импликанттарды табу. Егер импликанттық матрицаның қайсыбір бағынында тек бір ғана белгі болса, онда осы белгіге сәйкес келетін алғашқы импликантта мәнді болып табылады, өйткені онсыз берілген термдердің барлық жиынтығын {m} алуға болмайды. Мәнді импликанттар міндетті түрде МҚДФ құрамына кіруі керек. Мәнді импликанттармен жабылатын термдерге сәйкес келетін бағандар және мәнді импликантты жолдар матрицадан сызылып тасталады. 4-кезең. Басы артық бастапқы импликанттарды сызып тастау. Алдыңғы кезеңдер орындалған соң, импликанттық матрицада бірде-бір белгісі жоқ жолдар пайда болуы мүмкін. Мұндай жолдарға сәйкес келетін бастапқы импликанттар әрі қарай қаралмайды, өйткені олар матрицадағы қалған алғашқы термдерді жаба алмайды. 5-кезең. Минималь жабын алу. Импликанттық матрицаның жолдары мен бағандарын сызып тастағанмен алынған матрица зерттеледі. Қалған жолдар ішінен қалған алғашқы термдерді тегіс жабатын бастапқы импликанттар жиынтығы іріктелініп алынады. Мұндай импликанттардан әріп сандарын аз жиынтық таңдалынып алынады. Оларға мәнді импликанттарды қосып, мөлшері әр-түрлі куб түрінде жазылған бастапқы импликанттардан рангі әр түрлі конъюнктивтік термдерге көшіріледі. Соңғыларды дизъюнкция белгісімен біріктіріп МҚДФ алынады.
Ұнады ма? Онда достарыңмен бөліс!
|