Exam 2

Question 1

Consider f, g : Z>0 → R⩾0. Give the definition of f = O(g).

Answer 1

f = O(g) if and only if there exist an integer n0 > 0 and a real number c > 0 such that,
for every n ⩾ n0, f (n) ⩽ cg(n).

Question 2

Consider f, g : Z>0 → R⩾0. Give the definition of f = Ω(g)

Answer 2

f = Ω(g) if and only if there exist an integer n0 > 0 and a real number c > 0 such that,
for every n ⩾ n0, f (n) ⩾ cg(n).

Question 3

Consider f, g : Z>0 → R⩾0. Give the definition of f = Θ(g)

Answer 3

f = Θ(g) if and only if f = O(g) and f = Ω(g)

Question 4

Give the definition of a finite state machine

Answer 4

A finite state machine is a tuple (S, s0, I, δ) where
* S is a finite set (of states),
* s0 is an element of S (the starting state),
* I is a finite set (of inputs),
* δ : S × I → S is a function (the transition function).

Question 5

Give the definition of a transducer (i.e. a finite state machine with output).

Answer 5

A transducer is a finite state machine equipped with a finite set (of outputs) O such
that its transition function is given by δ : S × I → S × O, where S and I denote the set of states
and the set of inputs of the finite state machine, respectively

Question 6

Give the definition of an acceptor.

Answer 6

An acceptor is a finite state machine equipped with a subset A ⊆ S of accepted states,
where S denotes the set of states of the finite state machine.

Question 7

State the principle of mathematical induction.

Answer 7

Given a predicate P (n) where n is a natural number, if
* P (0) holds and
* for every k ∈ N, P (k) ⇒ P (k + 1)
then P (n) holds for every n ∈ N

Question 8

State the strong form of the principle of mathematical induction

Answer 8

Given a predicate P (n) where n is a natural number, if
* P (0) holds and
* for every k ∈ N, P (0) ∧ P (1) ∧ · · · ∧ P (k) ⇒ P (k + 1)
then P (n) holds for every n ∈ N

Question 9

State the well-ordering principle.

Answer 9

Every non-empty subset of the natural numbers has a smallest element.

Question 10

Name the three components of the recursive definition of a set.

Answer 10

The recursive definition of a set consists of three components:
1. the basis elements,
2. the recursive rule, and
3. the exclusion statement

Question 11

State the structural form of the principle of mathematical induction.

Answer 11

Given a predicate P (x) where x belongs to a recursively-defined set S with recursive
rule “x ∈ S ⇒ f (x) ∈ S”, if
* P (x) holds for every basis element x ∈ S and
* P (x) ⇒ P (f (x)) for every x ∈ S
then P (x) holds for every x ∈ S.

Question 12

Give the definition of a relation R between a set X and a set Y

Answer 12

A relation R between X and Y is a subset of X × Y

Question 13

Give the definition of a relation R on a set X being reflexive

Answer 13

The relation R is reflexive if, for every x ∈ X, xRx

Question 14

Give the definition of a relation R on a set X being symmetric

Answer 14

The relation R is symmetric if, for every x, y ∈ X, xRy ⇔ yRx.

Question 15

Give the definition of a relation R on a set X being anti-symmetric

Answer 15

The relation R is anti-symmetric if, for every x, y ∈ X, if xRy and yRx then x = y

Question 16

Give the definition of a relation R on a set X being transitive

Answer 16

The relation R is transitive if, for every x, y, z ∈ X, if xRy and yRz then xRz

Question 17

Give the definition of an equivalence relation.

Answer 17

An equivalence relation is a relation which is reflexive, transitive, and symmetric.

Question 18

Let R be an equivalence relation on a set X. Give the definition of C ⊆ X being an equivalence
class

Answer 18

A subset C of X is an equivalence class if C is non-empty and, for any x ∈ C and any
y ∈ X, xRy if and only if y ∈ C

Question 19

Give the definition of a partial order.

Answer 19

A partial order is a relation which is reflexive, transitive, and anti-symmetric.

Question 20

Give the definition of a partially ordered set.

Answer 20

A partially ordered set is a pair (X, ⩽) where X is a set and ⩽ is a partial order on X

Question 21

Let (X, ⩽) be a partially ordered set. Give the definitions of two elements x, y ∈ X being comparable

Answer 21

The elements x and y are comparable if x ⩽ y or y ⩽ x

Question 22

Let (X, ⩽) be a partially ordered set. Give the definition of an element x ∈ X being minimal.

Answer 22

The element x is minimal if there is no element y ∈ X distinct from x such that y ⩽ x

Question 23

Give the definition of a relation R on a set X being irreflexive

Answer 23

The relation R is irreflexive if, for every x ∈ X, x ̸ R x

Question 24

Give the definition of a strict order.

Answer 24

A strict order is a relation which is irreflexive and transitive.

Question 25

Give the definition of a directed graph.

Answer 25

A directed graph is a pair (V, E) where V is a set whose elements are called vertices
and E is a subset of V × V whose elements are called directed edges