Question

For each of the following compound propositions give its truth table and derive an

equivalent compound proposition in disjunctive normal formal (DNF) and in conjunc￾tive normal form (CNF).

(a) (p → q) → r

(b) (p ∧ ¬q) ∨ (p ↔ r)

Answer 1

a) (p → q) → r

The truth table is presented below

DNF:

$(p\to q)\to r\iff (\lnot p\lor q)\to r \iff \lnot(\lnot p \lor q)\lor r\iff(p\land \lnot q)\lor r$

CNF:

$(p\to q)\to r\iff (\lnot p\lor q)\to r \iff \lnot(\lnot p \lor q)\lor r\iff(p\land \lnot q)\lor r \iff (r\lor p)\land (r\lor \lnot q)$

(b) (p ∧ ¬q) ∨ (p ↔ r)

The truth table is presented below

DNF:

$(p ∧ ¬q) ∨ (p ↔ r) \iff (p ∧ ¬q) ∨ (p\land r) \lor (\lnot p \land \lnot r)$

CNF:

$(p ∧ ¬q) ∨ (p ↔ r) \iff (p ∧ ¬q) ∨ (p\land r) \lor (\lnot p \land \lnot r) \iff \lnot(\lnot((p ∧ ¬q) ∨ (p\land r) \lor (\lnot p \land \lnot r)))\iff \lnot((\lnot p \lor q) \land (\lnot p \lor \lnot r) \land (p\lor r))\iff \lnot((\lnot p\lor(q\land \lnot r))\land (p\lor r))\iff \lnot(((\lnot p \lor (q\land \lnot r))\land p)\lor (\lnot p \lor (q\land \lnot r))\land r))\iff \lnot((p\land q\land \lnot r)\lor (r \land \lnot p)) = (\lnot p \lor \neg q \lor r) \land (\lnot r \lor p)$