1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I agree with your personal opinion, and whilst one could argue that it is subjective, I think your answer provides an extra dimension for people to think about these problems in. Thanks! $\endgroup$ – Oscar Jul 9 '18 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.