Question

Convert the logical statement ~(P || ~R) || (Q -> R) to conjunctive normal form. Please explain the steps!!

Answer 1

Conjunctive normal form is equivalent to Product of Sums(POS). It is a conjunction of disjunctive clauses.

Assumption:- || stands for logical OR. (disjunction). ^ stands for logical AND(Conjunction)

General Outline: (Only for propositional logic -- There are additional rules for FOL.)

1. Remove double implication, P <-> Q ≡ (P -> Q) ^ (Q -> P)

2. Remove implication, P->Q ≡ ~P || Q

3. Apply demorgan's laws to get individual literals

4. Check if the result is in CNF. If it is not keep applying distributive law( (P ^ Q) || R ≡ (P || R) ^ (Q || R)) until it comes in CNF form.

Question:

~(P || ~R) || (Q -> R)

Remove the implication(->)

≡ ~(P || ~R) || (~Q || R) [Since, P->Q ≡ ~P || Q, by definition]

Apply demorgan's law to ~(P || ~R).

≡ (~P ^ ~ (~R)) || (~Q || R) [~(P || Q) ≡ (~P ^ ~Q)]

≡ (~P ^ R) || (~Q || R) [~(~P) ≡ P, by involution]

It is not in CNF. So apply distributive law :

≡ (~P || ~Q || R) ^ (R || ~Q || R) [(P ^ Q) || R ≡ (P || R) ^ (Q || R)]

≡ (~P || ~Q || R) ^ (~Q || R) ....(Answer) [Since P || P ≡ P , identity law]

The above result is in CNF with two clauses ~P || ~Q || R and  ~Q || R.