Минимизиране на булевите функции на алгебра

Една от основните задачи на синтеза на дискретни устройства е тяхното изграждане с минимално използване на логически елементи, които изпълняват функциите за формиране на стойностите на входните променливи и изпълнението на елементарни FAL.

Каноничният проблем за минимизиране на FAL, реализиран от дискретно устройство, е да се намери алгебричен израз с минималния брой появявания на променливи.

Първоначалните форми на FAL при решаване на каноничната задача за минимизиране са SDNF и SKNF, които имат максимален брой появявания на елементи, равен на броя набори от стойности на променливи, върху които е дефинирана функцията.

Минимизиране на FAL в SDNF.

Минималният DNF (MDNF) е запис на функция, който съдържа минималния брой появявания на променливи в сравнение с други DNF, еквивалентни на тази функция.

Всички методи за минимизиране се основават на двойно залепване на съседни съставни части на единицата, различаващи се по стойности само на една променлива. Например в израза (х1 ∙ х2 ∙ х3) + (∙ х2 ∙ х3) - две съставки на едната са съседни, тъй като те се различават по стойностите на една променлива х1, и така те могат да бъдат слепени заедно, като се изключи тази променлива: х2 ∙ х3 ∙ (х1 +) = х2 ∙ х3 ∙ 1 = х2 ∙ х3. В резултат на залепването на съставните части на единството, броят на появите на променливи в FAL е намалял.

---