Find DNF and CNF of an expression 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?
 A: 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?
A: Using SymPy:
>>> x, y, z = symbols('x y z')
>>> Phi = Xor(x,y,z)

The DNF is
>>> to_dnf(Phi,simplify=true)
Or(And(x, y, z), And(x, Not(y), Not(z)), And(y, Not(x), Not(z)), And(z, Not(x), Not(y)))

In $\LaTeX$,
$$\left(x \wedge y \wedge z\right) \vee \left(x \wedge \neg y \wedge \neg z\right) \vee \left(y \wedge \neg x \wedge \neg z\right) \vee \left(z \wedge \neg x \wedge \neg y\right)$$
The CNF is
>>> to_cnf(Phi,simplify=true)
And(Or(x, y, z), Or(x, Not(y), Not(z)), Or(y, Not(x), Not(z)), Or(z, Not(x), Not(y))) 

In $\LaTeX$,
$$\left(x \vee y \vee z\right) \wedge \left(x \vee \neg y \vee \neg z\right) \wedge \left(y \vee \neg x \vee \neg z\right) \wedge \left(z \vee \neg x \vee \neg y\right)$$
A: For DNF:


*

*look at each row where $p = 1$

*encode a proposition from the atoms $p_i$ for row $i$ (that gives $p$ is 1) that has $a_i$ if that atom is 1 in the truth table and $\neg a_i$ if it's 0. You are using an and to combine the atoms so that only this terms is 1 when you are on that row. You can think of this conjunction as a product.

*take the OR of all such proposition corresponding to the rows being 1

*since this proposition is a disjunction (think of it as an addition) that are only 1s for unique rows, you get the whole thing is only 1 when you need it to be 1.


For CNF:


*

*Look at the rows where $p=0$

*encode a proposition from the atoms $p_i$ for row $i$ (that gives p being zero) that has $a_i$ if that atom is 1 in the truth table and $\neg a_i$ if it's 0. Now conjunct them. This is not the form you actually want so negate $p_i$ to get $\neg p_i$. By Demorgans all disjunctions became conjunctions.

*now take the AND of all such disjunctive propositions.

*This is correct because whenever you choose a row, the proposition you built returns 1 IFF you are not in that row. Since you are not in that row, all those rows return 1 simultaneously indicating your not in any of the rows that gives a zero. Thus you get the whole thing giving a 1.



If you need more help check this video:
https://www.youtube.com/watch?v=tpdDlsg4Cws
A: 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) $$
