Find DNF and CNF of an expression

Question

I want to find the DNF and CNF of the following expression

$$ x \oplus y \oplus z $$

I tried by using

$$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$

but it got all messy.

I also plotted it in Wolfram Alpha, and of course it showed them, but not the steps you need to make to get there.

Any ideas to how this could be done?

Answer 1

Simply write down the truth table, which is quite simple to find, and deduce your CNF and DNF.

\begin{array}{| c | c | c | c |} \hline X & Y & Z & \\ \hline T & T & T & T \\ \hline T & T & F & F \\ \hline T & F & T & F \\ \hline T & F & F & T \\ \hline F & T & T & F \\ \hline F & T & F & T \\ \hline F & F & T & T \\ \hline F & F & F & F \\ \hline \end{array}

If you want to find DNF, you have to look at all rows that ends with $T$. When you find those rows, take the $x, y,$ and $z$ values from each respective column. Thus, you get $$(x \wedge y \wedge z) \vee (x \wedge \neg y \wedge \neg z) \vee (\neg x \wedge y \wedge \neg z) \vee (\neg x \wedge \neg y \wedge z).$$ Similarly, you can find CNF

$$ (\lnot x \lor \lnot y \lor z) \land (\lnot x \lor y \lor \lnot z) \land (x \lor \lnot y \lor \lnot z) \land (x \lor y \lor z) $$

Answer 2

Aha. In such a more general setting you can interpret $\oplus$ as addition modulo 2. E.g., if you have 5 variables $a_1, \ldots, a_4 \in \{0, 1\}$. Then $a_1 \oplus \cdots \oplus a_4 = (a_1 + \ldots + a_4) \mod 2$. Using this fact, you can write down your CNF. In fact, this "method" uses implicitly truth tables.

For example, assume that we want to find the CNF of $a \oplus b \oplus c \oplus d$. Then you have to enumerate all disjunctions of $a, b, c, d$ with an even number of negations. In the CNF you will find $(a \vee b \vee c \vee d)$, $(\neg a \vee \neg b \vee c \vee d)$, $(\neg a \vee b \vee \neg c \vee d)$ etc. but not $(\neg a \vee b \vee c \vee d)$.

Note that in general transforming formulas by equivalence transformations to CNF and DNF is NP-hard.

I hope the idea is clear?