Obtain the principal (canonical) conjunctive normal form of the principal formula
(p ^ q) v (~q ^ r)
where ^ is logical and, v is inclusive or, and ~ is negation.
GATE 1995 · Discrete Mathematics · Propositional Logic · medium
Answer: PCNF = (p v q v r) ^ (p v ~q v r) ^ (~p v q v r) ^ (~p v ~q v r)
Build the truth table: Row(p,q,r): (000)->F v F=F; (001)->F v T=T; (010)->F v F=F; (011)->T v F=T; (100)->F v F=F; (101)->F v T=T; (110)->F v F=F; (111)->T v F=T. False rows: 000(row 0), 010(row 2), 100(row 4), 110(row 6).
Write maxterms for False rows and form PCNF: Row 000: (p v q v r). Row 010: (p v ~q v r). Row 100: (~p v q v r). Row 110: (~p v ~q v r). PCNF = (p v q v r) ^ (p v ~q v r) ^ (~p v q v r) ^ (~p v ~q v r).