“Информатика” факультети

Лаборатория иши №3

Мавзу: Нормал дизъюнктив ва конъюнктив шакллар. +ис=артирилган нормал дизъюнктив ва конъюнктив шакллар. Етук нормал дизъюнктив шакл ва етук нормал конъюнктив шакллар.

Режа:

1. 
   Нормал дизъюнктив ва конъюнктив шакллар ща=ида умумий тушунчалар.
   
2. 
   +ис=артирилган нормал дизъюнктив ва конъюнктив щамда =ис=артирилган нормал дизъюнктив ва конъюнктив шакллар ща=ида умумий тушунчалар.
   
3. 
   Етук нормал дизъюнктив шакл. ва етук нормал конъюнктив шакллар. ща=ида умумий тушунчалар.
   
4. 
   Турли манти=ий функцияларни схемаларини ташкил этиш.
   
5. 
   Вариант быйича 3.1 ва 3.2 жадвалда берилган ифодаларни нормал дизъюнктив шаклга келтиринг.
   

3.1. Нормал дизъюнктив ва нормал конъюнктив шакллар ща=ида умумий тушунчалар.
Манти=ий =урилмалар синтези бир неча бос=ичларга былинади. Биринчи бос=ичда функцияни сызлик, жадваллик ёки бош=а турдаги шаклларини базис ёрдамида манти=ий ифода кыринишида намоён =илиш лозим. Кейинги бос=ичлар минимал турдаги функциялар щосил =илишга келтирилган былиб, улар =урилманинг синтезидаги энг минимал ми=дордаги электрон жищозининг ва функционал схеманинг рационал тузилишини таъминлайди. Биринчи бос=ич учун, манти=ий =урилманинг тузилишида ишлатиладиган базисга бо\ли=сиз равишда, ВА, ЁКИ ва ЭМАС базиси =ылланилади. Кейинги соддалаштиришлар =улайлиги учун функцияларнинг иккита каноник шакллари мавжуд: =ис=артирилган дизьюнктив нормал шакл (+ДНШ) ва =ис=артирилган коньюнктив нормал шакл (+КНШ).
Дизьюнктив нормал шакли деб, функциянинг шундай кыринишидаги шаклига айтиладики, унда функциянинг манти=ий ифодаси дизьюнкциянинг =атор щадлари кыринишида ва щар бири оддий коньюнкция аргументи ёки инверсияда былади. Масалан, дизьюнктив нормал шаклга кыриниш.

дизьюнктив нормал шаклига была олмайдиган функциянинг кыриниши.

бу ифодани ДНШ да была олмаслигини сабаби, ундаги охирги щад оддий коньюнкция аргументи эмас. Шунингдек, =уйидаги келтирилган функция щам ДНШ га эга эмас:

Агар ДНШ нинг щар бир щадида функциянинг щамма аргументлари (ёки инверсиялари) кырсатилган былса, бундай форма +ДНШ дейилади. (1.9) ифода +ДНШ да была олмайди, чунки унинг учинчи щадидагина функциянинг щамма аргументлари мавжуд. ДНШ дан +ДНШ га ытиш учун щамма аргументлари келтирилмаган щар бир щадга кыринишидаги ифодани киритиш керак. Бу ерда -щадида =атнашмайдиган аргумент былгани учун бундай операция функциянинг =ийматини ызгартира олмайди. ДНШ дан +ДНШ га ытиш йылини мана бу ифодада кырсатамиз:

Щадларга кыринишидаги ифодани =ышилиши функциянинг мана бу щолга олиб келади:

(3.1) асосида

Ыхшаш щадларнинг келтирилишидан кейин

+ДНШ га ытамиз.

3.10-жадвал

х1	0	0	0	0	1	1	1	1
х2	0	0	1	1	0	0	1	1
х3	0	1	0	1	0	1	0	1
f(х1,х2,х3)	0	0	1	1	0	1	0	1

Функциянинг 3.10-жадвал шаклида берилган былса, бу функциянинг +ДНШ и =уйидаги кыринишда былади:

(3.10) даги щар бир аргументнинг =ийматлари тыпламига мос келиб, бунда f(х₁,х₂,х₃) тенг 1. f(х₁,х₂,х₃) тенг 1(3-,4-,6-,8- устунлар тыплами) даги щар бир тыпламлар, аргументлар (1.10) ифодадаги мос келувчи щадни 1 га айлантиради, бунинг натижасида бутун функциянинг =иймати щам бирга тенг былади.
Функциянинг +ДНШ кыринишида ёзиш учун =уйидаги =оидани =ыллаш лозим: функцияниг жадвалдаги нечта бирга эга эканлигига =араб, шунча щамма аргументлари коньюнкцияси кыринишидаги щадларни ёзиш керак. Щар бир коньюнкция ани= аргументлар тыпламига мос келиб функцияни бирга айлантиради, агар бу аргументда тыплам =иймати 0 га тенг былса, унда коньюнкцияга берилган аргументнинг инверцияси киради. Функция фа=ат битта +ДНШ га эга была олади.
+КНШ деб, функциянинг шундай кыринишидаги шаклига айтиладики, унда функциянинг манти=ий ифодаси коньюнкциянинг =атор щадлари кыринишида ва щар бир оддий дизьюнкция аргументи ёки уларнинг инверсияси. Масалан КНШ га =уйидаги функция мисол была олади:

Кейинги келтирадиган мисолларимизда функциялар КНШ га мисол была олмайди:

(бу ерда 3-щад оддий дизьюнкция аргументи ёки уларнинг инверсиясига мисол была олмайди);

(бу форма щам КНШ была олмайди, чунки биринчи щади =олган щадлар билан коньюнкция операцияси билан бо\ланмаган).
+КНШ да КНШ нинг щар бир щадида щар бир аргументлар намоён былиши шарт. КНШ дан +КНШ га ытиш учун щар бир аргументларни ыз ичига олмаган щадга кыринишидаги щадни =ышиш керак, бу ерда x_i-щаднинг ичида йы= былган аргумент. былгани учун бундай операция функциянинг, =ийматига ызгартириш киритмайди. ни бирор бир щадга Y =ышишимиз, мана бундай ифодани келтиради. , бу ифодани мана бу щолга келтиришимиз мумкин:

Бу тенгликнинг ты\рилиги та=симлаш =онунидан келиб чи=ади. Буни яна ифодани ынг тарафидаги =авсларни очилиши билан щам кыришимиз мумкин.

былгани учун,

Функциянинг мисолида

КНШ дан +КНШ га ытишни кыриб чи=амиз.

Та==ослаш =онунини =ылланилганини бу ерда ифодани битта щадида кыриб чи=амиз, бу ифода:

деб тенглаб оламиз. Та==ослаш =онуни асосида:



Кейинчалик га тенглаб оламиз ва та==ослаш =онунини =ыллаймиз.

z₁ ва z₂ ларни =ийматларни =ыйиб, олдин келтирилган ифодани КНШ дан +КНШ га ытишида олинган щадларни оламиз. Функциянинг +КНШ иси ща=и=ат жадвалидан тезро= топилади. Мисол тари=асида (3.10) функцияни кыриб чи=амиз:

Бу ифодада шунча щадки, коньюнктив операцияси билан бо\ланган, f(х₁,х₂,х₃) функциянинг ща=и=ат жадвалида =ийматлар орасида нечта 0 былса, шунча былади. Шундай =илиб, щар бир аргументнинг =иймати 0 былганда +КНШ ини бир щадига ты\ри келади. Мана шу бос=ичда 0 =ийматини олувчи +КНШ нинг щадлари коньюнктив операцияси билан бо\ланганлигига сабаб функциянинг битта щади 0 га тенг былса, функциянинг =иймати щам 0 тенг былади.

Шундай =илиб функциянинг +КНШ и ща=и=ат жадвалидан келтириб чи=иш =оидасини асослашимиз мумкин. Шунча коньюнктив щадларни ёзиш керакки, нечта аргументнинг =иймати 0 былса ва агар аргументнинг =ийматига тенг былса, дизьюнкцияга шу аргументнинг инверсияси киради. Щар =андай функция битта +КНШ га эга.