Пятница, 09.12.2016, 08:44
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 30
Гостей: 30
Пользователей: 0
» »
17:39
Метод Квайна

Метод квайна (Куайна)

  • Определение. Элементарная конъюнкция К называется импликантом функции 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 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что

Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.

Категория: логика | Просмотров: 943 | Добавил: Admin | Теги: булева алгебра | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .