Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

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

Элементарная конъюнкция называется импликантой , если она равна 0 на тех наборах, на которых f обращается в 0. Простой импликантой называется импликанта, в которой отбрасывание любой буквы ведет к получению элементарной конъюнкции, которая не является импликантой.

Пример 3.11. Найдем импликанты и простые импликанты для функции . Всего имеется 8 элементарных конъюнкций с переменными x1, x2. Приведем их таблицы истинности.

 

x1 x2 x1®x2 x1x2 x1 x2

 

Из таблиц истинности заключаем, что , , x1x2, , x2 являются импликантами функции f. Из них простыми являются и x2.

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

Известны аналитические и графические способы построения минимальной ДНФ.







Дата добавления: 2015-09-18; просмотров: 392. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.02 сек.) русская версия | украинская версия








Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7