MTH 307 Midterm, Fall 2005

Lebanese American University Fall 2005 Byblos Discrete Structure II Test #2 Date: 21/12/2005 Duration: 1h 30 1. Use propositional resolution to prove the following: (a) {A → B ∨ C} ⊢ (A → B) ∨ (A → C) (b) {A → B, B → A, A ∨ B} ⊢ A ∧ B 2. Find natural deduction proof of the following formula: ∃x (ϕ(x) ∧ ψ(x)) → (∃x ϕ(x) ∧ ∃x ψ(x)) Prove, by a counter-example, that the reverse of this formula is not universally valid. 3. Find a resolution proof of SSSS0 − SS0 = SS0, assuming the appropriate recursion equations for the difference predicate diff (x, y, z). 4. (a) Give the definition of a tree and a bipartite graph. (b) Prove that a graph can be coloured by two colours iff it is a bipartite graph. (c) Prove that a tree is a bipartite graph and outline an algorithm which explains how we can find the representation of a tree as a bipartite graph. (d) Give an example of a bipartite graph which is not a tree. (e) We say that a graph G is a forest if it is without circuits. i. Verify that a tree is a forest. Give an example of a forest which is not a tree. ii. Prove that a forest is a bipartite graph and outline an algorithm which explains how we can find the representation of a forest as a bipartite graph. iii. Give an example of a bipartite graph which is not a forest. 5. Bonus question. We consider the following predicate logic formula: ∀x ∃y ϕ(x, y) −→ ∀y ∃x ϕ(x, y) This formula is universally valid? Give a deduction proof or a counter-example. MARKS : 1. [20] 2. [15] 3. [15] 4. [50] 5. [10] 1 SOCIAL