82 LOGIC AND PROPOSITIONAL CALCULUS [CHAP.

(b) The formal definition that L is the limit of a sequence a1 , a2 , . . . follows:

∀ ∈ > 0, ∃ n0 ∈ N, ∀n > n0 we have | an − L| < ∈

Thus L is not the limit of the sequence a1 , a2 , . . . when:

∃ ∈ > 0, ∀n0 ∈ N, ∃ n > n0 such that | an − L| ≥ ∈

Solved Problems

PROPOSITIONS AND TRUTH TABLES

4.1. Let p be “It is cold” and let q be “It is raining”. Give a simple verbal sentence which describes each of the
following statements: (a) ¬p; (b) p ∧ q; (c) p ∨ q; (d) q ∨ ¬p.
In each case, translate ∧, ∨, and ∼ to read “and,” “or,” and “It is false that” or “not,” respectively, and then simplify
the English sentence.

(a) It is not cold. (c) It is cold or it is raining.

(b) It is cold and raining. (d) It is raining or it is not cold.

4.2. Find the truth table of ¬p ∧ q.

Construct the truth table of ¬p ∧ q as in Fig. 4-9(a).

Fig. 4-9

4.3. Verify that the proposition p ∨ ¬(p ∧ q) is a tautology.

Construct the truth table of p ∨ ¬(p ∧ q) as shown in Fig. 4-9(b). Since the truth value of p ∨ ¬(p ∧ q) is T for
all values of p and q, the proposition is a tautology.

4.4. Show that the propositions ¬(p ∧ q) and ¬p ∨ ¬q are logically equivalent.
Construct the truth tables for ¬(p ∧ q) and ¬p ∨ ¬q as in Fig. 4-10. Since the truth tables are the same (both
propositions are false in the first case and true in the other three cases), the propositions ¬(p ∧ q) and ¬p ∨ ¬q are
logically equivalent and we can write
¬(p ∧ q) ≡ ¬p ∨ ¬q.

Fig. 4-10
CHAP. 4] LOGIC AND PROPOSITIONAL CALCULUS 83

4.5. Use the laws in Table 4-1 to show that ¬(p ∧ q) ∨ (¬p ∧ q) ≡ ¬p.
Statement Reason
(1) ¬(p ∨ q) ∨ (¬p ∧ q) ≡ (¬p ∧ ¬q) ∨ (¬p ∧ q) DeMorgan’s law
(2) ≡ ¬p ∧ (¬q ∨ q) Distributive law
(3) ≡ ¬p ∧ T Complement law
(4) ≡ ¬p Identity law

CONDITIONAL STATEMENTS
4.6. Rewrite the following statements without using the conditional:

(a) If it is cold, he wears a hat.

(b) If productivity increases, then wages rise.
Recall that “If p then q” is equivalent to “Not p or q;” that is, p → q ≡ ¬p ∨ q. Hence,
(a) It is not cold or he wears a hat.
(b) Productivity does not increase or wages rise.

4.7. Consider the conditional proposition p → q. The simple propositions q → p, ¬p → ¬q and ¬q → ¬p

are called, respectively, the converse, inverse, and contrapositive of the conditional p → q. Which if any
of these propositions are logically equivalent to p → q?
Construct their truth tables as in Fig. 4-11. Only the contrapositive ¬q → ¬p is logically equivalent to the original
conditional proposition p → q.

Fig. 4-11

4.8. Determine the contrapositive of each statement:

(a) If Erik is a poet, then he is poor.

(b) Only if Marc studies will he pass the test.
(a) The contrapositive of p → q is ¬q → ¬p. Hence the contrapositive follows:

If Erik is not poor, then he is not a poet.

(b) The statement is equivalent to: “If Marc passes the test, then he studied.” Thus its contrapositive is:
If Marc does not study, then he will not pass the test.

4.9. Write the negation of each statement as simply as possible:

(a) If she works, she will earn money.

(b) He swims if and only if the water is warm.
(c) If it snows, then they do not drive the car.
(a) Note that ¬(p → q) ≡ p ∧ ¬q; hence the negation of the statement is:

She works or she will not earn money.

84 LOGIC AND PROPOSITIONAL CALCULUS [CHAP. 4

(b) Note that ¬(p ↔ q) ≡ p ↔ ¬q ≡ ¬p ↔ q ; hence the negation of the statement is either of the following:

He swims if and only if the water is not warm.

He does not swim if and only if the water is warm.

(c) Note that ¬(p → ¬q) ≡ p ∧ ¬¬q ≡ p ∧ q. Hence the negation of the statement is:

It snows and they drive the car.

ARGUMENTS
4.10. Show that the following argument is a fallacy: p → q, ¬ p $ ¬q.
Construct the truth table for [(p → q)∧¬p] → ¬q as in Fig. 4-12. Since the proposition [(p → q)∧¬p] → ¬q
is not a tautology, the argument is a fallacy. Equivalently, the argument is a fallacy since in the third line of the truth
table p → q and ¬p are true but ¬q is false.

Fig. 4-12

4.11. Determine the validity of the following argument: p → q, ¬ p $ ¬p.

Construct the truth table for [(p → q)∧¬q] → ¬p as in Fig. 4-13. Since the proposition [(p → q)∧¬q] → ¬p
is a tautology, the argument is valid.

Fig. 4-13

4.12. Prove the following argument is valid: p → ¬q, r → q, r $ ¬p.

Construct the truth table of the premises and conclusions as in Fig. 4-14(a). Now, p → ¬q, r → q, and r are
true simultaneously only in the fifth row of the table, where ¬p is also true. Hence the argument is valid.

Fig. 4-14
CHAP. 4] LOGIC AND PROPOSITIONAL CALCULUS 85

4.13. Determine the validity of the following argument:

If 7 is less than 4, then 7 is not a prime number.
7 is not less than 4.

7 is a prime number.
First translate the argument into symbolic form. Let p be “7 is less than 4” and q be “7 is a prime number.” Then
the argument is of the form
p → ¬q, ¬q $ q
Now, we construct a truth table as shown in Fig. 4-14(b). The above argument is shown to be a fallacy since, in the
fourth line of the truth table, the premises p → ¬q and ¬p are true, but the conclusion q is false.
Remark: The fact that the conclusion of the argument happens to be a true statement is irrelevant to the fact that the
argument presented is a fallacy.

4.14. Test the validity of the following argument:

If two sides of a triangle are equal, then the opposite angles are equal.
Two sides of a triangle are not equal.

The opposite angles are not equal.

First translate the argument into the symbolic form p → q, ¬p $ ¬q, where p is “Two sides of a triangle are
equal” and q is “The opposite angles are equal.” By Problem 4.10, this argument is a fallacy.
Remark: Although the conclusion does follow from the second premise and axioms of Euclidean geometry, the above
argument does not constitute such a proof since the argument is a fallacy.

QUANTIFIERS AND PROPOSITIONAL FUNCTIONS

4.15. Let A = {1, 2, 3, 4, 5}. Determine the truth value of each of the following statements:

(a) (∃x ∈ A)(x + 3 = 10) (c) (∃x ∈ A)(x + 3 < 5)

(b) (∀x ∈ A)(x + 3 < 10) (d) (∀x ∈ A)(x + 3 ≤ 7)

(a) False. For no number in A is a solution to x + 3 = 10.

(b) True. For every number in A satisfies x + 3 < 10.
(c) True. For if x0 = 1, then x0 + 3 < 5, i.e., 1 is a solution.
(d) False. For if x0 = 5, then x0 + 3 is not less than or equal 7. In other words, 5 is not a solution to the given
condition.

4.16. Determine the truth value of each of the following statements where U = {1, 2, 3} is the universal set:
(a) ∃x∀y, x 2 < y + 1; (b) ∀x∃y, x 2 + y 2 < 12; (c) ∀x∀y, x 2 + y 2 < 12.
(a) True. For if x = 1, then 1, 2, and 3 are all solutions to 1 < y + 1.
(b) True. For each x0 , let y = 1; then x02 + 1 < 12 is a true statement.
(c) False. For if x0 = 2 and y0 = 3, then x02 + y02 < 12 is not a true statement.

4.17. Negate each of the following statements:

(a) ∃x ∀y, p(x, y); (b) ∃x ∀y, p(x, y); (c) ∃y ∃x ∀z, p(x, y, z).

Use ¬∀x p(x) ≡ ∃x¬p(x) and ¬∃x p(x) ≡ ∀x¬p(x):

(a) ¬(∃x∀y, p(x, y)) ≡ ∀x∃y¬p(x, y)

(b) ¬(∀x∀y, p(x, y)) ≡ ∃x∃y¬p(x, y)
(c) ¬(∃y ∃x ∀z, p(x, y, z)) ≡ ∀y ∀x ∃z¬p(x, y, z)
86 LOGIC AND PROPOSITIONAL CALCULUS [CHAP. 4

4.18. Let p(x) denote the sentence “x + 2 > 5.” State whether or not p(x) is a propositional function on each
of the following sets: (a) N, the set of positive integers; (b) M = {−1, −2, −3, . . .};
(c) C, the set of complex numbers.

(a) Yes.
(b) Although p(x) is false for every element in M, p(x) is still a propositional function on M.
(c) No. Note that 2i + 2 > 5 does not have any meaning. In other words, inequalities are not defined for complex
numbers.

4.19. Negate each of the following statements: (a) All students live in the dormitories. (b) All mathematics
majors are males. (c) Some students are 25 years old or older.
Use Theorem 4.4 to negate the quantifiers.

(a) At least one student does not live in the dormitories. (Some students do not live in the dormitories.)
(b) At least one mathematics major is female. (Some mathematics majors are female.)
(c) None of the students is 25 years old or older. (All the students are under 25.)

Supplementary Problems

PROPOSITIONS AND TRUTH TABLES

4.20. Let p denote “He is rich” and let q denote “He is happy.” Write each statement in symbolic form using p and q. Note
that “He is poor” and “He is unhappy” are equivalent to ¬p and ¬q, respectively.

(a) If he is rich, then he is unhappy. (c) It is necessary to be poor in order to be happy.

(b) He is neither rich nor happy. (d) To be poor is to be unhappy.

4.21. Find the truth tables for. (a) p ∨ ¬q; (b) ¬p ∧ ¬q.
4.22. Verify that the proposition (p ∧ q) ∧ ¬(p ∨ q) is a contradiction.

ARGUMENTS
4.23. Test the validity of each argument:
(a) If it rains, Erik will be sick. (b) If it rains, Erik will be sick.
It did not rain. Erik was not sick.

Erik was not sick. It did not rain.

4.24. Test the validity of the following argument:
If I study, then I will not fail mathematics.
If I do not play basketball, then I will study.
But I failed mathematics.

Therefore I must have played basketball.

QUANTIFIERS
4.25. Let A = {1, 2, . . . , 9, 10}. Consider each of the following sentences. If it is a statement, then determine its truth value.
If it is a propositional function, determine its truth set.
(a) (∀x ∈ A)(∃y ∈ A)(x + y < 14) (c) (∀x ∈ A)(∀y ∈ A)(x + y < 14)
(b) (∀y ∈ A)(x + y < 14) (d) (∃y ∈ A)(x + y < 14)