Q2Discrete Mathematics Structure

Question

(a) Define tautology and prove the following : (p → q) → (~q → ~p) is tautology. (b) Define fallacy and prove the following : (p ∧ q) ∧ ~(p ∧ q) is a fallacy. (c) Prove the following : (i) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (ii) p ↔ q ≡ (p → q) ∧ (q → p)

Answer 1

(a) Tautology: $(p \to q) \to (\sim q \to\sim p)$ . This is the law of contraposition. If $p \to q$ is true, then if $q$ is false, $p$ must be false. Truth table shows all rows are True.

(b) Fallacy: $(p \land q) \land \sim (p \land q)$ . This is of the form $A \land \sim A$ , which is always false regardless of the truth values of $p$ and $q$ .

(c) Equivalences: (i) Distributive law $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ . (ii) Definition of biconditional $p \leftrightarrow q \equiv (p \to q) \land (q \to p)$ .

Q2Discrete Mathematics Structure

Question

Answer