Минимизация систем булевых функций


 

Задача минимизации систем булевых функций хорошо исследована в ФПСБФ Рассмотрим один из наиболее распространенных методов минимизации.

Пусть задана система полностью определенных булевых функций в ДНФ, например:

Все различные элементарные конъюнкции систем булевых функций объединим в множество А, которое назовем полным множеством элементарных конъюнкций системы булевых функций.

Система ДНФ булевых функций называется минимальной, если ее полное множество элементарных конъюнкций содержит минимальное количество букв, а каждая ДНФ булевых функций системы включает минимальное число элементарных конъюнкций наименьшего ранга. минимизация систем полностью определенных булевых функций может производиться по алгоритму, аналогичному алгоритму метода Квайна с небольшими отличиями.

Пример: пусть система булевых функций задана таблицей истинности. Найти МДНФ системы булевых функций.

Представим функции в СДНФ:

1. Построим полное множество А элементарных конъюнкций системы, указывая, какой функции принадлежит каждая конституэнта "1".

 

2. Построим СДНФ функции , конституэнтами "1" которой являются все элементы множества А. Найдем СкДНФ функции .

Выполним все склеивания:

1-2:

2-3:

4-6:

5-6:

Если конституэнты единицы не принадлежат одной и той же функции системы, склеивание не производится.

Выполним все поглощения с учетом признака принадлежности каждой конъюнкции к функциям системы:

3. Строим импликантную матрицу Квайна.

 
 

- ядро функции :

в данном случае ядро совпадает с МДНФ функции .

МДНФ системы булевых функций:

Недостаток метода: большая трудоемкость операций склеивания и поглощения с признаками.


Глава 9



Дата добавления: 2016-07-18; просмотров: 2531;


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

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

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

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