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

Бул функцияларни минималлаштириш.

Тўла аниқланмаган Бул функцияларни минималлаштириш.

Кўп чиқишли схемаларни синтез қилиш.

Бул функцияларни минималлаштириш.

Бул функцияларни минималлаштириш вазифасининг мақсади минимал мураккабликка эга бўлган эквивалент формулани топишдан иборат. Формуланинг мураккаблиги деганда, уни таркибига кирувчи ҳарфлар миқдори тушинилади. Энг яхши ишлаб чиқилган усуллар деб ДНШ да тасвирланган Бул функцияларни минималлаштириш усуллари ҳисобланади. Ушбу усуллар оддий импликантлар тушунчаси асосига қурилган.

Агар бирон бир φ Бул функция, бошқа F функция нолга тенг бўлган тўпламда ҳамда яна бошқа баъзи бир тўпламларда нолга тенг бўлса, φ функция F функцияга тегишли ва унинг импликанти деб юритилади. Тегишлилик шарти қуйидагича ёзилади: F. Масалан, F=XY функцияни қараймиз. Унинг импликантлари ҳисобланади.

F Бул функциянинг оддий импликантлари деб шундай элементар конъюнкцияларга айтиладики, уларнинг ўзлари шу функцияга киради, аммо бу конъюнкцияларнинг биронта ҳам хусусий қисми F функцияга кирмайди. Хусусий қисм деб, кўпайтмадан бир ёки бир неча кўпайтувчини чиқариб ташлаш йўли билан олинган кўпайтмага айтилади. Масалан, кўпайтма қуйидаги хусусий қисмларга эга:

Масалан, учун . Демак ва лар F функциянинг оддий импликантлари ҳисобланади.

Оддий импликантлар ўзида берилган Бул функцияга кирувчи энг қисқа элементар конъюнкцияларни ифодалайди.

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