Reference no: EM131523218
Q1. (a) Determine the truth value of the statement, give reasons for your answer.
(∀x ∈ R) (∃y ∈ R) ((y ≥ 0 ∧ y = x) v (x < 0 ∧ y = -x)).
(b) Show that the statement ∃x∀yP(x, y) = ∀y∃xP(x, y) is universally valid, i.e. is true for any interpretation of the predicate P(x, y) in a non-empty domain U common for all quantifiers.
(c) Prove by contraposition that if a + b < 2n, then either a < n or b < n where the universe is the set of real numbers R. Write down the corresponding formal statement in Predicate Logic.
Q2. (a) Prove that if A and B are sets with A - B ⊆ B, then A ⊆ B. Do not use Venn diagrams.
(b) Let A be a set with precisely 4 elements, that is, |A| = A. Compute (just give final answer):
(1) |A x A| =
(2) |P(A)| =
(3) |P(P(A))1| =
(4) |A ∪ A| =
(5) |A ∩ A| =
(6) |A - A| =
(c) For sets A, B, C, D, let f : A → B and g : C → D be functions.
Let h : A x C → B x D be defined by
h((x, y)) = (f (x), g(y)) for all (x, y) ∈ A x C.
(i) Assume that f and g are both injective. Prove that then h is also injective.
(ii) Assume that f and g are both surjective. Prove that then h is also surjective.
Q3. (a) Show that f (x) = 5x4 + 3x2 + 2x + 1 is Θ(x4) by directly finding the least possible witnesses.
(b) Give as good a big-O estimate as possible (in terms of the standard reference functions) for the function
f(n) = n log(n3 + 1) + (n + 1) log(n!) + k=1Σnk, where n is a positive integer.
Q4. (a) Determine whether each binary relation R on the set Q of rational numbers is reflexive, symmetric, anti-symmetric, or transitive where xRy if and only if
(i) x ≠ y.
(ii) xy ≥ 1
(b) Find the equivalence classes [1] and [1/2] of 1 and 1/2 respectively for the equivalence relation R on R : (a, b) ∈ R. iff a - b ∈ Z.
Q5. Prove by induction
(a) k=1Σnk⋅2k = (n-1)2n+1 + 2, n ≥ 1.
(b) 1 + 1/√2 + 1/√3 + ⋅ ⋅ ⋅ + 1/√n > √n, n ≥ 2.
Q6. (a) For the Fibonacci sequence defined recursively by f0 = 0, f1 = 1, and fn+1 = fn + fn-1 for all n ≥ 1 prove that
fn+1 fn-1 - fn2 = (-1)n for all integers n ≥ 1.
(b) Show that the set S ⊆ Z defined by 1 ∈ S and s + t ∈ S whenever s ∈ S and t ∈ S is the set of positive integers Z+.
Q7. (a) Find a recurrence relation and give initial conditions for the number of bit strings of length n that contain at least 3 consecutive zeroes.
(b) How many bit strings of length 8 contain at least 3 consequtive zeroes?
Q8. (a) Solve the recurrence relation
an = -5an-1 - 6an-2 + 42 ⋅ 4n, n ≥ 2
with initial conditions a0 = 16, a1 = 65.
(b) (i) Which complete bipartite graphs Km,n are trees?
Let T be a full 8-ary tree with 201 vertices.
(ii) How many internal vertices does T have?
(iii) How many leaves does T have?
Q9. (a) Determine whether the digraphs G and H below are isomorphic.
(b) For which values of n are the graphs Kn and Cn bipartite?
(c) Show that in a finite simple undirected graph with at least two vertices there must be two vertices of the same degree.
Q10. (a) Can someone cross all the bridges shown in this map exactly once and return to the starting point?
(b) For which values of m and n does the complete bipartite graph Km,n have an
(i) Euler circuit?
(ii) Euler path?
(iii) Hamilton circuit?
(iv) Hamilton path?
Please provide detailed steps for the proofs.