Задача 3.1. Докажите, что совершенная, сокращенная и минимальная ДНФ функции odd(X1,X2,…, Xn) совпадают и состоят из 2n-1 элементарных конъюнкций длины n.
Задача 3.2. Докажите лемму 3.2 возвратной индукцией по i.
Задача 3.3. Используя лемму 3.2, докажите утверждение 2 теоремы 3.2.
Задача 3.4. Постройте минимальные УБДР для двуместных функций: x

y, x

y, x + y, x

y, x|y.
Задача 3.5. Постройте минимальные УБДР для функции

относительно двух упорядочений переменных:

• x1 < x2 < x3 < x4 < x5 < x6 и
• x1 < x3 < x5 < x2 < x4 < x6.

Задача 3.6. Пороговая функция Tnk от n переменных с порогом k выдает 1, если во входном наборе имеется не менее k единиц: Tnk(x1,x2, …, xn) = 1

x1 + x2 + … + xn

k.

• Постройте минимальные УБДР для пороговых функций T32, T42, T53.
• Зависит ли сложность минимальной УБДР для пороговых функций от порядка переменных?
• Оцените сложность минимальной УБДР для пороговой функции Tnk.

Задача 3.7. Выберите подходящий порядок переменных и постройте для него минимальные УБДР, реализующие функции из задач 12.5 и 12.6.
Задача 3.8. Как мы видели, логические схемы естественным образом реализуются в виде неветвящихся программ. Наоборот, для деревьев решений и УБДР естественным программным представлением являются ветвящиеся программы, включающие лишь условные операторы вида if ... then ... else ... с тестами вида "x = 0?" и "x = 1?" (они соответствуют внутренним вершинам диаграмм) и операторы присвоения значения 0 или 1 результату (они соответствуют вершинам-стокам).
Напишите ветвящиеся программы, вычисляющие функции, представляемые УБДР D2 на рис. 3.3 и Df на рис.3.6.