1-Laboratoriya ishi. Mavzu: Electronics Workbench dasturi imkoniyatlari va komponentalari bilan tanishish

х1, х2 қийматлари ва у0… у15 функциялар	Конъюнкция, дизъюнкция, инкор амал-лари орқали ифодала-ниши	Амаллар-нинг асосий белгиси	Функция номи
Мантиқий элемент номи
				х1 0 0 1 1
	х2 0 1 0 1
у0 0 0 0 0	у0 = 0		нол константаси	“нол” генератори
у1 0 0 0 1	у1 = х1 · х2		конъюнкция, мантиқий кўпайтириш	конъюнктор, “ЁКИ”схе-маси
у2 0 0 1 0	у2 =	х1 = х2	х2 бўйича таъқиқ	х2 бўйича “ЭМАС” схемаси
у3 0 0 1 1	у3 = х1		х1 бўйича тавтология	х1 бўйича такрорлагич
у4 0 1 0 0	у4 =	х2 = х1	х1 бўйича таъқиқ	х1 бўйича “ЭМАС” схемаси
у5 0 1 0 1	у5 = х2		х2 бўйича тавтология	х2 бўйича такрорлагич
у6 0 1 1 0	у6 =	х1 х2	истисноли “ЁКИ”, мантиқий тенгмаъно-лик эмас	истисноли “ЁКИ” схемаси
у7 0 1 1 1	у7 = х1 + х2		дизъюнкция, мантиқий қўшиш	дизъюнктор, “ҲАМ” схемаси
у8 1 0 0 0	у8 =		дизъюнкция инкори, Пирс стрелкаси, Вебб функцияси, ЭМАС - ЁКИ амали	Пирс элементи, “ЭМАС-ЁКИ” схемаси (“ЁКИ-ЭМАС”)
у9 1 0 0 1	у9 =	х1 ~ х2	эквивалентлик, тенг-маънолик	солиштириш схемаси
у10 1 0 1 0	у10 =		инвер-сияси	х2 инвертори
у11 1 0 1 1	у11 =		х2 дан х1 га импликация	х2 дан импликатор
у12 1 1 0 0	у12 =		х1 инверсияси	х1 инвертори
у13 1 1 0 1	у13 =		х1 дан х2 га импликация	х1 дан импликатор
у14 1 1 1 0	у14 =	х1 / х2	Шеффер штрихи, ”ҲАМ-ЭМАС” амали	Шеффер элементи, ”ҲАМ-ЭМАС” схемаси
у15 1 1 1 1	у15 = 1		бир константаси	“бир” генератори

12 –Laboratoriya ishi

Мантиқий алгебра функцияларини минималлаштириш (Карно карталари)

Машғулотнинг мақсади: Мантиқий функцияларини минималлаштиришнинг асосий усуллари билан танишиш, МАФни минималлаштиришда шу усуллардан фойдаланишда амалий кўникмаларни ҳосил қилиш.

МАФни минималлаштириш (соддалаштириш) жараёни қуйидаги босқичлардан иборат:

1. 
   МАФни каноник мукаммал дизъюнктив нормал шакли (МДНШ) ёки мукаммал конъюнктив нормал шакли (МКНШ) аниқланади.
   
2. 
   МДНШ (МКНШ) дан қисқартирилган дизъюнктив нормал шаклига (қисқартирилган конъюнктив нормал шаклига) ўтилади.
   
3. 
   Қисқартирилган ДНШ (қисқартирилган КНШ) асосида берк ДНШ (берк КНШ) топилади
   
4. 
   Зарур бўлса аниқланган берк ДНШ у ёки бу базисга ўтказилади, акс ҳолда шу кўринишда қолади.
   

Биринчи босқичда МАФни МДНШни аниқлашда унинг ҳақиқатлик жадвалидан фойдаланиш мақсадга мувофиқ.
Иккинчи босқичда МДНШдан қисқартирилган ДНШга ўтилади.Бунда мантиқий алгебранинг қонун ва қоидаларидан фойдаланиш йўли билан ёндош импликанталар бириктирилади ва қисқартирилади.
Барча ёндош импликанта қисқартирилгандан сўнг, учинчи босқичга ўтилади, яъний ортиқча импликанталар аниқланади. Ортиқча оддий импликанта деганда қисқартирилган ДНШдан чиқариб ташланган ҳолда МАФни қийматини ўзгартиришга олиб келмайдиган импликанта тушунилади.
Натижада қисқартирилган ДНШдан ортиқча импликанталар олиб ташланса берк ДНШ ҳосил бўлади. Агар қўйилган шарт бўйича у ёки бу базисга ўтиш лозим бўлса, де Морган қоидаларидан фойдаланиб ёки Пирс базисига («ЁКИ-ЭМАС»), ёки Шеффер базисига («ҲАМ-ЭМАС») ўтилади. Акс ҳолда берк ДНШ минимал шакл деб ҳисобланади.
Минималлаштириш жараёни турли усулларда бажарилиши мумкин.Кенг тарқалган усуллар:
- аналитик (ҳисоблаш) усули;
- ҳисоб- жадвал (Квайн ) усули;
- жадвал (Вейч-Карно) усули.
Уларни яқинроқ кўриб чиқамиза.

Минималлаштиришни аналитик (ҳисоблаш) усули

МАФни ҳақиқатлик жадвали асосида унинг МДНШни ёзамиз.Сўнг ёндош минтермларга нисбатан бириктириш усулини қўллаб, яъни Ax v Ax = A(x v x) = A, уларнинг даражасини (ўзгарувчилар сонини) биттага камайтирамиз.

Агар бирорта минтерм бошқаларга нисбатан ёндош бўлмаса, у ҳолда ўзгармас кўринишда ёзилади. Сўнг ҳосил бўлган импликанталар бир бири билан таққосланади ва улар орасида ёндошлар бор бўлса, улар ҳам бириктирилади ва импликанталарнинг даражаси яна биттага камаяди. Барча ёндош импликанталар аниқланиб бир бири билан бириктирилгандан сўнг қисқартирилган ДНШ ҳосил бўлади.
Энди ортиқча импликанталар аниқлаш жараёнига ўтамиз. Маълумки, ҳар қандай импликанталар фақат уни ҳосил қилувчи ўзгарувчилар бирлик қийматига тенг бўлгандагина бирлик қийматига эга бўлади. Агар ўзгарувчиларнинг шу қийматида МАФни қолган импликанталар дизъюнкцияси бир қийматига тенг бўлса, унда кўриб чиқилган импликанта функцияни қийматига таъсир қилмайди ва ортиқча деб ҳисобланади.
Қисқартирилган ДНШдан ортиқча импликанталар чиқариб ташланса берк ДНШ ҳосил бўлади. Агар ортиқча импликанталар сони иккита ва ундан ортиқ бўлса, аввал биттаси чиқариб ташланади ва ортиқча импликантани аниқлаш жараёни қайтирилади.
Агар кўриб чиқиладиган бошланғич МАФни шакли мукаммал конъюнктив нормал шакли бўлса, у ҳолда ёндош макстермлар бириктирилиб, яъни (A v x)(A v ^_ x) = A ифодадан фойдаланиб, имплициенталар ранги (даражаси) камайтирилади ва натижада қисқартирилган КНШ аниқланади. Берк КНШ ҳосил қилиш учун ортиқча имплициенталар аниқланади. Бу жараёнда имплициенталарнинг қиймати нолга тенглаштирилади.
Агар қисқартирилган КНШдаги функцияни нол қиймати текширилаётган имплициентасиз ҳам ўзгармаса,у ҳолда ортиқча имплициента чиқариб ташланади.
Мисол тариқасида олдинги машғулотдаги мисолни кўриб чиқамиз:

№	Х1	Х2	Х3	Y
0	0	0	0	1
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Ортиқча импликанталарни аниқлаймиз.

1) - ортиқча эмас;
2) - ортиқча;
3) - ортиқча эмас;
ортиқча бўлган импликантани чиқариб ташлаб функцияни берк шаклини хосил қиламиз.

Агар бошланғич холат бўлиб функцияни МКНШ кўрилса, у ҳолда


Ортиқча импликанталарни аниқлаймиз
1) - ортиқча;
2) - ортиқча эмас;
3) - ортиқча эмас;

Агар берк шаклидан у ёки бу базисга ўтиш зарур бўлса, де Морган теоремасидан фойдаланилади:
Бизнинг мисолда:


Квайн (ҳисоб жадвал) усули
Ҳисоб-жадвал усулида минималлаштиришни 1 босқичи ҳисоблаш усули каби бажарилади, лекин қулай ва кўзга кўринарли бўлган учун импликантлар устунларга жойлаштирилади. Биринчи устунга МФни МДНШ (МКНШ)ни ҳамма минтерми ва макстермлари нумерланиб ёзилади. Сўнг улар таҳлил қилинадилар. Иккинчи устунга қўшни минтермларнинг номерлари ёзилади ва ёнига умумий импликанта ёзилади.Ҳамма минтермларни солиштириб қўшнини аниқлагандан сўнг иккинчи устун таркиби таҳлилланади. Агар бириктиришда қайсидир минтерм қатнашмаса, у иккинчи устуннинг пасига ёзилади.
Сўнг иккинчи устундаги ҳамма импликанталар нумерланиб бириктириш жараёни давом этади. Шундай қилиб биринчи устунга ҳамма минтермлар (n-разрядли импликантлар) ёзилиб қолади, иккинчи устунга – бириктиришда қатнашмаган n-1 рангли импликантлар ва n-2 рангли импликантлар эса учинчи устунда ва ҳ.к. бу жараён импликантларни бириктириш мумкин бўлмаган ҳолгача такрорланади.
Биз кўрган мисолда:


Ортиқча импликанталарни аниқлаш учун Квайн жадвали тузилиб, устун сарлавхасига минтермлар, қатор бошига эса қисқартирилган ДНШ таркибидаги энг кичик ранга эга бўлган импликанталар ёзилади. Сўнг қатор бошидаги ҳар бир импликанта ҳамма минтермлар билан солиштирилади. Агар у минтермларни ҳусусий қисмини,яъний минтерм таркибини ташкил этса, у ҳолда мос келган кесишган катакга «+» қўйилади. Ортиқча импликанталарни аниқлаш масаласи шундан иборатки, баъзи (ортиқча) импликанталарни ўчириб ҳар бир устунда жуда бўлмаган битта «+» қолдиришда дир. Шундай қилиб ортиқча бўлмаган импликанталарга эга бўлган функцияни ядроси топилади.
Бизнинг мисолимизда:

Импли-канталар	Минтермлар
	+	+
		+	+
			+	+

Агар биринчи қаторни ўчирсак, унда биринчи устунда «+» қолмайди. Демак, бу импликанта ортиқча эмас. Иккинчи қатор ўчирилганда эса ҳар бир устунда биттадан «+» қолади. Демак, бу импликанта ортиқча. Ҳудди шундай қилиб учунчи қатор текширилади. У ортиқча эмас, чунки аксинча бўлганда кейинги устунда «+» бўлмайди. Натижада берк ДНШ тенг бўлади:

МКНШ учун эса