Бул функцияларни минималлаштириш. Тўла аниқланмаган Бул функцияларни минималлаштириш. Кўп чиқишли схемаларни синтез қилиш

Карно (Вейч) карталари. Карно картаси бу катакларга бўлинган тўғри тўртбурчак бўлиб, катакларнинг сони берилган мантиқий функция мустақил ўзгарувчиларининг бўлиши мумкин барча тўпламларининг сонига тенг. Икки ўзгарувчили функция учун карта 4 катакдан, 3 ўзгарувчили функция учун 8 катакдан иборат бўлади ва ҳ.к.

Икки ўзгарувчи учун мўлжалланган картани қараймиз (21-расм). Картанинг ҳар бир катаги бирлик конституентига мос келади.

21-расм. Икки ўзгарувчили функция учун Карно картаси

22-расм. Уч ўзгарувчили функция учун Карно картаси

Ўзгарувчи қўшилиши билан карта икки баравар ошиб боради. Уч ўзгарувчили функция учун Карно картаси 22-расмда кўрсатилган.

Карталарни ҳосил қилишда қуйидаги қоидадан фойдаланиш мумкин: n ўзгарувчили функция учун Карно картаси n-1 ўзгарувчили функция карталаридан олинади, бунда охирига худди шунақа, симметрик жойлашган, узунлиги бир хил карта карта қўйиш йўли билан икки баравар оширилади. Бунда янги картанинг ярми тасдиқ шаклли янги ҳарф билан белгиланади, қолган ярми эса худди шу ҳарф орқали, аммо инкор шакли билан белгиланади. 23-расмда тўрт ўзгарувчили функция учун Карно картаси келтирилган бўлиб, бу карта 22-расмдаги карталардан олинган. Тўғри ёйилган картада исталган иккита қўшни катаклар бирикувчи бирлик конституентлари орқали мос келади. Бундан ташқари, карта чегаралари бўйлаб чап ва ўнгдан ёки тепа ва пастга қараб симметрик жойлашган исталган икки катак ҳам бирикувчи бирлик конституентлари орқали мос келади.



23-расм. Тўрт ўзгарувчили функция учун Карно картаси.
Берилган мантиқий функцияни Карно картаси ёрдамида минималлаштириш қуйидаги тартибда амалга оширилади.

1. Берилган функция ҲДНШга ўтказилади.

2. Берилган функциянинг ҳар бир бирлик конституенти Карно картасининг мос катагида бир билан белгиланади.

3. Қўшни ёки карта чегараларига нисбатан симметрик жойлашган бирлар тўғри тўртбурчак билан ўралади. Бунда қуйидаги талабларга риоя қилиш зарур:

- бир тўртбурчак билан ўралган бирлар сони 2^k га тенг бўлиши зарур, бу ерда k бутун сон;

- ҳар бир тўртбурчак имкони борича кўпроқ бирларни ўраши, ўровчи тўртбурчаклар сони эса имкони борича камроқ бўлиши лозим;

- айнан битта бирнинг ўзи бир неча марта турли тўртбурчаклар билан ўралиши мумкин.

4. Бирларни ўровчи ҳар бир тўртбурчак учун конъюнкцияни ёзамиз. Бу конъюнкция ичига шу тўртбурчак томонидан ўралган бирлар учун умумий бўлган ҳарфлар кириши лозим.

5. Барча ўровчи тўртбурчакларга мос келувчи конъюнкцияларни ўз ичига олувчи минимал ДНШни ёзиб оламиз.

6. Агар имкони бўлса, умумий аъзоларни қавслардан чиқариш йўли билан олинган формулани қисқартирамиз.

Мисол: Тўрт ўзгарувчининг функциясини қараймиз. Берилган функциянинг ҲДНШ қуйидагича бўлсин:



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



24-расм. Беш ўзгарувчили функция учун Карно картаси.

Беш ўзгарувчили функция учун Карно картаси 24-расмда кўрсатилган. Олти ўзгарувчили функция учун эса 25-расмда. Беш ва олти ўзгарувчили функциялар учун Карно карталари қуйидаги хусусиятларга эга. Карта ичида марказий симметрия ўқига нисбатан симметрик жойлашган бирлар бириктирилган конъюнкциялар билан мос келади.

Мисол: Беш ўзгарувчининг функцияси 24-расмдаги Карно картасида белгиланган бирлар билан берилган бўлсин. Ўраш натижасида қуйидаги минимал ДНШни ҳосил қиламиз:

Олти ўзгарувчининг функциясини минималлаштиришни 25-расмдаги картада бирлар билан белгиланган функция мисолида кўриб чиқамиз. Ўраш натижасида қуйидагини оламиз:

Карно картасидаги бирларни ўраш натижасида олинган импликантларни ёзиб олаётганда, текшириш учун қуйидаги боғлиқликдан фойдаланиш мумкин: l=n-k, m=2^k, бу ерда l – ўраш натижасида олинган импликантдаги ҳарфлар сони, m – шу тўртбурчак билан ўралган бирлар сони, k - бириктириш натижасида ютилган ҳарфлар сони, n – функциядаги мустақил ўзгарувчиларнинг сони.

25-расм. Олти ўзгарувчили функция учун Карно картаси.