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?
 A: 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. 
A: 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)$
A: 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.
