Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 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). Это - искомая минимальная ДНФ.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным