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


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

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

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

Вопрос 14
Минимизация булевой функции методом Квайна.

Представление заданной булевой функции дизъюнктивной нормальной формой (ДНФ), содержащей наименьшее число букв, называется минимизацией этой булевой функции.
Алгорктмизировать минимизацию булевых функций позволяет теорема Квайна: " Если в СовДНФ функции произвести сначала все возможные операции неполного склеивания x/\у\/ неx/\у=x/\у\/nex/\у\/у.
(3.17) и затем все возможные операции поглощения (3.14), то в результате получится сокращенная дизъюнктивная нормальная форма (СокрДНФ) этой функции".
Минимизацию по Квайну надо начинать с совершенной ДНФ. Если функция задана в произвольной дизыс жгивной форме, производят ее развертывание, умножая член, не содержащий какого-либо аргумента, на логическую единицу (закон исключенного третьего 16)) и получая два члена, содержащие весь набор аргументов. Например, функщдо двух аргументов х л у представим в совершенной дизъюнктивной форме как функцию трех аргументов:
х/\у=х/\у/\1=х/\у/\(z\/nez)=(х/\у/\z)/\(х/\у/\nez).

Пример 3.10. Минимизировать функцию
f(x,y,z)=(neх/\у/\z}\/ (neх/\у/\nez)\/ (х/\neу/\z)\/ (х/\neу/\nez)\/(х/\у/\z).

Решение. Так как функция задана с помощью СовДНФ, воспользуемся алгоритмом Квайна. Сначала произведем всевозможные неполные склеивания, используя формулу (3.17). Для наглядности результаты этой операции представим в виде таблицы. В ней укажем новые члены, которые получаются при таком склеивании:
f(x, у, z) = (neх/\у/\z)v(neх/\у/\nez)v(х/\neу/\z)v(х/\neу/\nez)v(х/\у/\z) v v (nex/\у)v(у /\z)v(х/\neу)v(х/\z). В этой формуле подчеркнуты одинаковым образом группы членов, к которым применим закон поглощения. Осуществив соответствующие поглощения, найдем f(x, у, z) = (у/\z)v(nex/\у)v(x/\ney)v(х/\у/\z)v(х/\z). Вновь применим закон поглощения:
f(x,y,z)=(y/\z)\/(nex/\y)\/(x/\ney)\/(x/\z) (3.18). Выясним, есть ли здесь лишние члены. Испытаем вначале слагаемое у/\z, обращаемое в 1 при у=1 и z=1. Оставшееся выражение формулы (3.18) при этом имеет вид neх/\х =1. Следовательно, член у/\z можно исключить: f(x, у,z)=(neх/\y)v (х/\neу)v(х/\z).

Легко показать, что ни одно из оставшихся слагаемых в полученной формуле не является лишним. Следовательно, последняя формула есть СокрДНФ. одна из ее тупиковых форм. Минимальная ДНФ получается применением к ней дистрибутивного закона: f(x,у,z)=(neх/\у)vх/\(neуvz).

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

 

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