Determine both the conjunctive and disjunctive normal forms for the following expression [verification]

Question

I have the following expression:

$$ (((p_3 \lor p_1) \ \land (p_2 \to p_1)) \ \land (p_3 \leftrightarrow p_2)) $$

---

Work so far:

1) CNF:

$ \begin{align*} &\ (((p_3 \lor p_1) \land (p_2 \to p_1)) \land (p_3 \leftrightarrow p_2)) & \text{(Given)} \\ \equiv &\ (((p_3 \lor p_1) \land (\neg p_2 \lor p_1)) \land (p_3 \leftrightarrow p_2)) & \text{(Simplification of implication)} \\ \equiv &\ (((p_3 \lor p_1) \land (\neg p_2 \lor p_1)) \land ((\neg p_3 \lor p_2 ) \land (p_3 \lor \neg p_2))) & \text{(Simplification of biconditional)} \\ \equiv &\ ((p_3 \lor p_1) \land (\neg p_2 \lor p_1) \land (\neg p_3 \lor p_2 ) \land (p_3 \lor \neg p_2)) & \text{(Associativity of conjunction)} \\ \end{align*} $

Q.E.D. (Whilst the expression could further be simplified, at this point it satisfies the definition of CNF).

2) DNF:

\begin{align*} &\ (((p_3 \lor p_1) \land (p_2 \to p_1)) \land (p_3 \leftrightarrow p_2)) & \text{(Given)} \\ \equiv &\ (((p_3 \lor p_1) \land (\neg p_2 \lor p_1)) \land (p_3 \leftrightarrow p_2)) & \text{(Simplification of implication)} \\ \equiv &\ (((p_3 \lor p_1) \land (\neg p_2 \lor p_1)) \land (( p_3 \land p_2 ) \lor (\neg p_3 \land \neg p_2))) & \text{(Simplification of biconditional)} \\ \equiv &\ ((p_1 \lor (\neg p_2 \land p_3)) \land (( p_3 \land p_2 ) \lor (\neg p_3 \land \neg p_2))) & \text{(Distribution of disjunction over conjunction)} \\ \equiv &\ ((p_1 \land ( p_3 \land p_2 )) \lor (p_1 \land (\neg p_3 \land \neg p_2)) \lor ((\neg p_2 \land p_3) \land ( p_3 \land p_2 )) \lor ((\neg p_2 \land p_3) \land (\neg p_3 \land \neg p_2))) & \text{(Distribution of conjunction over disjunction)} \\ \end{align*}

Q.E.D. (As above, sufficient albeit messy).

---

Why have I posted this question for verification?

• I am not sure if I have applied the steps correctly.
• I suspect that my approach is too verbose, and since this was taken from a practice exam where it wasn't worth many marks, I want to know if I can simplify my approach/save time anywhere. (So far the only thing I can think of is introducing shorthand terms a,b,c,d for the clauses in the final steps of each calculation, but this assumes my general approach is robust).

Is my solution correct? Can it be improved?

Answer 1

Yes, they are both correct.

The result for the DNF can be simplified:

$$((\neg p_2 \land p_3) \land ( p_3 \land p_2 )) \text{ and } ((\neg p_2 \land p_3) \land (\neg p_3 \land \neg p_2)))$$

are both impossible because they contain $x \land \neg x$. Hence you could just write $$((p_1 \land ( p_3 \land p_2 )) \lor (p_1 \land (\neg p_3 \land \neg p_2)).$$

---

There is a method which is computationally acceptable when you have few variables, such as in this case. You write the 'truth table' (the following picture is generated using a truth table generator):

Then the expression is true exactly when $(p_1, p_2, p_3) = (1, 1, 1) = v_1$ or $(p_1, p_2, p_3) = (1, 0, 0) = v_4$.

Consider the formulae

$$ \begin{align} \psi_1 &= (p_1 \land p_2 \land p_3) \\ \psi_4 &= (p_1 \land (\neg p_2) \land (\neg p_3)). \end{align} $$

The formula $\psi_i$ is true exactly when the truth assignment is that of $v_i$, hence the expression is equivalent to

$$(p_1 \land p_2 \land p_3) \lor (p_1 \land (\neg p_2) \land (\neg p_3))$$

as found before.

At this point you can easily find a CNF as follows

1. find a DNF for the negation: the expression is false exactly when $p_1$ is false or (the other two cases), hence $$(\neg p_1) \lor (p_1 \land (\neg p_2) \land p_3) \lor (p_1 \land p_2 \land (\neg p_3));$$

2. negate the previous expression to get the result: $$ \begin{align} &\ p_1 \land ((\neg p_1) \lor p_2 \lor (\neg p_3)) \land ((\neg p_1) \lor (\neg p_2) \lor p_3) \\ \equiv &\ p_1 \land (p_2 \lor (\neg p_3)) \land ((\neg p_2) \lor p_3). \end{align} $$

The results we found for the CNF are different but equivalent. I feel there is less chance to make errors with this method instead of manipulating long expressions, but this is a personal opinion.