Условие:
Размером ДНФ будем называть число вхождений переменных в нее. Ка
ков минимальный размер ДНФ, задающей функцию x1 ⊕...⊕xn?
Решение:
Для нахождения минимального размера ДНФ (дизъюнктивной нормальной формы), задающей функцию x1 ⊕ ... ⊕ xn, необходимо понять, как работает операция исключающего ИЛИ (XOR). Функция x1 ⊕ ... ⊕ xn равна 1, если количество единиц среди переменных x1, x2, ..., xn нечетно, и равна 0, если количество единиц четно. Теперь рассмотрим, как можно представить эту функцию в виде ДНФ. ДНФ состоит из конъюнкций (AND) переменных, которые объединяются дизъюнкциями (O...