Examination test from Discrete mathematics
4th term, 30/1/2017
Name and surname 1 2 3 4 5 Sum
16 points/task, 100 min.
1. Let X = {0, 1, 2} be a set and A ⊆ P(X) a system of its subsets. For each
of the formulas find a system which satisfies the formula and a system which
violates it. The later one denote as B. If there is no such A or B prove that.
a) (∃x ∈ X)(∀Y ∈ A)(x ∈ Y ).
b) (∀Y, Z ∈ A)(Y − Z ∈ A).
c) (∀x, y ∈ X)(∀Y ∈ A)((x = y ∧ x ∈ Y ) → y ∈ Y ).
d) (∀x ∈ X)(∀Y ∈ A)({x} ∪ Y ∈ A).
2. Construct some isotonne mapping f : (N, ≤) → (N, ≤) (or prove that it
does not exist) which does not have a fix-point (i.e. (∀x)f(x) = x) and is
a) injective (one-to-one),
b) surjective (onto).
3. Let ρ, σ be relations on set X. Prove that:
a) (ρ ∪ σ)−1
= ρ−1
∪ σ−1
,
b) (ρ ◦ σ)−1
= σ−1
◦ ρ−1
.
4. Find Hasse diagrams of all mutually non-isomorphic preordered sets with
four elements which do not have a greatest nor a smallest element.
5. a) Find some weight w : E → {1, 2} for the depicted graph G = (V, E)
such that there is exactly one minimal spanning tree.
• • •
• • •
b) Calculate a number of all such weights.