Discrete Mathematics Assignment1

Assignment1

August 28, 2009 1. Prove or disprove the following u (a) (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D) (b) (A − B) × (C − D) = (A × C) − (B × D) 2. Convert the following into cnf and dnf (a) (p → q) ↔ (¬p ∨ q) (b) (p ↔ q) ∧ (¬q ← s) (c) q ∧ (p → q) → q 3. Prove the following by using mathematical induction (a) 12 − 22 + 32 − 42 + . . . + (−1)n−1 n2 = (−1)n−1 n(n + 1)/2 (b) n! < nn 4. Prove the following logical inferences (a) P, P → (Q → (R ∧ S)) ⇒ Q → S (b) P → Q ⇒ P → (P ∧ Q) (c) Prove the following set of premises is inconsistent {P → Q, P → R, Q → ¬R, P } 5. Disprove the following (a) ∃y∃xP xy → ∀x∃yP xy (b) ∃x∀yP xy → ∀x∀yP xy 1

6. Show whether the following relations are reflexive, symmetric and transitive. Find r(R), s(R) and t(R). R = {(a, a), (a, b), (b, a)}. 7. R1 and R2 be arbitrary relations on a set A. Prove or disprove the following. (a) If R1 and R2 are reflexive then R1 R2 is reflexive. (b) The transitive closure of a symmetric relation is symmetric. 8. Prove or disprove that the union and intersection of two equivalence relations is an equivalence relation. 9. Let (A, ≤) be a partially ordered set. Let ≤R be a binary relation on A such that for a and b in A, a ≤R b if and only if b ≤ a. (a) Show that ≤R is a partial ordering relation. (b) Show that if (A, ≤) is a lattice, then (A, ≤R ) is also a lattice.

2