Метод Квайна-Мак-Класки

 

Метод формализован на этапе нахождения простых импликант. Формализация проводится таким образом:

1) Все конституэнты "1" из СДНФ булевой функции записываются их двоичными номерами.

2) Все номера разбиваются на непересекающиеся группы, в i-ой группе находятся конституэнты "1", содержащие i единиц в номере.

3) Склеиваются только номера соседних групп, склеивание номера как-либо отмечают.

4) Производят все возможные склеивания. Неотмеченные после склеивания номера являются простыми импликантами.

Пример:

1) В СДНФ заменим все конституэнты "1" их двоичными номерами:

2) Образуем группы двоичных номеров и произведем склеивание:

номер группы двоичные номера конституэнт "1"   номер группы двоичные номера конституэнт "1"   номер группы двоичные номера конституэнт "1"
- 0001 0011, 0101 0111, 1110 1111     00*1, 0*01 0*11, 01*1 *111, 111*   0**1

 

 
 

Простые импликанты: *111, 111*, 0**1

МДНФ:

Разбиение конституэнт на группы позволяет уменьшить число парных сравнений при склеивании.

 

Метод Нельсона

 

Метод позволяет получить СкДНФ булевой функции из ее произвольной КНФ. Если в произвольной КНФ булевой функции раскрыть все скобки и произвести все поглощения, то в результате будет получена СкДНФ булевой функции .

Пример:

Найдем СкДНФ:

Произведем поглощения: - СкДНФ.

 






Дата добавления: 2016-07-18; просмотров: 1536; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2020 год. Материал предоставляется для ознакомительных и учебных целей. | Обратная связь
Генерация страницы за: 0.007 сек.