Учебный материал
По теме
- Определение. Элементарная конъюнкция К называется импликантом функции 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. ... Смотреть решение »