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

Квайн теоремаси. Агар Бул функциянинг ҲДНШда тўлиқ бўлмаган бириктиришнинг барча амаллари, сўнгра ютилишнинг барча амаллари бажарилса, ушбу функциянинг қисқартирилган ДНШ, яъни барча оддий импликантларининг дизъюнкцияси ҳосил бўлади.

Ҳақиқатан, F ДНШда берилган бўлсин; масалан, F=F₁+F₂+F₃. Фараз қиламиз, F₁, F₂ ва F₂, F₃ лар жуфт-жуфт бирикади, яъни F₁+F₂=G₁, F₂+F₃=G₂, у ҳолда G₁+G₂=F₁+F₂+F₃=F. G₁, G₂F эканини кўрсатамиз. Ҳақиқатан ҳам, F=0 дан, G₁=0 ва G₂=0 экани келиб чиқади. Агар F=1 бўлса, ёки G₁=0 ва G₂=1, ёки G₁=1 ва G₂=0, ёки G₁=1 ва G₂=1 бўлиши мумкин. Демак, F функция нолга тенг бўлган барча тўпламларда ва яна баъзи бир тўпламларда G₁ ва G₂ лар ҳам нолга тенг экан.

Амалда қисқартирилган ДНШни қуйидаги кетма-кетликда топган қулайроқ.

ҲДНШда бирлик конституентларнинг мумкин бўлган барча тўлиқ бўлмаган бириктириш амалларини ва ютилишнинг мумкин бўлган барча амалларини ўтказиш.

Сўнгра, (n-1) ҳарфли аъзоларнинг мумкин бўлган барча тўлиқ бўлмаган бириктириш ва ютилиш амалларини бажариш.

Ҳарфлари сони (n-2) бўлган аъзоларнинг мумкин бўлган барча тўлиқ бўлмаган бириктириш ва ютилиш амалларини бажариш ва ҳ.к.

Мисол:

Тўрт ҳарфли конъюнкциялар билан мумкин бўлган барча тўлиқ бўлмаган бириктириш ва ютилиш амалларини бажарамиз. Натижани жадвалга киритамиз:

бириктирилган бириктириш

конъюнкций рақами натижаси

1 - 2

1 - 3