Description

CS 113 Discrete Mathematics
DM Course Staff
Definitions
Let A and B be sets. A binary relation from A to B is a subset of A × B
Relation on a set is a relation from A to A
A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A
Reflexive in predicate logic: ∀a((a,a) ∈ R)
A relation R on a set A is called symmetric if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A.
Symmetric in predicate logic: ∀a,∀b,((a,b) ∈ R =⇒ (b,a) ∈ R)
A relation R on a set A such that for all a,b ∈ A, if (a,b) ∈ R and (b,a) ∈ R then a = b is called anti-symmetric.
Anti-symmetric in predicate logic: ∀a,∀b,(((a,b) ∈ R ∧ (b,a) ∈ R) =⇒ (a = b)
A relation R on a set A is called transitive if whenever (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R for all a,b,c ∈ A.
Transitive in predicate logic: ∀a,∀b,∀c(((a,b) ∈ R ∧ (b,c) ∈ R) =⇒ (a,c) ∈ R
Advice from the book
This section gives the basic terminology, especially the important notions of reflexivity, symmetry, anti-symmetry, and transitivity. If we are given a relation as a set of ordered pairs, then
reflexivity is easy to check for: we make sure that each element is related to itself. Symmetry is
also fairly easy to test for: we make sure that no pair (a,b) is in the relation without its opposite
(b,a) being present as well. To check for anti-symmetry we make sure that no pair (a,b) with a ̸= b and its opposite are both in the relation. In other words, at most one of (a,b) and (b,a) is in the relation if a ̸= b. Transitivity is much harder to verify, since there are many triples of
elements to check. A common mistake to try to avoid is forgetting that a transitive relation that has pairs (a,b) and (b,a) must also include (a,a) and (b,b).
Questions
1. Those that don’t break their morals, are true to themselves. Only those with morals can break them. Those that are true to themselves can be trusted. Therefore the person who has no
1
morals can be trusted. Write and justify this argument in predicate logic. (Hint: use vacuous proof)
2. For each of these relations on the set {1,2,3,4}, decide whether it is reflexive, whether it is symmetric, whether it is anti-symmetric and whether it is transitive.
1. {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}
2. {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}
3. {(2,4),(4,2)}
4. {(1,2),(2,3),(3,4)}
5. {(1,1),(2,2),(3,3),(4,4)}
6. {(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)}
3. Prove that x2 + y2 ≥ 2xy for all real numbers x and y using backward reasoning.
4. (Recognize whether several important relations are reflexive or not over their respective domain.) Which of the following statements are True and which are False?
1. ∀x ∈ R(x = x)
2. ∀x ∈ R(x ̸= x). 3. ∀x ∈ R(x < x).
4. ∀x ∈ R(x ≥ x).
5. ∀a ∈ N(a | a)
6. ∀X ∈ 2U(X ⊆ X) where U is the universal set.
5. Draw the directed graph that represents the relation {(a,a),(a,b),(b,c),(c,b),(c,d),(d,a),(d,b)}
6. (Be able to describe the relations determined by Boolean operations.) Describe these relations over the set of Boolean variables.
1. p ∧ q = True
2. p ∧ q = False
3. p =⇒ q = True
4. p =⇒ q = False
5. p ≡ q = True
7. Is the “divides” relation on the set of positive integers symmetric? Is it antisymmetric?
8. How many reflexive relations are there on a set with n elements?
9. Let A be the set {1,2,3,4}. Which ordered pairs are in the relation R = {(a,b) | a divides b}?
10. Show that if a, b, and c are real numbers and a ̸= 0, then there is a unique solution of the equation ax + b = c.
11. Prove that between every two rational numbers there is an irrational number.
Hint: use the fact that is irrational and 0 1, and an irrational number added or multiplied with a rational number is still an irrational number.
12. For each of the following digraphs, list down the ordered pairs and determine whether the relations represented by the digraphs are reflexive, irreflexive, symmetric, antisymmetric, and/or transitive.
(a) (b)
(c)
(d)
(e)
(f)