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?
3 Answers
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.
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)$
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 1
Now 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.
