discrete_mathematics_with_applications/chapter_4/test_yourself.md

Test Yourself

Page 194

1. An integer is even if, and only if, ______.

it equals twice some integer.

2. An integer is odd if, and only if, ______.

it equals twice some integer plus 1.

3. An integer n is prime if, and only if, ______.

n is greater than 1 and if n equals the product of any two positive integers, then one of the integers equals 1 and the other equals n.

4. The most common way to disprove a universal statement is to find ______.

a counterexample.

5. According to the method of generalizing from the generic particular, to show that every element of a set satisfies a certain property, suppose x is a ______, and show that ______.

particular but arbitrarily chosen element of the set; x satisfies the given property.

6. To use the method of direct proof to prove a statement of the form, "For every x in a set D, if P(x) then Q(x)," one supposes that ______ and one shows that ______.

x is a particular but arbitrarily chosen element of the set D that makes the hypothesis P(x) true; x makes the conclusion Q(x) true.

---

Test Yourself

Page 204

1. The meaning of every variable used in a proof should be explained with ______.

The body of the proof.

2. Proofs should be written in sentences that are ______ and ______.

complete; grammatically correct

3. Every assertion in a proof should be supported by a ______.

reason

4. The following are some useful "little words and phrases" that clarify the reasoning in a proof:

   ______, ______, ______, ______, and ______.

because; since; then; thus; so; hence; therefore; consequently; it follows that; by substitution

5. A new thought or fact that does not follow as an immediate consequence of the preceding statement can be introduced by writing ______, ______, ______, ______, or ______.

observe that; note that; recall that; but; now

6. To introduce a new variable that is defined in terms of previous variables, use the word ______.

let

7. Displaying equations and inequalities increases the ______ of a proof.

readability

8. Some proof-writing mistakes are ______, ______, ______, ______, ______, ______, and ______.

arguing from examples; using the same letter to mean two different things; jumping to a conclusion; assuming what is to be proved; confusion between what is known and what is still to be shown; use of any when the correct word is some; misuse of the word if

---

Test Yourself

Page 210

1. To show that a real number is rational, we must show that we can write it as ______.

The ratio of integers, where the denominator is not 0.

2. An irrational number is a ______ that is ______.

real number; not rational

3. Zero is a rational number because ______.

zero is an integer that is a ratio of integers where the denominator is not zero, 0 = \dfrac{0}{1}.

---

Test Yourself

Page 220

1. To show that a nonzero integer d divides an integer n, we must show that ______.

n equals d divided by some integer and d \neq 0.

2. To say that d divides n means the same as saying that ______ is divisible by ______.

n; d

3. If a and b are positive integers and a \mid b, then ______ is less than or equal to ______.

a; b

4. For all integers n and d, d \nmid n if, and only if, ______.

\dfrac{n}{d} is not an integer.

5. If a and b are integers, the notation a \mid b denotes ______ and the notation a/b denotes ______.

the sentence "a divides $b$"; the number obtained when a is divided by b

6. The transitivity of divisibility theorem says that for all integers a, b, and c, if ______ then ______.

a \mid b and b \mid c; a \mid c

7. The divisibility by a prime theorem says that every integer greater than 1 is ______.

divisible by some prime number.

8. The unique factorization of integers theorem says that any integer greater than 1 is either ______ or can be written as ______ in a way that is unique except possibly for the ______ in which the numbers are written.

prime; a product of prime numbers; order

---

Test Yourself

Page 232

1. The quotient-remainder theorem says that for all integers n and d with d \geq 0, there exists ______ q and r such that ______ and ______.

integers; n = dq + r; 0 \leq r < d

2. If n and d are integers with d > 0, n\ div\ d is ______ and n \mod d is ______.

the quotient obtained when n is divided by d; the nonnegative remainder obtained when n is divided by d

3. The parity of an integer indicates whether the integer is ______.

even or odd

4. According to the quotient-remainder theorem, if an integer n is divided by a positive integer d, the possible remainders are ______. This implies that n can be written in one of the forms ______ for some integer q.

0, 1, 2, \dots d - 1; dq + 1, dq + 2, \dots dq + (d - 1)

5. To prove a statement of the form "If A_1 or A_2 or A_3, then C," prove ______ and ______ and ______.

If A_1 then C; If A_2 then C; If A_3 then C

6. The triangle inequality says that for all real numbers x and y, ______.

|x + 6| \leq |x| + |y|

---

Test Yourself

Page 239

1. Given any real number x, the floor of x is the unique integer n such that ______.

n \leq x < n + 1

2. Given any real number x, the ceiling of x is the unique integer n such that ______.

n - 1 < x \leq n

---

Test Yourself

Page 248

1. To prove a statement by contradiction, you suppose that ______ and you show that ______.

the statement is false; this supposition leads to a contradiction

2. A proof by contraposition of a statement of the form "$\forall x \in D, \text{ if } P(x) \text{ then } Q(x)$" is a direct proof of ______.

\forall x \in D, \text{ if } \neg Q(x) \text{ then } \neg P(x)

3. To prove a statement of the form "$\forall x \in D, \text{ if } P(x) \text{ then } Q(x)$" by contraposition, you suppose that ______ and you show that ______.

Q(x) is false; P(x) is false.

---

Test Yourself

Page 256

1. The ancient Greeks discovered that in a right triangle where both legs have length 1, the ratio of the length of the hypotenuse to the length of one of the legs is not equal to a ratio of ______.

two integers.

2. One way to prove that \sqrt{2} is an irrational number is to assume that \sqrt{2} = \dfrac{m}{n} for some integers m and n that have no common factor greater than 1, use the lemma that says that if the square of an integer is even then ______, and eventually show that m and n ______.

that integer is even; have a common factor greater than 1.

3. One way to prove that there are infinitely many prime numbers is to assume that there is a largest prime number p, construct the number ______, and then show that this number has to be divisible by a prime number that is greater than ______.

N = (2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \dots \cdot p) + 1; p

---

Test Yourself

Page 265

1. The total degree of a graph is defined as ______.

The sum of the degrees of all the vertices of the graph

2. The handshake theorem says that the total degree of a graph is ______.

equal to the number of edges of the graph

3. In any graph the number of vertices of odd degree is ______.

an even number

4. A simple graph is ______.

a graph with no loops or parallel edges

5. A complete graph on n vertices is a ______.

a simple graph with n vertices whose set of edges contains exactly one edge for each pair of vertices

6. A complete bipartite graph on (m, n) vertices is a simple graph whose vertices can be divided into two distinct, non-overlapping sets, say V with m vertices and W with m vertices, in such a way that (1) there is ______ from each vertex of V to each vertex of W, (2) there is ______ from any one vertex of V to any other of V, and (3) there is ______ from any one vertex of W to any other vertex of W.

one edge; no edge; no edge

---

Test Yourself

Page 277

1. When an algorithm statement of the form x := e is executed, ______.

The expression e is evaluated (using the current values of all the variables in the expression), and this value is placed in the memory location corresponding to x (replacing any previous contents of the location)

2. Consider an algorithm statement of the following form.

\text{\textbf{if }(condition)}\\ \text{\textbf{then }} s_1\\ \text{\textbf{else }} s_2

then the algorithm at s_1 is executed; then the algorithm at s_2 is executed

When such a statement is executed, the truth or falsity of the condition is evaluated. If condition is true, ______. If condition is false, ______.

3. Consider an algorithm statement of the following form.

\text{\textbf{while }(condition)}

[statements that make up the body of the loop]

\text{\textbf{end while}}

When such a statement is executed, the truth or falsity of the condition is evaluated. If condition is true, ______. If condition is false, ______.

the statements that make up the body of the loop are executed in order and then execution moves back to the beginning of the loop and the process repeats; the loop ends and execution passes to the next algorithm statement following the loop

4. Consider an algorithm statement of the following form.

the statements that make up the body of the loop are executed in order, the variable's value is assigned to the next (iterated), and then execution moves back to the beginning of the loop and the process repeats; the loop ends and execution passes to the next algorithm statement following the loop

\text{\textbf{for } variable } := \text{initial expression \textbf{to} final expression.}

[statements that make up the body of the loop]

\text{\textbf{next } (same) variable}

When such a statement is executed, variable is set equal to the value of the initial expression, and a check is made to determine whether the value of variable is less than or equal to the value of final expression. If so, ______. If not, ______.

5. Given a nonnegative integer a and a positive integer d the division algorithm computes ______.

Integers q and r with the property that n = dq + r and 0 \leq r < d.

6. Given integers a and b, not both zero, \text{gcd}(a, b) is the integer d that satisfies the following two conditions: ______ and ______.

d \mid a and d \mid b; if c is a common divisor of both a and b, then c \leq d.

7. If r is a positive integer, then gcd(r, 0) = ______.

r

8. If a and b are integers not both zero and if q and r are nonnegative integers such that a = bq + r then \text{gcd}(a, b) = ______.

gcd(b, r)

9. Given positive integers A and B with A > B, the Euclidean algorithm computes ______.

the greatest common divisor of A and B, \text{gcd}(A, B).