Квайн усули днш ва кнш ни минимал ҳадлар сони билан ва ҳадларда минимал ҳарфлар сони билан кўрсатиш имконини беради

Квайн усули ДНШ ва КНШ ни минимал ҳадлар сони билан ва ҳадларда минимал ҳарфлар сони билан кўрсатиш имконини беради. Бу усул икки босқичдан иборатдир: биринчи босқичда каноник шаклда (ҚДНШ ёки ҚКНШ) қисқартирилган формага ўтамиз, иккинчи босқичда-мантиқий ифодани қисқартирилган шаклдан минимал шаклига ўтамиз.

Биринчи босқич (қисқартирилган шаклни олиш). Бизга келтирилган f функцияни ҚДНШ кўринишида бўлсин. қисқартирилган формага ўтиш босқичма-босқич иккита операциясини қўлланишидан келиб чиқади: бирлаштириш ва ютилиш қонуни. Бирлаштириш операцияси бажарилиши учун функциянинг ифодасида мана бу кўринишдаги ҳадни топамиз. ва бу ҳадлар биттасининг аргументи инверсия билан кейингиси инверсиясизлиги билан ажралиб туради. Кейин бирлаштириш операцияси бажарилади:

бирлаштириш натижаси w қўшимча ҳадлар сифатида функциянинг ифодасига қўшилади ва ютилиш қонуни бажарилади. У мана бу тенгликка асосланади. ( ҳади ҳадни ютади). Бу операцияни бажариш жараёнида мантиқий ифодада ҳамма ҳадлар ўчирилади. Бирлаштириш операцияси натижасида келтирилган ҳадларни ютилтирилди.

Бирлаштириш ва ютилиш операциялари имкон қадар бажарилади. Бу операцияни функцияга кўринишини 1.11 жадвалда берилган функцияда кўриб чиқамиз.
1.11-жадвал

х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	0	1	1	1	1

Функциянинг ҚДНШ ни ёзамиз:

Ҳар бир ҳадларни текширганимизда бирлашадиган ҳадлар жуфтлигини топамиз.

1- ва 4- ҳадлар ( -бирлашиш натижаси)

2- ва 3- ҳадлар ( -бирлашиш натижаси)
2- ва 4- ҳадлар ( -бирлашиш натижаси)
3- ва 5- ҳадлар ( -бирлашиш натижаси)
4- ва 5- ҳадлар ( -бирлашиш натижаси)

бирлашув операциясининг натижаларини функциянинг ифодасига киритамиз ва ютилиш операциясини қўллаймиз:

   
 


ҳади шундай ҳадни ютадики, х₁ ва х₄ аргументлари бор бўлган. Бу ҳадларни чизиб ташлаймиз. ҳади иккинчи ва учинчини ютади, ҳади-бешинчи ҳадни. Бирлаштириш ва ютилиш операцияларини такрор бажарамиз.


    
бу ерда ва ҳадлар жуфтлиги бирлашади холос.
( ва ҳадлар жуфтлиги бирлашуви шу натижага олиб келади), х₁ бирлашув натижаси 2-, 3-, 4- ва 5- ҳадларни ютади, сўнгра бирлаштириш ва ютилиш қонунларини қўллаб бўлмайди (бу мисолда функциянинг қисқартирилган шакли минимал шаклига мос келади).



Қисқартирилган шаклни ҳадлари (бу мисолда ва х₁) функциянинг оддий импликанталари дейилади. Кўрганимиздек, олинган ифода соддароқ ҚДНШ га қараганда.
1.23 расмда мантиқий қурилманинг тузилиш схемаси келтирилган, ВА, ЁКИ, ЭМАС базасида қўлланилган:

Иккинчи босқич (минимал шаклга келтириш). Қисқартирилган шаклда қўшимча ҳадлар бўлиши мумкин. Уларни чиқариб ташлаймиз, функциянинг қийматига хеч қандай таъсир этмайди.
Мантиқий ифодани қисқартирилиши мана шу ифодадаги қўшимча ҳадларни чиқариб ташлаш билан топилади-минималлаштиришнинг иккинчи босқичи. Бу босқични қуйидаги мисолда кўриб чиқамиз. Функциянинг 1.12 жадвалда берилган
1.12-жадвал

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

Бу функциянинг ҚДНШ

Қискартирилган шаклга келтириш учун бмрлаштириш ва ютиш операцияларини кўллаймиз:
  
    

Ифода (1.15) берилган функциянинг қисқартирилган шакли. Унинг ҳадлари оддий импликанталар. Қисқартирилган шаклдан минимал шаклига ўтиш учун импликант матрицасидан, 1.13 жадвалидан келтирилгани билан фойдаланамиз.

Импликанта матрицасининг устунига ҚДНШ нинг берилган функциянинг ҳадлари ёзилади, сатрларига-функциянинг оддий импликанталари, функциянинг мантиқий ифодасини қисқартирилган шаклининг ҳадлари. ҚДНШ нинг ҳадлар устунини масалан оддий импликанталар билан ютилганларни, Х белгиси билан ўчирамиз. 1.13 жадвалида оддий импликантаси ҳадларини ютади (биринчи қаторнинг биринси ва иккинчи устунларида Х белгиси билан белгиланган).
1.13-жадвал

Оддий импликанта
	Х	Х
	Х		Х
			Х	Х
				Х	Х
					Х	Х

Иккинчи импликанта ҚДНШ ининг биринчи ва учинчи ҳадларини ютади (иккинчи қаторнинг биринчи ва учинчи устунлари белгиланган), ортиқча бўлмаган импликанталарни қисқартирилган шаклдан чиқариб ташлашимиз мумкин, бу ядрони ташкил қилади. Ядрога кирадиган импликанталарни импликанта матрицасидан осон топишимиз мумкин.
Кўриб чиқаётган мисолимизда ва импликанталар ядрони ташкил этади. Ядрога кирмайдиган барча импликанталарни бирдагина чиқариб ташлашимиз мумкин эмас. Минимал шаклни олиш учун ядро ҳадлари билан кесишмаган ҳарфлар сони минимал бўлган импликанталарни танлаб оламиз. Бизнинг миослимизда матрицанинг учинчи ва тўртинчи устунларида импликанталар билан кесиштиришимиз керак. Бунинг учун бир нечта усуллар бор, лекин минимал импликанталар сони бўлиши шарт, шунинг учун импликантасини танлаймиз.
Берилган функциянинг ҚДНШи:



бу ифоданинг тузилма схемаси 1.24-расмда кўрсатилган.

Қисқартирилган шаклдан МДНШ га ўтиш ва импликанталарни чиқариб ташлаш йўли билан амалга ошди. ва импликанталар кейинги аргументларнинг қийматида мантиқий 1 га тенг бўлади:

Бу импликанталарнинг (1.15) ифода f(х₁,х₂,х₃,х₄) функцияга 1 қийматини беради, лекин мана шу тўпламда функция 1 га тенглиги 1.15 ифоданинг бошқа импликанталар ёрдамида кўрсатилган. Ҳақиқатдан 1.17 ни 1.16 га қўйсак:

бўлганда





бўлганда

Шундай қилиб, ва ҳадларни 1.15 ифодадан чиқариб ташлашимиз тасдиқланди. Ҳозиргача биз МДНШ ни олиш жараёнини кўриб чиқдик, энди МКНШ ни кўриб чиқамиз.

МКНШ учун ҚКНШ асос бўлади. Бирлашадиган ҳадлар жуфтлиги ва кўринишида бўлади. Ютилиш операцияси

ифода асосида қўлланилади.

Квайн усулини қўлланилишини мисолда кўриб чиқамиз, функция 1.14-жадвалда келтирилган
1.14-жадвал

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

Кўриб чиқилган функциянинг ҚКНШ

Бирлашадиган ҳадлар жуфтлиги:

1- ва 3- ҳадлар ( -бирлашув натижаси)
1- ва 4- ҳадлар ( -бирлашув натижаси)
2- ва 3- ҳадлар ( -бирлашув натижаси)