Минимизация КНФ

Определение. Элементарная дизъюнкция u называется имплицентой булевой функции F , если .

Например, элементарная дизъюнкция является имплицентой функции .

Определение. Если никакая собственная часть имплиценты u ( т.е. ) булевой функции F не является имплицентой F, то u называется простойимплицентой (т. е. если удаление из u хотя бы одного литерала нарушает условие , то u – простаяимплицента).

Например, – простая имплицента булевой функции , имплицента не является простой для этой функции, так как (собственная часть имплиценты ) является имплицентой функции F.

Определение. Конъюнкция всех простых имплицент булевой функции F называется сокращенной КНФ (СкКНФ)функции F.

Например, – СкКНФ булевой функции . Отметим, что СкКНФ является единственной для конкретной булевой функции F.

Определение.КНФ булевой функции F, содер­жащая наименьшее число множителей среди всех КНФ, реализующих функцию F, называется кратчайшей КНФ (КрКНФ).

Например, является также и КрКНФ этой же булевой функции F.

Вообще говоря, для заданной булевой функции F может существовать несколько различных по числу вхождений литералов КрКНФ.

Определение.КНФ булевой функции F, содер­жавшая наименьшее число вхождений литералов среди всех КНФ, ре­ализующих функцию F, называется минимальной КНФ (МДНФ).

Отметим, что для заданной булевой функции F существует, вообще говоря, несколько МКНФ, отличающихся друг от друга чис­лом слагаемых.

Более того, МКНФ не всегда совпадает с КрКНФ булевой функции n переменных F. Хотя для начальных значе­ний n ( n = 2 или n = 3 ) МКНФ всегда совпадает с КрКНФ. Например, является КрКНФ и МКНФ рассматриваемой функции F.

Задача минимизации булевой функции в классе КНФ формулируется следующим образом: тре­буется для булевой функции n переменных F построить КНФ с минимально возможным числом множителей (КрКНФ) или с мини­мально возможным числом вхождений литералов (МКНФ).

Также отметим, что задача минимизации булевых функций n переменных F в классе КНФ также, как и задача минимизации булевых функций n переменных F в классе ДНФ, является чрезвычайно громоз­дкой и ее трудоемкость с ростом n возрастает по экспонен­циальному закону.

К настоящему времени разработано около 200 различных ме­тодов минимизации булевых функций в классе КНФ.

Пример. Составить по таблице истинности СКНФ булевой функции и минимизировать ее, применяя законы склеивания.