Кафедра информационных систем

Основы дискретной математики — Вопрос 16

By 29.11.2007 No Comments

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).
Вопрос 16
Минимизация булевой функции по методу Нельсона.

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 16
Минимизация булевой функции по методу Нельсона.
Представление заданной булевой функции дизъюнктивной нормальной формой (ДНФ), содержащей наименьшее число букв, называется минимизацией этой булевой функции. Булева функция, представленная в конъюнктивной нормальной форме (КНФ), минимизируется методом Нельсона: «Если, в произвольной КНФ булевой функция раскрыть все скобки в соответствии с дистрибутивным законом и устранить все элементарные поглощения, то в результате получится СокрДНФ этой функции».

Пример 3.13. Минимизировать функцию
f(х,у,z) = (xvney)/\(neх\/z)/\(хvy\/nez), заданную в виде КНФ.

Решение.

Здесь следует применять метод Нельсона. Для этого вначале раскроем скобки с учетом закона противоречия:
f(x, у, z) = (х/\z)v(х/\neу/\z)v(х/\у/\z)v(nex/\ney/\nez)
и здесь последовательно устрйдим элементарные поглощения: вначале в подчеркнутых слагаемых
f(x,у,z)=(x/\z)v(х/\у/\z)v(nex/\neу/\nez), и затем — в новых подчеркнутых. В результате получим
f(x, у,z)=(х/\z)v(neх/\neу/\nez). Это — искомая минимальная ДНФ.

Leave a Reply