Минимизация нормальных форм
Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.
Всякий импликант функции fесть часть функции f.
Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.
Определение. Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.
Утверждение. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.
предыдущаяследующая