|
|
Discrete Mathematics Lecture Notes - Week 1
1 The Foundations: Logic and Proof
1.1 Propositional Logic
The rules of logic specify the precise meaning of mathematical statements. These rules are used to distinguish between valid and invalid mathematical arguments. In addition to its importance in understanding mathematical reasoning, logic has numerous applications in computer science. The rules of logic are used in the design of computer circuits, the con- struction of computer programs, the verification of correctness of programs, and in many other ways.
Our discussion begins with an introduction to the basic building blocks of logic proposi- tions.
Propositions
A proposition is a declerative sentence that is either true or false, but not both.
Example 1.1 The followings are propositions:
1. Ankara is the capital of Turkey.
2. 2 < 4
3. 4 = 7
4. 2+2 = 3
Propositions 1 and 2 are true, whereas 3 and 4 are false.
Example 1.2 The following are not propositions:
1. What is your name? (This is a question.)
2. Do your homework! (This is a command.)
3. x is an even number. (Depends on what x represents.
4. Everybody on this Earth is a liar! (Think about this one!)
Letters are used to denote propositions. The conventional letters used for this purpose are
p, q, r, s, . . . .
The truth value of a proposition is true denoted by T , if it is a true proposition, and false, denoted by F if it is a false proposition.
Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions us- ing logical operators.
Definition 1.1 Let p be a proposition. The statement
’it is not the case that p’
is another proposition, called the negation of p. The negation of p is denoted by ¬p, and it is read ’not p’.
Example 1.3 Find the negation of the proposition
’Today is Friday.’
Solution:
The negation is or more simply
’It is not the case that today is Friday.’
’Today is not Friday.’
Table 1: The Truth Table for the Negation of a Proposition
| p | ¬p |
| T | F |
| F | T |
The truth or falsehood of a proposition is called its truth value. A truth table displays the
relationships between the truth values of propositions.
Connectives are used for making compound propositions, i.e., connectives are the logical operators that are used to form new propositions from two or more existing propositions.
Definition 1.2 Let p and q be propositions. The proposition ’p and q’, denoted by p ∧ q, is true when both p and q are true, and is false otherwise. The proposition p ∧ q is called the conjunction of p and q.
Table 2: The Truth Table for the Conjunction of Two Propositions
| p q | p ∧ q |
| T T | T |
| T F | F |
| F T | F |
| F F | F |
Example 1.4 Find the conjunction of the propositions p and q where p is the proposition
’Today is Friday’ and q is the proposition ’It is raining today’.
p ∧ q: ’Today is Friday and it is raining today’.
Table 3: The Truth Table for the Disjunction of Two Propositions
| p q | p ∨ q |
| T T | T |
| T F | T |
| F T | T |
| F F | F |
Definition 1.3 Let p and q be propositions. The proposition ’p or q’, denoted by p ∨ q, is the
propostion that is false when both p and q are false, and is true otherwise. The proposition
p ∨ q is called the disjunction of p and q.
Example 1.5 Find the disjunction of the propositions p and q where p is the proposition
’Today is Friday’ and q is the proposition ’It is raining today’.
p ∨ q: ’Today is Friday or it is raining today’.
Definition 1.4 Let p and q be propositions. The exclusive or ’p and q’, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true, and is false otherwise.
Table 4: The Truth Table for the Exclusive Or of Two Propositions
| p q | p ⊕ q |
| T T | F |
| T F | T |
| F T | T |
| F F | F |
Definition 1.5 Let p and q be propositions. The implication ’p → q’ is the propostion that
is false when p is true and q is false, and true otherwise. In this implication p is called the
hypothesis and q is called the conclusion.
A wide variety of terminology is used to express p → q. Some of the most common ways of expressing this implication are:
• ’if p then q’
• ’p implies q’
• ’if p, q’
• ’q is necessary for p’
• ’q whenever p’
Unfortunately, the if-then construction used in many programming languages is different from that used in logic. Most programming languages contain statements such as if p then S, where p is a proposition and S is a program segment. When execution of a program encounters such a statement, S is executed if p is true, whereas S is not executed if p is false.
Example 1.6 What is the value of the variable x after the statement if 2 + 2 = 4 then x := x + 1
if x = 0 before the statement is encountered?
(:= stands for assignment. The statement x := x + 1 represents the assignment of the value
x + 1 to x.)
Solution: Since 2 + 2 = 4 is true, the assignment statement x := x + 1 is executed. Hence,
x has the value 0 + 1 = 1 after this statement is encountered.
Definition 1.6 Let p and q be propositions. The biconditional ’p ↔ q’ is the propostion that is true when p and q have the same truth values and is false otherwise. The biconditional p ↔ q is the proposition that is true precisely when both the implications p → q and q → p are true. Because of this, the terminology ’p if and only if q’ is used for the biconditional.
Name Represented Meaning Negation Conjunction Disjunction Exclusive or Implication Biconditional ¬p p ∧ q p ∨ q p ⊕ p p → q p ↔ q ’not p’ ’p and q’ ’p or q (or both)’ ’either p or q but not both’ ’if p then q’ ’p if and only if q’
Table 5: SUMMARY
p q ¬p p ∧ q p ∨ q p ⊕ q p → q p ↔ q T T F F T F T F F F T T T F F F T T T F F T T F T F T T T F F T
Table 6: Truth Table
Logic and Bit Operations
Computer bit operations correspond to the logical connectives. By replacing true by a 1(one)
and false by a 0(zero) for operators ∧, ∨, and ⊕, we obtain the following tables:
∨ 0 1
0 0 1
1 1 1
Definition 1.7 A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string.
Example 1.7 101010011 is a bit string of length nine.
We will use the notation OR, AN D, and X OR for the operators ∧, ∨, and ⊕, as is done in various programming languages.
Example 1.8 Find the bitwise OR, bitwise AN D, and bitwise X OR of the bit strings
0110110110 and 1100011101.
Solution:
0110110110
1100011101
1110111111 bitwise OR
0100010100 bitwise AN D
1010101011 bitwise X OR
1.2 Propositional Equivalences:
Tautology, Contradiction, Contingency
Definition 1.8 (i) A proposition is said to be a tautology if its truth value is T for any assignment of truth values to its components.
(ii) A proposition is said to be a contradiction if its truth value is F for any assignment of truth values to its components.
(iii) A proposition that is neither a tautology nor a contradiction is called a contingency.
Example 1.9 (i) The proposition p ∨ ¬p is a tautology. (ii) The proposition p ∧ ¬p is a contradiction.
Logical Equivalences
Definition 1.9 The propositions p and q are called logically equivalent if p ↔ q is a tautol- ogy. The notation p ⇔ q denotes that p and q are logically equivalent.
Remark 1 When two compound propositions have the same truth values no matter what truth value their constituent propositions have, they are called logically equivalent.
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | ¬p ∧ ¬q |
| T T F F | T F T F | T T T F | F F F T | F F T T | F T F T | F F F T |
Example 1.10 (De Morgan’s Law) Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equiv-
alent.
Solution: The truth values of the propositions ¬(p ∨ q) and ¬p ∧ ¬q agree for all possible combinations of the truth values of p and q.
Example 1.11 Show that p → q and ¬p ∨ q are logically equivalent.
Solution: Again this can be check via the truth table.
| p | q | ¬p | ¬p ∨ q) | p → q |
| T T F F | T F T F | F F T T | T F T T | T F T T |
Table 7: Logical Equivalences
| Equivalence | Name |
| p ∧ T ⇔ p p ∨ F ⇔ p | Identity Laws |
| p ∨ T ⇔ T p ∧ F ⇔ F | Domination Laws |
| p ∨ p ⇔ p p ∧ p ⇔ p | Idempotent Laws |
| ¬(¬p) ⇔ p | Double Negation Law |
| p ∨ q ⇔ q ∨ p p ∧ q ⇔ q ∧ p | Commutative Laws |
| (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r) | Associative Laws |
| p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) | Associative Laws |
| ¬(p ∧ q) ⇔ ¬p ∨ ¬q ¬(p ∨ q) ⇔ ¬p ∧ ¬q | De Morgan’s Laws |
Example 1.12 Show that (p ∧ q) → (p ∨ q) is a tautology.
Solution: To show that this statement is a tautology, we will use logical equivalences to
demonstrate that it is logically equivalent to T . (Note that this could also be done via a truth table.)
(p ∧ q) → (p ∨ q) ⇔ ¬(p ∧ q) ∨ (p ∨ q) by Example 1.11
⇔ (¬p ∨ ¬q) ∨ (p ∨ q) by De Morgan’s Law
⇔ (¬p ∨ p) ∨ (¬q ∨ q) by Associative and Commutative Law
⇔ T ∨ T by Example 1.9 and Commutative Law
⇔ T
1.3 Predicates and Quantifiers
A predicate or propositional function is a statement containing variables. For instance,
’x + 2 = 7’, ’p is a prime number’, ’x is greater than 3’ are predicates.
The truth value of a predicate depends on the value assigned to its variables. For instance, if we replace x with 1 in the predicate ’x + 2 = 7’, we obtain ’1 + 2 = 7’, which is false. But, if we replace x with 5 in the predicate ’x + 2 = 7’, we obtain ’5 + 2 = 7’, which is true.
We represent a predicate by a letter followed by the variables enclosed between paranthesis:
P (x), Q(x, y), etc.
Example 1.13 Let P (x) denote the statement ’x > 3’. What are the truth values of P (4)
and P (2)?
Solution: P (4) is the statement ’4 > 3’ and it is true. However, P (2) is the statement
’2 > 3’, and it is false.
Example 1.14 Let Q(x, y) denote the statement ’x = y + 3’. What are the truth values of the propositions Q(1, 2) and Q(3, 0)? Solution: Q(1, 2) is the statement ’1 = 2 + 3’ and it is false. However, Q(3, 0) is the statement ’3 = 0 + 3’ and it is true.
Quantifiers
When all the variables in a propositional function are assigned values, the resulting state- ment has a truth value. However, there is another important way to change propositional functions into propositions, called quantification.
Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the universe of discourse.
Definition 1.10 The universal quantification of P (x) is the proposition ’P (x) is true for all values of x in the universe of discourse’. The notation ∀x P (x) denotes the universal quantification of P (x). ∀x P (x) is also expressed as ’for all x P (x)’ or ’for every x P (x)’.
Example 1.15 Let P (x) be the statement ’x + 1 > x’. What is the truth value of the quantification ∀x P (x), where the universe of discourse is the set of real numbers?
Solution: Since P (x) is true for all real numbers x, the quantification ∀x P (x) is true.
Example 1.16 What is the truth value of ∀x P (x), where P (x) is the statement ’x2 < 10’, and the universe of discourse consists of positive integers not exceeding 4?
Solution: The statement ∀xP (x) is the same as the conjunction P (1) ∧ P (2) ∧ P (3) ∧ P (4) since the universe of discourse consists of the integers 1, 2, 3, 4. Since P (4) which is the statement ’42 < 10’, is false, it follows that ∀x P (x) is false.
Definition 1.11 The existential quantification of P (x) is the proposition ’There exists an element x in the universe of discourse such that P (x) is true’. We use the notation ∃x P (x) and is expressed as ’There is an x such that P (x)’, or ’There is at least one x such that P (x)’.
Example 1.17 Let P (x) be the statement ’x > 3’. What is the truth value of the quantifi- cation ∃x P (x), where the universe of discourse is the set of real numbers?
Solution: Since P (x) is true, for instance when x = 4, the quantification ∃x P (x) is true.
1.4 Nested Quantifiers
In predicates with more than one variable it possible to use several quantifiers at the same time, for instance ∀x∀y∃z P (x, y, z), meaning ’for all x and all y there is some z such that P (x, y, z)’. Note that in general the existential and universal quantifiers cannot be swapped, i.e. in general ∀x∃y P (x, y) means something different from ∃y∀x P (x, y).
Example 1.18 Let Q(x, y) denote ’x + y = 0’. What are the truth values of the quantifi- cations ∃y∀x Q(x, y) and ∀x∃y Q(x, y)?
Solution: The quantification
∃y∀x Q(x, y) denotes the proposition
’There is a real number y such that for every real number x, Q(x, y) is true.’
No matter what value of y is chosen, there is only one value of x for which x + y = 0. Since there is no real number y such that x + y = 0 for all real numbers x, the statement
∃y∀x Q(x, y) is false.
The quantification
∀x∃y Q(x, y) denotes the proposition
’For every real number x there is a real number y, Q(x, y) is true.’
Given a real number x, there is a real number y such that x + y = 0; namely y = −x. Hence the statement ∀x∃y Q(x, y) is true.
Generalized De Morgan Laws for Logic
If ∃x P (x) is false then there is no value of x for which P (x) is true, i.e. P(x) is always false.
Hence,
¬∃x P (x) ⇔ ∀x ¬P (x)
On the other hand, if ∀xP (x) is false then it it not true that for every x, P (x) holds, hence for some x, P (x) must be false. Thus,
Section 1.1
1. Write the following compound propositions in good English, using the following:
v: “I take a vacation”
s: “it is summer”
w: “I work”
(a) s → v (b) s → ¬w (c) w ⊕ v
2. Write the following compound propositions in symbols, using the following:
v: “I take a vacation”
s: “it is summer”
w: “I work”
(a) I take a vacation only if it is summer.
(b) When it is summer I take a vacation, but when it is not summer I work. (c) I work and take a vacation every summer.
3. (1.1.27) Construct a truth table for each of these compound propositions:
(a) p ∧ ¬p
(b) p ∨ ¬p
(c) (p ∨ ¬q → q)
(d) (p → q) → (q → p)
4. (1.1.31) Construct a truth table for each of these compound propositions:
(a) p → ¬q
(b) ¬p ↔ q
(c) (p → q) ∨ (¬p → q) (d) (p → q) ∧ (¬p → q)
5. (1.1.37) Find the bitwise OR, bitwise AND, and bitwise XOR of each of the following bit strings.
(a) 1011110,0100001 (b) 11110000,10101010
Section 1.2
6. (1.2.5) Use the truth table to verify the distributive law
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
7. (1.2.15) Determine whether (¬q ∧ (p → q)) → ¬p is a tautology.
8. (1.2.17) Show that ¬(p ↔ q) and p ↔ ¬q are logically equivalent.
Section 1.3
9. (1.3.5) Let P (x) be the statement ’x spends more than five hours every weekday in class,’ where the domain for x consists of all students. Express each of these quantifi- cations in English.
(a) ∃x P (x) (b) ∀x P (x) (c) ∃x ¬P (x) (d) ∀x ¬P (x)
10. Write the following statements in good English. Use the following variables and pred-
x: people
icates:
y: stores
S(x, y): “x shops in y”
T (x): “x is a student”
(a) ∀y S(M argaret, y)
(b) ∃y ∀x S(x, y) (c) ∀x ∃y S(x, y)
(d) ∃y ∀x [T (x) → ¬S(x, y)] (e) ∀y ∃x [T (x) ∧ S(x, y)]
11. (1.3.17) Suppose that the domain of the propositional function P (x) consists of in- tegers {0, 1, 2, 3, 4}. Write out each of the following propositions using disjunctions, conjunctions and negations.
(a) ∃x P (x) (b) ∀x P (x) (c) ∃x ¬P (x)
(d) ∀x ¬P (x) (e) ¬∃x P (x) (f ) ¬∀x P (x)
Section 1.5
1. (1.5.3) What rule of inference is used in each of these arguments?
(a) Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science major.
(b) Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics major.
(c) If it is rainy, then the pool will be closed. It is rainy, and therefore the pool is closed.
(d) If it snows today, the university will close. The university is not closed today.
Therefore, it did not snow today.
(e) If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I will sunburn. Therefore, if I go swimming, then I will sunburn.
Solution:
(a) Addition.
(b) Simplification. (c) Modus ponens. (d) Modus tollens.
(e) Hypothetical syllogism.
2. (1.5.15) For each of these arguments determine whether the argument is correct or incorrect and explain why.
(a) All students in this class understand logic. Xavier is a student in this class, there- fore Xavier understands logic.
(b) Every computer science major takes discrete mathematics. Natasha is taking dis- crete mathematics. Therefore, Natasha is a computer science major.
(c) All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit.
(d) Everyone who eats granola every day is healthy. Linda is not healthy. Therefore, Linda does not eat granola everyday.
Solution:
(a) Correct, using universal instantiation and modus ponens. (b) Invaild; fallacy of affirming the conclusion.
(c) Invaild; fallacy of denying the hypothesis.
(d) Correct, using universal instantiation and the hypothesis.
3. (1.5.27) Use the rules of inference to show that if ∀x (P (x) → Q(x) ∧ S(x)) and
∀x (P (x) ∧ R(x)) are true, then ∀x (R(x) ∧ S(x)) is true.
Solution:
Step Reason
1. ∀x (P (x) ∧ R(x)) Premise
2. P (a) ∧ R(a)) Universal instantiation from (1)
3. P (a) Simplification from (2)
4. ∀x (P (x) → Q(x) ∧ S(x)) Premise
5. Q(a) ∧ S(a)) Universal modus ponens from (3) and (4)
6. S(a) Simplification from (5)
7. R(a) Simplification from (2)
8. R(a) ∧ S(a) Conjunction from (7) and (8)
9. ∀x (R(x) ∧ S(x)) Universal generalization from (8)
4. (1.5.29) Use the rules of inference to show that if ∀x (P (x) ∨ Q(x)), ∀x (¬Q(x) ∨ S(x)),
∀x (R(x) → ¬S(x)), ∃x ¬P (x) are true, then ∃x ¬R(x) is true.
Solution:
Step Reason
1. ∃x ¬P (x) Premise
2. ¬P (c) Existential instantiation from (1)
3.∀x (P (x) ∨ Q(x)) Premise
4. P (c) ∨ Q(c) Universal instantiation from (3)
5. Q(c) Disjunctive syllogism from (4) and (2)
6. ∀x (¬Q(x) ∨ S(x)) Premise
7. ¬Q(c) ∨ S(c) Universal instantiation from (6)
8. S(c) Disjunctive syllogism from (5) and (7)
9. ∀x (R(x) → ¬S(x)) Premise
10. R(c) → ¬S(c) Universal instantiation from (9)
11. ¬R(c) Modus tollens from (8) and (10)
12. ∃x ¬R(x) Existential generalization from (11)
Section 1.6
5. (1.6.1) Use a direct proof to show that sum of two odd integers is even.
Solution:
Let n = 2k + 1, and m = 2l + 1 be odd integers. Then n + m = 2(k + l + 1) is even.
6. Using the definitions of even and odd integer, give a direct proof that the following statement is true for all integers n:
if n is odd, then 5n + 3 is even.
Solution: Suppose n is odd.
Therefore n = 2k + 1 for some integer k.
Therefore 5n + 3 = 5(2k + 1) + 3 = 10k + 8 = 2(5k + 4). Therefore 5n + 3 is even. (5n + 3 is an integer multiple of 2)
7. (1.6.17) Show that if n is an integer and n3 + 5 is odd, then n is even using
(a) a proof by contraposition. (b) a proof by contradiction.
Solution:
(a) Assume that n is odd, so n = 2k + 1 for some integer k. Then n3 + 5 = 2(4k3 +
6k2 + 3k + 3. Because n3 + 5 is two times some integer, it is even.
(b) Suppose that n3 + 5 is odd and n is odd. Because n is odd and the product of two odd numbers is odd, it follows that n2 is odd, and then n3 is odd. But then
5 = (n3 + 5) − n3 would have to be even because it is difference of two odd integers. Therefore the supposition n3 + 5 and n are both odd is wrong.
8. Using the definitions of even and odd integer, give an indirect proof that the following statement is true for all integers n:
if n is odd, then 5n + 3 is even.
Solution: Suppose 5n + 3 is not even. Therefore 5n + 3 is odd.
Therefore 5n + 3 = 2k + 1 for some integer k. Therefore 5n = 2k − 2 = 2(k − 1).
2(k − 1)
Therefore n = .
5
Since n =
2(k − 1)
5
is an integer and 2 is not divisible by the prime 5, 5 is a divisor of
k − 1.
Therefore n is even (it is equal to 2 times the integer
k − 1 ).
5
9. (1.6.27) Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.
Solution:
First, assume that n is odd, so that n = 2k + 1 for some integer k. Then 5n + 6 =
5(2k + 1) + 6 = 10k + 11 = 2(5k + 5) + 1. Hence, 5n + 6 is odd. To prove the converse, suppose that n is even, so that n = 2k for some integer k. Then 5n + 6 = 5(2k) + 6 =
10k + 6 = 2(5k + 3). Hence, 5n + 6 is even. Hence, n is odd if and only if 5n + 6 is odd.
10. (Adapted from Problem A4 from the 1988 William Lowell Putnam Mathematics Com- petition.)
(a) Suppose that every point of the plane is painted one of two colors (A or B). Must there be two points of the same color that are exactly 1 inch apart?
(b) Suppose that every point of the plane is painted one of three colors (A, B, or C ).
Must there be two points of the same color that are exactly 1 inch apart? (c) What if nine colors are allowed?
Solution:
?(a) There must be two points of the same color that are exactly 1 inch apart. Take an equilateral triangle with each of its sides 1 inch long. Of the three vertices of the triangle, at least two (say x and y) must have the same color. Therefore x and y have the same color and are 1 inch apart.
(b) There must be two points of the same color that are exactly 1 inch apart. We give a proof by contradiction. Suppose it is possible to color every point of the plane such that no two points that are 1 inch apart have the same color. Take an equilateral triangle of side length 1 inch. The colors of the three vertices of the triangle must all be different — color the three points A, B, and C . Fix the point colored A (call the point A) and consider all equilateral triangles of side length 1 with one vertex at A. The other two vertices of such triangles trace a circle S of radius 1 with center at A. Note that each point on S must be colored B or C . (If any point of S is colored A, then that point and the center of the circle S have the same color and are 1 inch apart, which would be a contradiction.)
Take any one triangle with a vertex at A that has its other vertices on the circle S — the other two vertices of the triangle are colored B and C (call these points B and C ). Flip this triangle over the side BC to obtain a new point, which must also be colored A.
If this is done for all triangles with a vertex at A and sides of length 1 inch, the new point of each flipped triangle must also be colored A. This gives a circle T with the property that all points on the circle must be colored A. Take any two points on this circle T that are 1 inch apart (which is possible since its diameter is at least 1), and a contradiction is obtained.
(c) It is possible to color the points of the plane so no two points that are 1 inch apart have the same color. One such color can be obtained by using the following figure, where each square has diagonal length 0.9 inches. Use this 3 × 3 square as a
’tile’, and tile the plane with such squares, arranging the squares left-to-right and
bottom-to-top. No two points in the same square of a tile can have the same color (the squares are not large enough). Also, squares of the same color in diffferent tiles are too far apart to have points 1 inch apart.
Section 1.7
11. Prove that if n is an integer, then n2 ≥ n.
Solution:
We can prove that n2 ≥ n for every integer by considering three cases, when n = 0, when n ≥ 1, and when n ≤ −1. We split the proof into three cases because it is straightforward to prove the result by considering zero, positive integers, and negative
integers seperately.
(i) When n = 0, because 02 = 0, we see that 02 ≥ 0, it follows that n2 ≥ n is true in this case.
(ii) When n ≥ 1, when we multiply both sides of the inequality n ≥ 1 by the positive integer n, we obtain n · n ≥ n · 1, this implies that n2 ≥ n is true in this case.
(iii) In this case n ≤ −1, but n2 ≥ 0, hence n2 ≥ n is true.
Because the inequality is true in all three cases, we can conclude that if n is an integer, then n2 ≥ n.
12. (1.7.3) Prove that if x and y are real numbers then max(x, y) + min(x, y) = x + y.
Solution:
We can prove this by considering two cases, x ≥ y, and x ≤ y.
(i) When x ≥ y, max(x, y) + min(x, y) = x + y. (ii) When x ≤ y, max(x, y) + min(x, y) = y + x.
Because the inequality is true in both cases, the equality always holds.
13. Prove that the square of every even integer ends in 0, 4, or 6.
Solution:
Every even integer n can be written as n = 10k + r where r = 0, 2, 4, 6, 8. Examine each of these cases separately:
n = 10k + 0: n2 = 100k2, which ends in 0
n = 10k + 2: n2 = 100k2 + 40k + 4 = 10(10k2 + 4k) + 4 and hence ends in 4
n = 10k + 4: n2 = 100k2 + 80k + 16 = 10(10k2 + 8k + 1) + 6 and hence ends in 6
n = 10k + 6: n2 = 100k2 + 120k + 36 = 10(10k2 + 12k + 3) + 6 and hence ends in 6
Section 1.5
1. (1.5.3) What rule of inference is used in each of these arguments?
(a) Alice is a mathematics major. Therefore, Alice is either a mathematics major or a computer science major.
(b) Jerry is a mathematics major and a computer science major. Therefore, Jerry is a mathematics major.
(c) If it is rainy, then the pool will be closed. It is rainy, and therefore the pool is closed.
(d) If it snows today, the university will close. The university is not closed today.
Therefore, it did not snow today.
(e) If I go swimming, then I will stay in the sun too long. If I stay in the sun too long, then I will sunburn. Therefore, if I go swimming, then I will sunburn.
2. (1.5.15) For each of these arguments determine whether the argument is correct or incorrect and explain why.
(a) All students in this class understand logic. Xavier is a student in this class, there- fore Xavier understands logic.
(b) Every computer science major takes discrete mathematics. Natasha is taking dis- crete mathematics. Therefore, Natasha is a computer science major.
(c) All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit.
(d) Everyone who eats granola every day is healthy. Linda is not healthy. Therefore, Linda does not eat granola everyday.
3. (1.5.27) Use the rules of inference to show that if ∀x (P (x) → Q(x) ∧ S(x)) and
∀x (P (x) ∧ R(x)) are true, then ∀x (R(x) ∧ S(x)) is true.
4. (1.5.29) Use the rules of inference to show that if ∀x (P (x) ∨ Q(x)), ∀x (¬Q(x) ∨ S(x)),
∀x (R(x) → ¬S(x)), ∃x ¬P (x) are true, then ∃x ¬R(x) is true.
Section 1.6
5. (1.6.1) Use a direct proof to show that sum of two odd integers is even.
6. Using the definitions of even and odd integer, give a direct proof that the following statement is true for all integers n:
if n is odd, then 5n + 3 is even.
7. (1.6.17) Show that if n is an integer and n3 + 5 is odd, then n is even using
(a) a proof by contraposition. (b) a proof by contradiction.
8. Using the definitions of even and odd integer, give an indirect proof that the following statement is true for all integers n:
if n is odd, then 5n + 3 is even.
9. (1.6.27) Prove that if n is a positive integer, then n is odd if and only if 5n + 6 is odd.
10. * (Adapted from Problem A4 from the 1988 William Lowell Putnam Mathematics
Competition.)
(a) Suppose that every point of the plane is painted one of two colors (A or B). Must there be two points of the same color that are exactly 1 inch apart?
(b) Suppose that every point of the plane is painted one of three colors (A, B, or C ).
Must there be two points of the same color that are exactly 1 inch apart? (c) What if nine colors are allowed?
Section 1.7
11. Prove that if n is an integer, then n2 ≥ n.
12. (1.7.3) Prove that if x and y are real numbers then max(x, y) + min(x, y) = x + y.
Hiç yorum yok:
Yorum Gönder