Apply equivalence rules to convert to CNF
I am having trouble seeing how I could apply the equivalence rules mentioned here to the following formula in order to convert it into Conjunctive Normal Form (CNF).
$$(p \wedge q) \vee (\neg p \wedge r)$$
I know the solution through Wolfram Alpha, but I do not see how these rules could be applied in order to obtain the answer. These rules get a little confusing for me when a negation of a literal is involved. Could someone please help me to understand this process?
$\endgroup$3 Answers
$\begingroup$If we look here we are given an algorithm to follow, and we will see that at each step all we need to do is step $5$.
$$(p \wedge q) \vee (\neg p \wedge r) \equiv ((p \wedge q) \vee \neg p) \wedge ((p \wedge q) \vee r) \quad \text{ distribute} \vee \text{ over } \wedge$$ $$\equiv ((p \vee \neg p) \wedge (q \vee \neg p)) \wedge ((p \vee r) \wedge (q \vee r)) \quad \text{ again distribute} \vee \text{ over } \wedge $$ $(p \vee \neg p)$ is a tautology and we know that $t \wedge a \equiv a$ for any tautology $t$, so that we can just "throw out" $(p \vee \neg p)$. This leaves us with:
$$(q \vee \neg p) \wedge ((p \vee r) \wedge (q \vee r)) \equiv (q \vee \neg p) \wedge (p \vee r) \wedge (q \vee r) \quad \text{ since } \wedge \text{ is associative} $$
This is in conjunctive normal form, although it is not exactly what Wolfram is giving.
$\endgroup$ 5 $\begingroup$This formula is in Disjunctive normal form (DNF), so if you just use those rules to covert to CNF, it will cost much effort. But there is a trick to convert DNF to CNF quickly.
Let denote two new variables A, B such that:
- $A \to (p \wedge q) = \neg A \vee (p \wedge q) = (\neg A \vee p)\wedge(\neg A \vee q)$
- $B \to (\neg p \wedge r) = \neg B \vee(\neg p \wedge r)= (\neg B \vee \neg p)\wedge(\neg B \vee r)$
So your formula in CNF is $(A \vee B)$ together with the constraints above, which means:
$(A \vee B) \wedge (\neg A \vee p)\wedge(\neg A \vee q) \wedge (\neg B \vee \neg p)\wedge(\neg B \vee r)$
$\endgroup$ 3 $\begingroup$First write out the truth table:
p q r (p∧q) (¬p∧r) [(p∧q)∨(¬p∧r)] 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1Now how do you write a disjunctive normal form from this? As a rough outline you interpret all "0s" as negations of the variables, and "1s" as the variables when and only when the statement evaluates to 1, and make an n-ary conjunction of that. Then you make a disjunction of all that. The conjunction normal form consists of the dual of the disjunctive normal form. You can look at the rows where the statement form evaluates to 0 instead of to 1, and exchange "OR" for "AND". We write a literal if it matches to 0, and the negation of the literal if it matches to 1 for the rows where we have a "0".
The definition of a conjunctive normal form says that they have to qualify as wffs or statement forms or significant expressions. To spare your eyes and my labor of writing a string with many parentheses, I will hereafter use Polish notation.
Given an informal rule of detachment, we can thus define the relevant wffs as follows:
- All lower case letters of the Latin alphabet qualify as wffs.
- If $\alpha$ qualifies as a wff, then so does N$\alpha$.
- If $\alpha$, $\beta$ qualify as wffs, then so does K$\alpha$$\beta$.
- If $\alpha$, $\beta$ qualify as wffs, then so does A$\alpha$$\beta$.
Thus, Kpq represents the wff (in a distinct language) above the first column not falling underneath a variable. KNpr represents the wff above the second column not falling underneath a variable, and AKpqKNpr represents the wff above the third column not falling underneath a variable.
AApqr only evaluates to 1 when one of it's variables takes on the value 1. Otherwise it qualifies as false. AApNqr only evaluates to 1 when Nq evaluates to 0, and so do p and r. And so on, allowing us to infer
KKK AApqr AApNqr AANpqr AANpqNr as a conjunctive normal form.
$\endgroup$
