Find DNF and CNF of an expression

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) $$

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?

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)$$

For DNF:

1. look at each row where $p = 1$
2. 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.
3. take the OR of all such proposition corresponding to the rows being 1
4. 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:

1. Look at the rows where $p=0$
2. 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.
3. now take the AND of all such disjunctive propositions.
4. 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