2015-04-01
1232
1. Доказать, что дизъюнкция любого числа импликант логической функции 
также является импликантом этой функции.
Указание. При доказательстве можно воспользоваться определением импликанта и законом дистрибутивности конъюнкции относительно дизъюнкции (2.3).
2. Написать подпрограмму, производящую склеивание двух элементарных конъюнкций 
и 
, заданных своими векторами вхождения и обращения, каждый из которых занимает одно машинное слово (т. е. число переменных в конъюнкциях меньше, чем разрядность машины). Результат склеивания также оформить в виде вектора вхождения и обращения. Если и 
не склеиваются, то выдавать два нулевых слова.
3. Используя результаты задачи 2, программно реализовать минимизацию булевых функций методом Квайна. Исходная логическая функция задается вектором значений.
Указание. При реализации этапа получения сокращенной ДНФ используйте разбивку конъюнкций на пояса (см. выше).
4. Разработать структуру хранения бинарного графа и реализовать алгоритм его построения, если исходная булева функция задана в ДНФ, каждая элементарная конъюнкция представлена векторами вхождения и обращения. Выбор переменной разложения в алгоритме построения бинарного графа осуществлять произвольно.
5. Из заданного множества элементарных конъюнкций K выделить простые импликанты 
, если:
1) 
, 
;
2) 
, 
;
3) 
, 
.
6. С помощью метода Блейка-Порецкого построить сокращенную ДНФ по заданной ДНФ D.
;
;
.
7. Сокращенную ДНФ функции 
, заданной в виде КНФ, можно получить следующим образом. Сначала раскрыть скобки, пользуясь законом дистрибутивности, затем вычеркнуть из получившейся ДНФ буквы и конъюнкции, используя правила 
, 
, 
, 
. Например, функция задана КНФ 
. Раскрыв скобки, получим ДНФ функции 
. Применяя указанные выше правила, получим функцию в сокращенной ДНФ: 
.
Получить сокращенную ДНФ функции f заданной КНФ:
;
;
.
8. Построить все тупиковые ДНФ следующих функций:
;
;
.
9. Выяснить, являются ли тупиковыми или минимальными следующие ДНФ:
;
;
.
10. Переменная 
является существенной переменной функции 
тогда, и только тогда, когда эта переменная явно входит в сокращенную ДНФ функции . Получить сокращенную ДНФ функции и указать существенные переменные.
;
;
.
