MATEMATIK Datum: 970617 Göteborg University Klockan: 8.45-13.45

Telefonvakt: Anette Wiberg 0740-479626 (minicall) Inga Hjälpmedel

Tentamensskrivning in Diskret Matematik

The questions can be answered in English or in Swedish.

1. On the set N × N define the relation (a, b) ≤ (c, d) iff a ≤ c and b ≤ d. Show that this defines a reflexive antisymmetric and transitive relation. How many elements (a, b) satisfy (a, b) ≤ (2, 3)? In general how many elements (a, b) satisfy (a, b) ≤ (p, q)? Show that the relation (a, b) < (c, d) - defined as usual by (a, b) ≤ (c, d) and (a, b) ≠ (c, d) - is well-founded.

2. Let E be the set of infinite subsets X of N such that the complement N − X of X is also infinite. Give an example of an element of E. We define the relation X < Y on E by: X ⊆ Y and X ≠ Y. Show that < is not well-founded by giving an example of an infinite chain X_{0} > X_{1} > X_{2} …

3. Give the definition of a countable set and the proof that the set {0, 1}^{N} is not countable.

4. Find how many (i) functions (ii) one-to-one functions (iii) onto functions (iv) bijections there are from X to Y in these cases; in each case, justify your answer:

• X = {1, 2}, Y = {1, 2},

• X = {1, 2, 3, 4, 5}, Y = {1, 2},

• X = {1, 2}, Y = {1, 2, 3, 4, 5, 6, 7, 8, 9}

5. Classify each of the following propositions as a tautology, a contradiction or neither. Justify your claims by using truth tables or otherwise.

\begin{matrix}(a) ¬P → P, & (b) ((P → Q) → P) → P, & (c) P ∨ (P → Q), \\ (d) (P ∨ Q) → (P ∧ Q), \end{matrix}

and finally

(e) ((P ∨ Q) ∧ (Q ∨ R) ∧ (R ∨ P)) → ((P ∧ Q) ∨ (Q ∧ R) ∨ (R ∧ P)).

6. In a boolean algebra, prove the following equivalence

(1) a = b ⟺ (a ∧ b′) ∨ (a′ ∧ b) = 0

(2) a ∧ b ≤ c ∨ d ⟺ a ∧ c′ ≤ b′ ∨ d.

7. Apply the unification algorithm on the following pair of terms, with C_{3} = {f}, C_{1} = {g} (C_{n} is the set of function symbols of arity n):

(a) f(g(y), g(x), g(z)) and f(g(x), g(z), g(g(y))),

(b) f(f(z, z, x), y, x) and f(y, y, z).

8. Let (a_{n}) and (b_{n}) be two sequences satisfying a_{0} = b_{0} = 1 and

a_{n+1} − b_{n} = 0
b_{n+1} − a_{n} − b_{n} = 0.

Find a recurrence equation for (a_{n}) of the form a_{n+2} = Aa_{n+1} + Ba_{n}. Give a closed form formula for a_{n} and b_{n}.

9. Which one of these formulae are valid? In each case, motivate your answer:

(a) [¬∀x P (x)] ⇒ [∀x¬P (x)],

(b) [∃x¬P (x)] ⇒ [¬∃x P (x)],

(c) [¬∃x P (x)] ⇒ [∀x¬P (x)].