Answer to Question #259420 in Discrete Mathematics for King

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)$