The tables above show that ¬(p ⟶ q) is logically equivalent to p ∧ ¬q.
Exercises (1.2)
1. Show that p ⟶ q is logically equivalent to ¬p ∨ q.
2. Show that ¬(p ∧ q) is logically equivalent to ¬p ∨ ¬q.
3. Show that p ⟶ q is logically equivalent to ¬q ⟶ ¬p.
4. Classify each of the following propositions as true or false.
(a) If 5 + 2 = 8, then
(b) If 5 + 2 = 8, then
(c) If 5 + 2 = 7, then
(d) If 5 + 2 = 7, then
Remark. Although most people initially find the truth-table definition of p ⟶ q peculiar, this does not result in confusion in practice. It may seem odd that we classify as true such statements as, “If 2 + 3 = 6 then 2 + 3 = 5,” but, since we really never use such statements in proving theorems, no confusion arises.
(e) if and only if (⟷)
p ⟷ q means each of the following:
p if and only if q.
p is logically equivalent to q.
(p ⟶ q) ∧ (q ⟶ p)
p and q are either both true or both false.
p is a necessary and sufficient condition for q.
q is a necessary and sufficient condition for p.
p implies q, and q implies p.
(p ⟶ q) ∧ (¬p ⟶ ¬q)
Exercises (1.3)
1. Let the symbol # represent “the exclusive or.” That is, p # q means: p or q but not both. Write a truth table defining p # q.
2. Use truth tables to show that the following propositions are equivalent:
(a) p ⟷ q
(b) (p ⟶ q) ∧ (q ⟶ p)
(c) (p ⟶ q) ∧ (¬p ⟶ ¬p)
Tautologies and contradictions. A sentence that is always true is called a tautology. For example, p ∨ ¬p is a tautology.
A 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 ∉