Apply equivalence rules to convert to CNF

Question

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?

Answer 1

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.

Answer 2

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)$

Answer 3

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:

1. All lower case letters of the Latin alphabet qualify as wffs.
2. If $\alpha$ qualifies as a wff, then so does N$\alpha$.
3. If $\alpha$, $\beta$ qualify as wffs, then so does K$\alpha$$\beta$.
4. 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.