Найти длину совершенной ДНФ

[kdm]

Найти длину совершенной ДНФ $f(\tilde x^n)\oplus g(\tilde x^n)$, если известны длины совершенных ДНФ следующих функций:

1)$f(\tilde x^n) * g(\tilde x^n)$ и $f(\tilde x^n) \vee g(\tilde x^n)$
2)$f(\tilde x^n) \rightarrow g(\tilde x^n)$ и $g(\tilde x^n) \rightarrow f(\tilde x^n)$

Ответ: 1) $l_1 - l_2$, где $l_1$ - длина $f(\tilde x^n) \vee g(\tilde x^n)$, $l_2$ - длина $f(\tilde x^n) * g(\tilde x^n)$

2) $2^n^+^1 - l_1 - l_2$,где $l_1$ - длина $f(\tilde x^n) \rightarrow g(\tilde x^n)$, $l_2$ - длина $g(\tilde x^n) \rightarrow f(\tilde x^n)$

Вопрос в том, как это делать? Интересно само решение. Или хотя бы куда направить свои мысли.

[luitzen]

Длиной СДНФ назовём число элементарных конъюнкций в ней.

1.
Необходимым условием для того, чтобы набор учитывался пр подсчёте длины СДНФ (иначе говоря, увеличивал её на единицу), является $f\lor g = 1$ на этом наборе. Число таких наборов — $l_1$.

Вместе с тем, если на этом наборе $f * g = 1$, то такой набор приходится не учитывать. Таких наборов $l_2$ и, что удивительно, для всех них $f\lor g = 1$ (т. е. все они были занесены в кандидаты на предыдущем шаге; нет такой ситуации, что мы не имеем права «минусовать» элементарную конъюнкцию по той причине, что она не была «плюсована»).

Короче говоря, из того, что $f \oplus g$ эквивалентно $(f \lor g) * \overline{(f * g)}$, всё следует.

2.
Попробуйте разобраться самостоятельно. Возможно, Вам поможет эквивалентность $f \oplus g$ и $\overline{(f \to g)}\lor \overline{(g \to f)}$.

Интересно, откуда взялось $2^{n+1}$? Неужели придется вводить фиктивную переменную? Не хотелось бы, конечно.