Главная | Обратная связь

Методы минимизёации булевых функций

МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

 

План

1. Методы минимизации булевых функций

1.1. Метод диаграмм Вейча

1.2. Метод Квайна

1.3. Метод импликантных таблиц

2. Индивидуальные задания

 

Литература

1 Прикладная теория цифровых автоматов Киев "Вища Школа" 1987 К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский, Ю.С. Каневский, М.М. Пиневич страницы (195 - 197).

2. Прикладна теорія цифрових автоматів" Київ, "Вища Школа" 1987, К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйський, Ю.С. Каневский, М.М. Пиневич, ст. (201 - 202).

Методы минимизёации булевых функций

Для рассмотрения методов минимизации введем некоторые определения.

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

Под импликантой булевой функции f(x₁, х₂, ...,х_n) понимается такая булева функция f₁(x₁, х₂, ...,х_n), если на любом наборе значений переменных x₁, х₂, ...,х_n, на котором значение функции f₁ равно единице, значение функции f также равно единице.

Под простой импликантой булевой функции f(x₁, х₂, ...,х_n) понимается всякое элементарное произведение , которое является импликантой функции f и никакая собственная часть этого произведения в функцию f не входит, т.е. простые импликанты — элементарные конъюнкции наименьшего ранга, входящие в данную булеву функцию.

Сокращенной дизъюнктивной нормальной формой булевой функции называется такая функция, которая равна дизъюнкции всех своих простых импликант.

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

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

Таким образом, общую задачу минимизации булевых функций можно решать в такой последовательности.

1. Для заданной функции находят сокращенную ДНФ, т.е. все простые импликанты.

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