Question

Convert the following sentences to Conjunctive Normal Form (CNF).

3.1. ¬((¬P ↔ R) → ((Q ∧ R) ∨ P))
3.2. ¬((P ∨ Q) → ((P ∨ Q ∨ ¬R) ∧ (R ∨ P ∨ Q)))

Answer 1

CNF: (conjective normal forms)

these are nothing but product of sums so the output is in the form of product of sums

we can convert an expression to cnf using 2 methods

1. using boolean algebra laws

2. using truth tables

for our problems I am using truth table method to convert the given expressions into CNF form.

3.1)

¬((¬P ↔ R) → ((Q ∧ R) ∨ P))

P	Q	R	¬P	¬P ↔ R	Q ∧ R	Q ∧ R) ∨ P)	(¬P ↔ R) → ((Q ∧ R) ∨ P)	¬((¬P ↔ R) → ((Q ∧ R) ∨ P))
0	0	0	1	0	0	0	1	0
0	0	1	1	1	0	0	0	1
0	1	0	1	0	0	0	1	0
0	1	1	1	1	1	1	1	0
1	0	0	0	1	0	1	1	0
1	0	1	0	0	0	1	1	0
1	1	0	0	1	0	1	1	0
1	1	1	0	0	1	1	1	0

3.2)

¬((P ∨ Q) → ((P ∨ Q ∨ ¬R) ∧ (R ∨ P ∨ Q)))

P	Q	R	¬R	A1	A2	A3	R1	R2	¬R2
				P ∨ Q	P ∨ Q ∨ ¬R	R ∨ P ∨ Q	A2 ∧ A3	A1 → R1
0	0	0	1	0	1	0	0	1	0
0	0	1	0	0	0	1	0	1	0
0	1	0	1	1	1	1	1	1	0
0	1	1	0	1	1	1	1	1	0
1	0	0	1	1	1	1	1	1	0
1	0	1	0	1	1	1	1	1	0
1	1	0	1	1	1	1	1	1	0
1	1	1	0	1	1	1	1	1	0