По теме
- Определение. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.
- Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.
- Всякий импликант функции f есть часть функции f.
- Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.
- Определение.Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.
- Утверждение. Всякая функция f реализуется своей сокращенной ДНФ.
- Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
- Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.
Алгоритм Куайна построения сокращенной ДНФ
1. Получить СДНФ функции.
2. Провести все операции неполного склеивания.
3. Провести все операции поглощения.
Пример. Минимизировать функцию f=1111010010101111.
Решение.
1. Строим таблицу значения для данной функции (табл.). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл.).
2. Проводим все операции неполного склеивания.
Первый этап склеивания (табл.):
В первом этапе склеивания участвовали все слагаемые СДНФ, значит, ни одно из исходных слагаемых не войдут в сокращенную ДНФ. После первого этапа склеивания (и возможных поглощений) получаем, что
Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл.).
Второй этап склеивания:
В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что
Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.