As usual, let’s start with the definitions.
Definition: “The compound propositions p and q are called logically equivalent if p ↔ q is a tautology. The notation p ≡ q denotes that p and q are logically equivalent.”
Notice that if p ↔q is a tautology, p and q have the same truth values.
Definition: “A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.”
Definition: “A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A.”
Definition: “A relation R on a set A is called symmetric if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A.”
Definition: “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.”
The definitions above are from the textbook “Discrete Mathematics and its applications” By Rosen.
So, let’s now solve the exercise.
Reflexive: p has the same truth values as p. Therefore, the relation is reflexive.
Symmetric: if p has the same truth values as q, then q has the same truth values as p. In other words, if p and q are related by ↔, then q and p are also related by ↔. Therefore, the relation is symmetric.
Transitive: If p and q have the same truth values, and q and r have the same truth values, then p and r have the same truth values. Therefore, the relation is transitive.
The relation ↔ is an equivalence relation because is reflexive, symmetric, and transitive.
What are the equivalence classes of F and of T?
The equivalence class of T is the set of all tautologies.
The equivalence class of F is the set of all contradictions.
Related exercises:
- Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack
- Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if a + d = b + c. Show that R is an equivalence relation
- Suppose that A is a nonempty set, and f is a function that has A as its domain. Let R be the relation on A consisting of all ordered pairs (x, y) such that f (x) = f (y)
- Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack.
