Квайн-Мак-Класки ықшамдау әдісі

«АЛМАТЫ ТЕХНОЛОГИЯЛЫҚ УНИВЕРСИТЕТІ»

СРС

Тақырыбы: Квайн-Мак-Класки ықшамдау әдісі.

Орындаған: Бақтияров Ә.

       Тобы: ИС-22-11 ТиПО        

Алматы 2022

Квайн-Мак-Класки әдісі. Жетілген қалыпты формалардан (ЖҚДФ және ЖҚКФ) тікелей минималь қалыпты формаларды (МҚДФ және МҚМФ) жапсыру және сіңіру ережелерін қайта-қайта қолдану арқылы алуға болады. Бұл ережелерді қолданғанда термдерді жүйесіз салыстыру кезінде минималь қалыпты формалар қажетті төменгі рангті термдер толық алынбауы мүмкін. Квайн әдісі 1952 жылы термдерді қос-қостан салыстыру операциясын ретке келтіріп, минималь қалыпты форманы алу алгоритмін анықтайды. Квайн әдісімен минимальдау үшін бастапқы функция ЖҚДФ берілген деп ұйғарылады. Оған кіретін барлық термдер қос-қостан салыстырылып, оларға қайсыбір айнымалы бойынша жапсыру операциясын қолданамыз: [pic 1]. Мұнда F-r=(n-1) рангті терм. Сонымен терм рангін r=n -нен r=n-1 -ге дейін төмендетіледі. Бұл операция қажетінше қайталанады. Жапсыру операциясына қатыспайтын термдерді бастапқы импликанттар деп атайды. Дизъюнкция белгісімен байланысқа бастапқы импликанттар жиыны МҚДФ түрінде бола бермейді. Сондықтан алынған импликанттар жиыны кейбір бастапқы импликанттарды алып тастау жолымен ықшамдалады. Алып тасталған имплианттар функцияның тепе-теңдігін бұзбауы керек. Квайн әдісінің елеулі кемістігі жапсыру амалын қолдану үшін барлық термдерді қос-қостан салыстыру керектігінде.

1956 жылы Мак-Класки конъюнктивтік термдерді ( [pic 2] ) екілік айнымалылар жиынтығы түрінде жазуды ұсынды. Мұнда термге t-куб сәйекстендіріледі. Бұл термдердің епетейсіз жазылуынан айырып, жапсыру операциясын қолдану үстінде термдерді қос-қосап салыстыру санын қысқартуға мүмкіндік береді. Өйкені барлық [pic 3] айнымалылар жиынтықтарын олардағы бірліктер санымен қиылыспайтын топтарға бөлуге болады, і-топқа і-бірліктері бар барлық жиынтықтар кіреді. Бұл жағдайда тек көршілес топтағы жиынтықтар бір-бірімен салыстырылады. (i-1) топ пен і топ; і топпен і+1 топ және т.с.с. көршілес емес топтарға кіретін жиынтықтар бір-бірімен кем дегенде екі бірліктермен өзгеше болады.

Сондықтан олардың жапсырылу ықтималдығы 0-ге тең. Төменде Квайнның Мак-Класки жетілдірген (Квайн-Мак-Класки әдісі) кезеңдерге бөлінген формальді алгоритмі баяндалады.

Логикалық функцияның қысқартылған ДНФ құрудың бірінші әдісі келесі теоремаға негізделген.

Теорема (Квин). Логикалық функцияның қысқартылған ДНФ-ін оның мінсіз ДНФ-тен алу үшін көршілес конъюнкциялардың барлық толық емес байланыстарын, содан кейін конъюнкцияларды сіңірудің барлық түрлерін орындау қажет.

Квин теоремасына сүйене отырып, Макклуски қысқартылған ДНФ құрылысын Теоремада ұсынылғаннан тиімдірек ұйымдастыратын алгоритмді тұжырымдады.

Біріншіден, алгоритмдегі конъюнктуралар логикалық және үштік векторлармен ұсынылған, бұл есептеулерді қарапайым және компьютерлік іске асыруға ыңғайлы етеді.

Екіншіден, көршілес векторлар салмағы бойынша ерекшеленеді (бірлік компоненттерінің саны) дәл бірлікке. Сондықтан, алгоритмде салмағы біреуден көп болатын немесе ерекшеленетін векторларды желімдеу мүмкіндігі тексерілмейді.

Үшіншіден, көршілес векторлар оларды желімдеу нәтижесінде жұтылады. Сондықтан желімделген көршілерді белгілеу (бірақ оларды сызып тастау емес, өйткені бір вектор бірнеше векторларға көрші болуы мүмкін) сіңіруді белгіленбеген векторларды жазуға дейін азайтуға мүмкіндік береді.

Квин –Макклуски Алгоритмі:

• Басталуы. Логикалық функцияның тамаша ДНФ берілген.
•   1-қадам. Біз функцияның барлық нүктелерінің тізімін жасаймыз (логикалық векторлар) және оларды бірлік – салмақ санының азаюына тапсырыс береміз.
•   2-қадам. Біз тізімді бірдей салмақтағы векторлардың ішкі жиындарына (кластарына) бөлеміз. Ci арқылы салмақ векторларының I класын белгілеңіз.
•   3-қадам. Біз Ci және ci+1, i = 0,1, ..., n-1 кластарының барлық көршілес векторларын толық емес желімдейміз. Біз желімдеуге қатысатын векторларды (α және β) белгілейміз, ал алынған векторларды (γ) жаңа тізімге енгізіп, оған ұқсас етіп береміз.
•   4-қадам. Егер векторлардың Жаңа тізімі бос болмаса, онымен бірге 2-қадамға оралайық (тізімнің үштік векторлары бірліктер саны бойынша реттелгенін ескеріңіз).
•   Соңы. Барлық тізімдерден белгіленбеген векторларды жазып, біз барлық максималды Интервалдардың жиынтығын аламыз, ол бастапқы функцияның қысқартылған ДНФ-ін көрсетеді.

Мысал 1: Алгоритмнің орындалуын көрсетейік, оның қадамдарын сұр матрицалармен сүйемелдеу.

Басталуы. Логикалық функцияның тамаша ДНФ берілген:

[pic 4]

1, 2 қадамдар. Біз мінсіз ДНФ-ті нүктелер тізімімен ұсынамыз, оларды салмағы бойынша реттейміз және сыныптарға бөлеміз.

[pic 5]

3-қадам. C2 және C3, содан кейін C3 және C4 кластарынан векторларды толық емес желімдеу арқылы және реттелген тізімде 0 * белгісімен желімделген векторларды белгілеу арқылы біз 1 – тізімді аламыз-екі нүктеден тұратын интервалдар тізімі. Жаңа тізімнің оң жағында желімдеуге қатысушы векторлардың нөмірлері көрсетілген. Тізім аралықтары Грейдің екі матрицасында көрсетілген.