[Math] New to discrete mathematics – Disjunctive normal form

discrete mathematicsdisjunctive-normal-form

I just started a Discrete mathematics course and i really need help with one of the exercises. It may not be very difficult, but i am really having a hard time understanding what i should do. Of course i have checked the answer-list in back of the book but unfortunately the exercise is not contained. I am the kind of kind who can not think of anything else than a problem i can not solve, so here i am.

Here is the exercise:

"Suppose that a truth table in n propositional values is specified. Show that a compound proposition with this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations, with one conjunction included for each combination of values for which the compound proposition is ture. The resulting compound proposition is said to be in disjunvtive normal form."

To be honest i had a hard time reading it the first time, but now i am trying to do exactly what the exercise says, but i guess my level is to low yet, to completely understand it.

Suppose i have two propositional values, p, q and their truth tables, how should i proceed from that ( if that is possible? )

Edit:

Suppose this is my truth table of p an q:
p q

t t
t f
f t
f f

Kind regards Chris

Best Answer

Here is a concrete example:

Suppose we have the following truth-table ($P * Q$ is some arbitrary formula involving atomic propositions $P$ and $Q$):

\begin{array}{cc|c} P & Q & P * Q\\ \hline T & T & T\\ T & F & T\\ F & T & F\\ F & F & T\\ \end{array}

Note that the formula is true in rows 1,2, and 4. In row 1, $P$ and $Q$ are both true, so we generate the corresponding expression $P \land Q$. In row 2, $P$ is true and $Q$ is false, so we generate the term $P \land \neg Q$. Row 4 corresponds to $\neg P \land \neg Q$.

If we now disjunct all these terms together, we get:

$$(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)$$

Now see what happens if we put this expression back on a truth-table:

\begin{array}{cc|c|c|c|c} P & Q & P \land Q & P \land \neg Q & \neg P \land \neg Q & (P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)\\ \hline T & T & T & F & F & T\\ T & F & F & T & F & T\\ F & T & F & F & F & F\\ F & F & F & F & T & T\\ \end{array}

Note how each of the disjuncts is true in exactly the one row that it was generated from, and thus how the disjunction is true in exactly those rows where the original expression $P * Q$ is true. Thus, we can describe $P * Q$ with the formula $(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)$. I think you will understand why this process will always work, no matter what the function that needs to be described looks like, and no matter how many atomic propositions are involved.

One last thing: if there is no row where the formula is true, then with this process you would not get any terms. However, this also means that the original formula is a contradiction, and we can always describe a contradiction with $P \land \neg P$ .. which is in DNF.

Related Question