All of Andy's Assignment's shuffled Flashcards

Question

# Translate each of these nested quantifications into an English statement that expresses a mathematical fact. The domain in each case consists of all real numbers. ∀x∀y(((x ≥ 0) ∧ (y < 0)) → (x – y > 0))

Answer 1

For every nonnegative number, one can find a negative number so that the first number minus the second is positive. One can find a nonnegative number so that for any positive number chosen, the first number minus the second is positive. An English statement for the given quantifier is "A nonnegative number minus a negative number is positive."

Answer 2

The expression for the statement is ∃ x (F(x) ∧ G(x)), and its negation is ∀ x¬(F(x) ∧ G(x)) and the sentence is "No pig can both swim and catch fish." Let F(x) be “x can swim” and let G(x) be “x can catch fish,” where the domain of discourse is pigs. Then our original statement is ∃x (F(x) ∧ G(x)). Its negation is ∀x¬(F(x) ∧ G(x)), which could also be written ∀x (¬F(x) ∨ ¬G(x)) by De Morgan’s law. In English this is “No pig can both swim and catch fish,” or “Every pig either is unable to swim or is unable to catch fish.”

Answer 3

∃ y1 ∃ y2(F(Nancy, y1) ∧ F(Nancy, y2) ∧ y1 ≠ y2 ∧ ∀ y(F(Nancy, y) → (y = y1 ∨ y = y2))) The statement "Nancy can fool exactly two people." can be expressed as ∃y1∃y2(F(Nancy, y1) ∧ F(Nancy, y2) ∧ y1 ≠ y2 ∧ ∀y(F(Nancy, y) → (y = y1 ∨ y = y2))).

Answer 4

``` ∀x∃y L(x, y) The statement "All students in this class have learned at least one programming language" can be expressed using quantifiers as ∀x∃y L(x, y) ```

Answer 5

modus tollens If modus tollens is used from the back, the given conclusion is arrived.

Answer 6

∃ x ∀ y ¬P(x, y) We need to use the transformations of De Morgan’s Laws for Quantifiers. In other words, we push all the negation symbols inside the quantifiers, changing the sense of the quantifiers as we do so, because of the equivalences of De Morgan’s Laws for Quantifiers. In addition, we need to use De Morgan’s laws to change the negation of a conjunction to the disjunction of the negations and to change the negation of a disjunction to the conjunction of the negations. We also use the fact that ¬(¬p) ≡ p. Using these method, we can rewrite the given expression as ∃x∀y ¬P(x, y).

Answer 7

∀ y(¬Q(y) ∨ ∃ xR(x, y)) We need to use the transformations of De Morgan’s Laws for Quantifiers. In other words, we push all the negation symbols inside the quantifiers, changing the sense of the quantifiers as we do so, because of the equivalences of De Morgan’s Laws for Quantifiers. In addition, we need to use De Morgan’s laws to change the negation of a conjunction to the disjunction of the negations and to change the negation of a disjunction to the conjunction of the negations. We also use the fact that ¬(¬p) ≡ p. Using these method, we can rewrite the given expression as ∀y(¬Q(y) ∨ ∃xR(x, y)).

Answer 8

Every system is either malfunctioning or in a diagnostic state. The expression ∀x(S(x, malfunctioning) ∨ S(x, diagnostic)) denotes that all systems are malfunctioning or all systems are in a diagnostic state, which can be simply stated as "Every system is either malfunctioning or in a diagnostic state."

Answer 9

Every system is working. Every system is not working. Some system is not working. Some system is working. - The expression ∀x¬S(x, working) denotes that all systems are not working, which can be stated in two ways: - No system is working. - Every system is not working.

Answer 10

P(1) ∨ P(3) ∨ P(5) The formal translation is as follows: ((−5 ≥ 0) ∧ P(−5)) ∨ ((−3 ≥ 0) ∧ P(−3)) ∨ ((−1 ≥ 0) ∧ P(−1)) ∨ ((1 ≥ 0) ∧ P(1)) ∨ ((3 ≥ 0) ∧ P(3)) ∨ ((5 ≥ 0) ∧ P(5)). Since only three of the x’s in the domain meet the condition, the answer is equivalent to P(1) ∨ P(3) ∨ P(5).

Answer 11

There is a student at your school who has visited North Dakota. At least one student at your school has visited North Dakota. Some students at your school have visited North Dakota. Every student at your school has visited North Dakota. All students at your school have visited North Dakota. It is not the case that a student at your school has visited North Dakota. No student at your school has visited North Dakota. There is a student at your school who has not visited North Dakota. At least one student at your school has not visited North Dakota. Some students at your school have not visited North Dakota. It is not the case that each student at your school has visited North Dakota. All students at your school have not visited North Dakota. Each student at your school has not visited North Dakota.

Answer 12

There exist two distinct people, the second of whom is enrolled in every class that the first is enrolled in. The statement ∃x1∃x2∀z((x1 ≠ x2) ∧ (C(x1, z) → C(x2, z))) can be written as "There exist two distinct people, the second of whom is enrolled in every class that the first is enrolled in."

Answer 13

∃xS(x); Some people can keep a secret. The original statement is ¬∃xS(x), and the negation is ∃xS(x); "Some people can keep a secret."

Answer 14

The errors are in step 3 and step 5, because the simplification rule is (P(x) ∧ Q(x)) → P(x).

Answer 15

Simplification applies to conjunctions, not disjunctions. The error is that simplification applies to conjunctions, not disjunctions.

Answer 16

Q(0) Q(−1) ∃ x¬Q(x) ∃ xQ(x) a) If x = 0, 0 + 1 > 2 · 0, we know that Q(0) is true. b) If x = –1, (−1) + 1 > 2 · (−1), we know that Q(−1) is true. c) If x = 1, 1 + 1 ≯ 2.1, we know that Q(1) is false. ``` From part (a), we know that there is at least one x that makes Q(x) true, so ∃xQ(x) is true. From part (c) we know that there is at least one x that makes Q(x) false, so ∃x¬Q(x) is true. ```

Answer 17

In order to prove the contrapositive, assume that n is odd. Then, we can write n = 2k + 1 for some integer k. Then, 3n + 2 = 3(2k + 1) + 2 = 6k + 5 = 2(3k + 2) + 1. This number is again of the form 2p + 1 for the integer p = 3k + 2; hence, it is odd. Thus, if n is odd, then 3n + 2 is odd.

Answer 18

Suppose that 3n + 2 is even and that n is odd. Since 3n + 2 is even, so is 3n. We know that if we subtract an odd number from an even number, we get an odd number. As 3n is even and n is odd, 3n – n should be odd, but 3n – n = 2n is even. This is a contradiction. Therefore, our supposition was wrong; hence n is even.

Answer 19

We need to prove two things, since this is an "if and only if" statement. First, let us prove directly that if n is even then 7n + 4 is even. Since n is even, it can be written as 2k for some integer k. Then, 7n + 4 = 14k + 4 = 2(7k + 2). This is 2 times an integer, so it is even as desired. Next, we give a proof by contraposition that if 7n + 4 is even then n is even. So, suppose that n is not even, i.e., that n is odd. Then, n can be written as 2k +1 for some integer k. Thus, 7n + 4 = 14k +11 = 2(7k + 5) + 1. This is 1 more than 2 times an integer; so it is odd. That completes the proof by contraposition.

Answer 20

{(0, a, x), (0, a, y), (0, b, x), (0, b, y), (0, c, x), (0, c, y), (1, a, x), (1, a, y), (1, b, x), (1, b, y), (1, c, x), (1, c, y)} The ordered n-tuple (a1, a2, ..., an) is the ordered collection that has a1 as its first element, a2 as its second element, ..., and an as its nth element. The Cartesian product of the sets C, A, and B, denoted by C × A × B, is the set of all ordered 3-tuples (a3, a1, a2), where a3 ∈ C, a1 ∈ A, and a2 ∈ B. Hence, C × A × B = {(a3, a1, a2) ∣ a3 ∈ C ∧ a1 ∈ A ∧ a2 ∈ B}. Thus, the Cartesian product C × A × B can be written as {(0, a, x), (0, a, y), (0, b, x), (0, b, y), (0, c, x), (0, c, y), (1, a, x), (1, a, y), (1, b, x), (1, b, y), (1, c, x), (1, c, y)}.

Answer 21

- Suppose that n and m are odd numbers. - Then n = 2k+1 for some integer k and m = 2q+1 for some integer q. - By multiplying these equations, we obtain nm = (2k+1)(2q+1). - Distributing, we get nm = 2(2kq + k +q) + 1 - By definition of an odd integer, that means that nm is odd.

Answer 22

This cannot be the power set of any set. Ø, {a}, and {Ø, a} are the subsets. These are not valid subsets of a set.

Answer 23

This is the power set of {a, b}. Ø, {a}, {b}, and {a, b} are the subsets.

Answer 24

3, as this set contains exactly three different elements, each of which is a set Cardinality is the number of elements in a set. The set {Ø, {Ø}, {Ø, {Ø} } } contains three elements Ø, {Ø}, and {Ø, {Ø} }.

Answer 25

- Fill the 5-gallon jug from the 8-gallon jug, leaving the contents (3, 5, 0), where the ordered triple is used to record the amount of water in the 8-gallon jug, the 5-gallon jug, and the 3-gallon jug, respectively. - Fill the 5-gallon jug from the 8-gallon jug, leaving the contents (3, 5, 0), where the ordered triple is used to record the amount of water in the 8-gallon jug, the 5-gallon jug, and the 3-gallon jug, respectively. - Pour the contents of the 3-gallon jug back into the 8-gallon jug, leaving (6, 2, 0). - Empty the 5-gallon jug’s contents into the 3-gallon jug, leaving (6, 0, 2), and then fill the 5-gallon jug from the 8-gallon jug, producing (1, 5, 2). - Top off the 3-gallon jug from the 5-gallon jug, and there will be (1, 4, 3), with four gallons in the 5-gallon jug. Fill the 5-gallon jug from the 8-gallon jug, leaving the contents (3, 5, 0), where we are using the ordered triple to record the amount of water in the 8-gallon jug, the 5-gallon jug, and the 3-gallon jug, respectively. Next fill the 3-gallon jug from the 5-gallon jug, leaving (3, 2, 3). Pour the contents of the 3-gallon jug back into the 8-gallon jug, leaving (6, 2, 0). Empty the 5-gallon jug’s contents into the 3-gallon jug, leaving (6, 0, 2), and then fill the 5-gallon jug from the 8-gallon jug, producing (1, 5, 2). Finally, top off the 3-gallon jug from the 5-gallon jug, and we’ll have (1, 4, 3), with four gallons in the 5-gallon jug.

Answer 26

- We will give a proof by contradiction. - Suppose that m is odd and n is odd. - By definition of odd number, m = 2p+1 for some integer p, and n = 2q+1 for some integer q. - Therefore, nm = (2q+1)(2p+1) = 4pq + 2q + 2p + 1 = 2(2pq + q + p) + 1. - By definition of odd number, this means that nm is odd. - Therefore, we have proved the contraposition of the desired statement and thus completed the proof by contraposition.

Answer 27

{3n | n = 0, 1, 2, 3, 4} In set builder notation, we characterize all the elements in a set by stating the property or properties they must have to be members.

Answer 28

If |y| ≥ 2, then 2x^2 + 5y^2 ≥ 2x^2 + 20 ≥ 20, so, the only possible values of y to try are 0 and ±1. In the former case, we would be looking for solutions to 2x2 = 14. In the latter case to 2x2 = 9. Clearly, there are no integer solutions to these equations, so, there are no solutions to the original equation. If |y| ≥ 2, then 2x2 + 5y2 ≥ 2x2 + 20 ≥ 20, so the only possible values of y to try are 0 and ±1. In the former case we would be looking for solutions to 2x2 = 14 and in the latter case to 2x2 = 9. Clearly, there are no integer solutions to these equations, so there are no solutions to the original equation.

Answer 29

B, D B is a subset of A. A = {2, 4, 6} and B = {2, 6}. C is a subset of A. A = {2, 4, 6} and C = {4, 6}. C is a subset of D. D = {4, 6, 8} and C = {4, 6}.

Answer 30

- a = 2 and b = 1/2, then ab = 21/2 is a counterexample that disproves the statement. - a = 2 and b = 1/2, then ab = 21/2 is a counterexample that proves the statement. - a = 3 and b = 1/2, then ab = 31/2 is a counterexample that disproves the statement. - If a = p / q and b = r / s are rational numbers, then ab can be written as )r / s= (pr / qs) , where , q, r, and s are integers. Thus, ab is rational. An assertion like this one is implicitly universally quantified—it means that for all rational numbers a and b, ab is rational. To disprove such a statement it suffices to provide a counterexample. There are two counter examples for the given statement. 1) Take a = 2 and b = 1/2. then ab = 21/2 = 2 [Math Processing Error] . 2) Take a = 3 and b = 1/2, then a^b = 3^(1/2) = √3 .

Answer 31

- Assume there were at most two chosen days falling into any one month. - Then, there will be at most 2.12 = 24 chosen days in 12 months. - This contradicts the assumption that we have 25 days. - Hence, three chosen days must fall in the same month.

Answer 32

- Assume n = m2, for some nonnegative integer m. - If m = 0, then n + 2 = 2, which is not a perfect square. The smallest perfect square greater than n is (m + 1)2. - Lets assume m ≥ 1. - Expand (m + 1)2 to obtain (m + 1)2 = m2 + 2m + 1 = n + 2m + 1 > n + 2 + 1 > n + 2. Expand (m + 1)2 to obtain (m + 1)2 = m2 + 2m + 1 = n + 2m + 1 > n + 2 + 1 > n + 2. - Hence, n + 2 is not a perfect square. An integer a is a perfect square if there is an integer b such that a = b2.

Answer 33

Of these three numbers, at least two must have the same sign, since there are only two signs. The product of two with the same sign is nonnegative. Of these three numbers, at least two must have the same sign (both positive or both negative), since there are only two signs. (It is conceivable that some of them are zero, but we view zero as positive for the purposes of this problem.) The product of two with the same sign is nonnegative.

Answer 34

- Therefore, on the right-hand equals c. - It follows that <= min(b,c). - On the right-hand side, c <= min(a,c), so, min(min(a,c), b) = c. - On the right-hand side, c <= min(a,c), so, min(min(a,b), c) = c. - So, the left-hand side equals c. - Suppose c is the smallest of the three real numbers. - It follows that c >= min(a,b). Suppose c is the smallest of the three real numbers. It follows that c ≤ min(b, c). So, the left-hand side equals c. On the right-hand side, c ≤ min(a, b), so, min(min(a, b), c) = c. Therefore, right hand side equals c.

Answer 35

{x ∈ Z ∣ x < x^2} = {x ∈ Z | x ≠ 0 ∧ x ≠ 1} Negative integers certainly satisfy this inequality, as do all positive integers greater than 1. However, 0 ≮ 0^2 and 1 ≮ 1^2. Thus the truth set is {x ∈ Z | x ≠ 0 ∧ x ≠ 1} = {..., −3, −2, −1, 2, 3, ...}.

Answer 36

- Suppose x is rational. - So, x = p/q where p and q are integers with q ≠ 0. - Then, x/2 = p/(2q). Since q ≠ 0. 2q ≠ 0. - Hence, x/2 is rational. Suppose that x = p/q where p and q are integers with q ≠ 0. Then x/2 = p/(2q), and this is rational, since p and 2q are integers.

Answer 37

- The set is countably infinite. - The set is finite. - The set is countably infinite with one-to-one correspondence 1 ↔ 11, 2 ↔ 12, 3 ↔ 13, and so on. - The set is countably infinite with one-to-one correspondence 1 ↔ 10, 2 ↔ 12, 3 ↔ 17, and so on. - The one-to-one correspondence is given by n ↔ (2n + 10). The integers in the set are 11, 12, 13, 14, and so on.

Answer 38

- The set is countable. | - The set is countably infinite with one-to-one correspondence 1 ↔ (2,1), 2 ↔ (3,1), 3 ↔ (2,2), 4 ↔ (3,2),and so on.

Answer 39

If we write down the first few terms of this sum we notice a pattern. It starts (1 + 1 + 1 + 1 + 1 + 1 + 1) + (2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2) + (3 + 3 + 3 + ... + 3) + .... There are seven 1s, then 19 2s, then 37 3s, and so on; in general, the number of i's is (i + 1)^3 – i^3 = 3i^2 + 3i + 1. So, we need to sum i(3i^2 + 3i + 1) for an appropriate range of values for i. We must find this range. It gets a little messy at the end if m is such that the sequence stops before a complete range of the last value is present. Let n=⌊^3√m⌋−1 . Then there are n + 1 blocks, and (n + 1)^3 – 1 is where the next-to-last block ends. The sum of those complete blocks is n∑i=1 i(3i^2+3i+1)=n∑i=1 3i^3+3i^2+i=n(3n+4)(n+1)^2/4 . The remaining terms in our summation all have the value n + 1 and the number of them present is m – ((n + 1)3 – 1). Our final answer is therefore m∑k=0 ⌊^3√k⌋=n(3n+4)(n+1)^2/4+(n+1)(m−(n+1)^3 +1) , where once again, n=⌊^3√m⌋−1.

Answer 40

511 We could evaluate this sum by breaking it into two summations. Both could be computed from the formula for the sum of a geometric progression. There is an easier solution though. All powers of 2 cancel except −20 when j = 0 and 29 when j = 8.

Answer 41

[1 1] [1 1] [1 1] A matrix all of whose entries are either 0 or 1 is called a zero–one matrix. Let A = [aij] be an m × k zero–one matrix and B = [bij] be a k × n zero–one matrix. Then, the Boolean product of A and B, denoted by A ⊙ B, is the m × n matrix with (i, j)th entry cij, where cij = (ai1 ∧ b1j) ∨ (ai2 ∧ b2j) ∨ ⋯ ∨ (aik ∧ bkj).

Answer 42

a0 = –1 Plug n = 1, 2, 3, 4, 5 into the formula: an = an – 1 – an – 2.

Answer 43

a0 = –1 and a1 = 0 Plug n = 2, 3, 4, 5 into the formula: an = na(n – 1) + a^2n – 2

Answer 44

[0 1] [0 1] A matrix all of whose entries are either 0 or 1 is called a zero–one matrix. We can write a∧b={1 if a=b=1 {0 otherwise Let A = [aij] and B = [bij] be m × n zero–one matrices. The meet of A and B is the zero–one matrix with (i, j)th entry aij ∧ bij. The meet of A and B is denoted by A ∧ B.

Answer 45

B = [0 1] | [0 1]

Answer 46

3 Plug n = 0 into the formula: an = 2 · (−3)^n + 5^n. a0 = 2 · (−3)^0 + 5^0 = 2(1) + 1

Answer 47

2,639 Plug n = 5 into the formula: an = 2 · (−3)^n + 5^n. a5 = 2 · (−3)^5 + 55 = –486 + 3,125

Answer 48

an = 1.09a(n – 1) The amount after (n − 1) years is multiplied by 1.09 to give the amount after n years, since 9% of the value must be added to account for the interest.

Answer 49

an = 1000(1.09)^n The amount after (n − 1) years is multiplied by 1.09 to give the amount after n years, since 9% of the value must be added to account for the interest.

Answer 50

a100 ≈ $5,529,041 The amount after (n − 1) years is multiplied by 1.09 to give the amount after n years, since 9% of the value must be added to account for the interest.

Answer 51

an = −3 + 2(−3) + 4an − 2 an = −3 + 2(−3) + 4(−3) + 8an − 3 an = −3 + 2(−3) + 4(−3) + 8(−3) + 16an − 4 Continuing the same manner, an = −3(1 + 2 + 4 + · · · + 2n − 1) + 2nan − n = −3(2n − 1) + 2n(−1) = −2n + 2 + 3

Answer 52

84 | ∑ j∈S j^2=1^2+3^2+5^2+7^2

Answer 53

[-4 9 2 10] [-4 -5 4 0 ] The sum of two matrices of the same size is obtained by adding elements in the corresponding positions.

Answer 54

# Define the sets Ai := {(i, n) | n ∈ Z^+}, where i belongs to Z^+. We can list the sets as A1 = {(1, n) | n ∈ Z^+}, A2 = {(2, n) | n ∈ Z^+}, and so on. For each i, define f(n) = (i, n), ∀n ∈ Z^+. Clearly, it is a one-to-one correspondence from the set of positive integers to the set Ai. From the definition of cardinality, each Ai is a countable set. Thus, we can think of Z^+ × Z^+ as a union of countable number of countable sets A1, A2, ..., An, .... We know that the union of countable number of countable sets is countable. Thus, Z^+ × Z^+ is countable. Let us define the sets Ai := {(i, n) | n ∈ Z^+}, where i belongs to Z^+. We can list the sets as A1 = {(1, n) | n ∈ Z^+}, A2 = {(2, n) | n ∈ Z^+}, and so on. For each i, define f(n) = (i, n), ∀n ∈ Z^+. Clearly, it is a one-to-one correspondence from the set of positive integers to the set Ai. From the definition of cardinality, each Ai is a countable set. Thus, we can think of Z^+ × Z^+ as a union of countable number of countable sets A1, A2, ..., An, .... We know that the union of countable number of countable sets is countable. Thus, Z^+ × Z^+ is countable.

Answer 55

[-37/125 18/125] [9/125 -1/125] Use the value of (A^(–1))^2 to arrive at (A^(–1))^3

Answer 56

[2 0 -3 -4 -1] [24 -7 20 29 2] [-10 4 -17 -24 -3] To multiply matrices A and B, compute the (i, j)^th entry of the product AB by adding all the products of elements from the i^th row of A with the corresponding element in the j^th column of B.

All of Andy's Assignment's shuffled Flashcards

(80 cards)