sentence that is always false is called a contradiction. For example, p ∧ ¬p is a contradiction.
In the following set of exercises, the symbol t denotes a tautology and the symbol c denotes a contradiction.
Exercises (1.4) Show that the following statements are tautologies. Traditional names for some of these tautologies are given in parentheses. There is no need to memorize these names.
1. ¬p ∧ p (Law of Excluded Middle)
2. p ⟶ (p ∧ q) (Addition)
3. (p ∧ q) ⟶ p (Simplification)
4. [p ∧ (p ⟶ q)] ⟶ q (Modus Ponens)
5. [¬q ∧ (p ⟶ q)] ⟶ ¬p (Modus Tollens)
6. (¬p ⟶ c) ⟶ p (Reductio ad Absurdum)
7. (p ⟶ q) ⟷ [(p ∧ ¬q) ⟶ c] (Reductio ad Absurdum)
8. ¬(p ∨ q) ⟷ (¬p ∧ ¬q) (De Morgan’s Law)
9. ¬(p ∧ q) ⟷ (¬p ∨ ¬q) (De Morgan’s Law)
10. c ⟶ p
11. p ⟶ t
12. (p ⟶ g) ⟷ (¬q ⟶ ¬p) (Contrapositive Law)
Sets. Loosely speaking, a set is a collection of objects. This is not a definition. The notion of a set is basic in mathematics, and the word set is not defined. (Since every concept must be defined in terms of concepts whose meaning is already known, some concepts must remain basic and undefined.) Objects which belong to a set are called elements of that set.
One way of specifying a set is to list its elements between set brackets.
Examples (1.3) The following are examples of sets.
1. {1, 3, 7, 9}
2. the set of positive even numbers {2, 4, 6, 8, . . . }
3. {{1, 2}, {1}}
Some well-known sets:
Ø: the empty set { }
The notation “a ∈ A” means that a is an element of the set A. We also say, “a is in A,” or “a belongs to A.” To say that a does not belong to A, we write “a ∉ A.”
Examples (1.4) The following statements are true.
3 ∉ Ø.
3 ∈
0 ∉
0 ∈
1.25 ∉
1.25 ∈
Remarks. We do not describe the sets
Quantifiers. Quantifiers are important mathematical tools. Using quantifiers, we can make our mathematical language precise. There are two principal quantifiers in mathematics: the universal and the existential.
Universal quantifier. The universal quantifier has the symbolic form ∀. To express the universal quantifier in English, we write “for all,” “for every,” or “for each.”
Examples (1.5) The following statements are equivalent.
1. (∀x ∈
2. For every x in
3. For every natural number x, the number x + 1 is also a natural number.
