TAOCP 7.1.1 Exercise 16
A full disjunctive normal form has the structure f(x_1,\ldots,x_n)=\bigvee_{k\in K} T_k(x_1,\ldots,x_n), where each $T_k$ is a minterm, that is, a conjunction of $n$ literals, each literal being eithe...
Exercise 16. [15] [15] Can we replace each $\vee$ by $\oplus$ in a full disjunctive normal form?
Verified: yes
Solve time: 57s
Solution
A full disjunctive normal form has the structure
$$ f(x_1,\ldots,x_n)=\bigvee_{k\in K} T_k(x_1,\ldots,x_n), $$
where each $T_k$ is a minterm, that is, a conjunction of $n$ literals, each literal being either $x_j$ or $\bar{x}_j$, and $K$ is the set of all assignments for which $f=1$.
Fix two distinct indices $i\neq j$ in $K$. The minterms $T_i$ and $T_j$ correspond to two different complete assignments of $(x_1,\ldots,x_n)$. Hence there exists an index $r$ such that one of $T_i$ and $T_j$ contains $x_r$ while the other contains $\bar{x}_r$. For any valuation of $(x_1,\ldots,x_n)$, the conjunction $T_i \wedge T_j$ requires simultaneously $x_r=1$ and $x_r=0$, so
$$ T_i \wedge T_j = 0. $$
Thus no two distinct minterms can be simultaneously true.
For any fixed input $(a_1,\ldots,a_n)$, at most one minterm $T_k$ evaluates to $1$. If none evaluates to $1$, both
$$ \bigvee_{k\in K} T_k \quad \text{and} \quad \bigoplus_{k\in K} T_k $$
evaluate to $0$. If exactly one minterm, say $T_{k_0}$, evaluates to $1$, then the OR evaluates to $1$ and the XOR also evaluates to $1$, since all other terms are $0$ and XOR of a family with a single $1$ equals $1$.
Therefore, for every input,
$$ \bigvee_{k\in K} T_k ;=; \bigoplus_{k\in K} T_k. $$
This shows that every full disjunctive normal form remains unchanged when each $\vee$ is replaced by $\oplus$.
This completes the proof. ∎