COMP 3240 Fall 2019
Midterm Exam Solutions
Part I (12pts): Prove the following theorems using direct proof, indirect proof
(contradiction, contrapositive), counterexample, and/or proof by cases.
(1) (6pts) For every
...
COMP 3240 Fall 2019
Midterm Exam Solutions
Part I (12pts): Prove the following theorems using direct proof, indirect proof
(contradiction, contrapositive), counterexample, and/or proof by cases.
(1) (6pts) For every pair of positive real numbers x and y, if xy > 400, then x > 20 or
y > 20.
(2) (6pts) For integers x and y, if xy is odd, then x is odd and y is odd.Correct answers marked with an asterisk (*)
1) p = F, q = T, and r = T.
Select the expression that evaluates to true.
a. ¬(? ∨ ?)
*b. (¬? ∧ ?) ∨ ?
c. (¬? ∨ ?) ∧ ?
d. ? ∨ ¬? ∨ ¬?
2) The propositional variables f, h, and p represent the propositions:
f: The student got an A on the final.
h: The student turned in all the homework.
p: The student is on academic probation
Select the logical expression that represents the statement: "The student is not on
academic probation and the student got an A on the final or turned in all the homework."
*a. ¬? ∧ (? ∨ ℎ)
b. (¬? ∧ ?) ∨ ℎ
c. ¬? ∧ ? ∧ ℎ
d. ¬(? ∧ ?) ∨ ℎ
3) Select the proposition that is a contradiction.
*a. ¬(? ∨ ?) ∧ ?
b. (? ∨ ?) ∧ ?
c. (¬? ∧ ?) ↔ ?
d. (¬? ∧ ¬?) → ?4) Select the proposition that is logically equivalent to ¬? → ? .
a. ? ∧ ¬?
*b. ? ∨ ?
c. ¬? ∨ ?
d. ¬? ∧ ?
5) Use De Morgan’s law to select the statement that is equivalent to:
"It is not true that the patient has high blood pressure or influenza."
a. The patient has high blood pressure or has influenza.
*b. The patient does not have high blood pressure and does not have influenza.
c. The patient does not have high blood pressure or does not have influenza.
d. The patient has high blood pressure and has influenza.
6) Select the law which shows that the two propositions are logically equivalent.
¬((? ∨ ?) ∧ (¬? ∧ ? ∧ ?))
¬(? ∨ ?) ∨ ¬(¬? ∧ ¬?)
*a. DeMorgan’s law
b. Distributive law
c. Associative law
d. Complement law
7) Select the law which shows that the two propositions are logically equivalent.
(¬? ∧ (? ∨ ¬?)) ∨ (¬(¬? ∧ ?)
¬? ∧ ((? ∨ ¬?) ∨ ?)
a. DeMorgan’s law
*b. Distributive law
c. Associative law
d. Commutative law8) The domain of discourse are the students in a class. Define the predicates:
S(x): x studied for the test
A(x): x received an A on the test
Select the logical expression that is equivalent to:
"Everyone who studied for the test received an A on the test."
a. ∀?(?(?) → ?(?))
*b. ∀?(?(?) → ?(?))
c. ∀?(?(?) ∧ ?(?))
d. ∀?(?(?) ↔ ?(?))
9) The domain of discourse are the students in a class. Define the predicates:
S(x): x studied for the test
A(x): x received an A on the test
Select the logical expression that is equivalent to:
"Someone who did not study for the test received an A on the test."
a. ∃?(?(?) → ¬?(?))
b. ∃?(¬?(?) → ?(?))
*c. ∃?(¬?(?) ∧ ?(?))
d. ∃?(¬?(?) ↔ ?(?))
10) The domain for variable x is the set {Ann, Ben, Cam, Dave}. The table below gives
the values of predicates P and Q for every element in the domain.
Name P(x) Q(x)
Ann F F
Ben T F
Cam T T
Dave T T
Select the statement that is true.
*a. ∀?(?(?) → ?(?))b. ∀?(?(?) → ?(?))
c. ∀?(?(?) ∧ ?(?))
d. ∀?(?(?) ∧ ?(?))
11) Select the truth assignment that shows that the argument below is not valid:
a. p = T
q = T
b. p = F
q = T
*c. p = T
q = F
d. p = F
q = F
12) Select the correct expression for (?) in the proof segment below:
1. ? → ? Hypothesis
2. ? ∧ ? Hypothesis
3. (?) Simplification, 2
4 ? Modus Tollens, 1, 3
*a. ?
b. ?
c. ? ∨ ?
d. ? ∧ ?
13) Select the correct rule to replace (?) in the proof segment below:
1. ¬? ∨ ? Hypothesis
2. ¬¬? Hypothesis
3. ? (?)a. Simplification
b. Hypothetical syllogism
*c. Disjunctive syllogism
d. Resolution
14) The domain for variables x and y is the set {1, 2, 3}. The table below gives the
values of P(x, y) for every pair of elements from the domain. For example, P(2, 3) = F
because the value in row 2, column 3, is F.
P 1 2 3
1 T T T
2 T F F
3 F T F
Select the statement that is false.
a. ∃?∀??(?, ?)
b. ∀?∃??(?, ?)
*c. ∃?∀??(?, ?)
d. ∀?∃??(?, ?)
15) Select the logical expression that is equivalent to:
¬∀?∃?(?(?) ∧ ?(?, ?))
*a. ∃?∀?(¬?(?) ∨ ¬?(?, ?))
b. ∃?∀?(¬?(?) ∨ ?(?, ?))
c. ∀?∃?(¬?(?) ∨ ¬?(?, ?))
d. ∀?∃?(¬?(?) ∨ ¬?(?, ?))
16) Select the expression that is equivalent to the following statement:
Among any two consecutive positive integers, there is at least one integer that is not
prime.
*a. If x is a positive integer, then x is not prime or x+1 is not prime.
b. If x is a positive integer, then x is not prime and x+1 is not prime.c. If x and y are positive integers, then x is not prime or y is not prime.
d. If x and y are positive integers, then x is not prime and y is not prime.
17) Select the value for x that is a counter-example to the following statement:
For every integer ?, ? < ?8 .
a. x = 1/2
b. x = -1/2
c. x = -1
*d. x = 1
18) Theorem: If r and s are rational numbers, then the product of r and s is a rational
number.
Which facts are assumed in a direct proof of the theorem?
a. rs = a/b, where a and b are integers ? ≠ 0 .
b. rs = a/b, where a and b are integers ? ≠ 0 .
c. r = a/b, and s = c/d, where a, b, c, d are integers and ? ≠ 0 and ? ≠ 0 .
*d. r = a/b, and s = c/d, where a, b, c, d are integers and ? ≠ 0 and ? ≠ 0 .
19) Theorem: For any two real numbers, x and y, if x and y are both rational then x + y is
also rational.
Which facts are assumed and which facts are proven in a direct proof of the theorem?
a. Assumed: x is rational or y is rational
Proven: x + y is rational
*b. Assumed: x is rational and y is rational
Proven: x + y is rational
c. Assumed: x + y is rational
Proven: x is rational or y is rational
d. Assumed: x + y is irrational
Proven: x is irrational and y is irrational20) Theorem: For any real number ? , if ?8 − 6? + 5 > 5 , then ? ≥ 5 or ? ≤ 1 .
Which facts are assumed and which facts are proven in a proof by contrapositive of the
theorem?
a. Assumed: ? ≥ 5 or ? ≤ 1
Proven: ?8 − 6? + 5 ≤ 5
b. Assumed: ? ≥ 5 and ? ≤ 1
Proven: ?8 − 6? + 5 ≤ 5
c. Assumed: ? < 5 or ? > 1
Proven: ?8 − 6? + 5 ≤ 5
*d. Assumed: 1 < ? < 5
Proven: ?8 − 6? + 5 ≤ 5
21) Theorem: For any two real numbers, x and y, if x and y are both rational then x + y is
also rational.
Which facts are assumed and which facts are proven in a proof by contrapositive of the
theorem?
a. Assumed: x is rational or y is rational
Proven: x + y is rational
b. Assumed: x is rational and y is rational
Proven: x + y is rational
*c. Assumed: x + y is irrational
Proven: x is irrational or y is irrational
d. Assumed: x + y is irrational
Proven: x is irrational and y is irrational
22) Theorem: The average of any two real numbers is less than or equal to at least one
of the two numbers.
A proof by contradiction of the theorem starts by assuming which fact?
a. For every two real numbers, x and y, (? + ?)/2 ≤ ? or (? + ?)/2 ≤ ? .
b. For every two real numbers, x and y, (? + ?)/2 > ? or (? + ?)/2 > ? .
*c. There exists two real numbers, x and y, such that (? + ?)/2 > ? and (? + ?)/2 > ? .
d. There exists two real numbers, x and y, such that (? + ?)/2 > ? or (? + ?)/2 > ? .23) Theorem: For any real numbers, ? and ? , ???(?, ?) = (1/2)(? + ? + |? − ?|) .
One of the cases in the proof of the theorem uses the assumptions that |? − ?| = ? − ? .
Select the case that corresponds to this argument.
a. ? ≥ 0
b. ? < 0
*c. ? ≥ ?
d. ? < ?
24) Select the statement that is false.
a. ? ⊂ ?
b. ?O ⊂ ?
*c. ? ⊂ ?O
d. ? ⊆ ?
25) Use the definitions below to select the statement that is true.
? = {x ∈ ?: ?is even}
? = {x ∈ ?: −4 < ? < 17}
a. A is finite.
b. ? ⊆ ?
c. ? ⊂ ?
*d. ∅ ⊂ ?
26) Use the definition below to select the statement that is false.
? = {x ∈ ?: ?is even and4 < ? < 17}
a. 4 ∉ ?
b. 6 ∈ ?
c. 17 ∉ ?*d. |?| = 7
27) A = {1, 2, {3, 4}, {5, 6, 7}}
Select the statement that is true.
a. {3} ∈ ?
b. {3,4} ⊆ ?
*c. {1,2} ⊆ ?
d. {1,2} ∈ ?
28) A = {1, 2, 3, 4}.
Select the statement that is false.
a. ∅ ∈ ?(?)
b. ∅ ⊆ ?(?)
c. {2,3} ∈ ?(?)
*d. {2,3} ⊆ ?(?)
29) For ? ∈ ?O , ?_ is defined to be the set of all integer multiples of ? . Select the set
corresponding to (`a _b8 ?_) ∩ {x ∈ ?: 1 ≤ ? ≤ 30}
a. ∅
b. {24}
*c. {12, 24}
d. {6, 12, 18, 24, 30}
30) ? = {x ∈ ?: ?is a prime number}
? = {3,5,9,12,15,16}
The universal set ? is the set of all integers. Select the set corresponding to ? ∩ ? .
a. {3,5}
b. {9,12,16}c. {3,5,9,15}
*d. {9,12,15,16}
31) Select the set that is equivalent to ? ∪ (? ∩ ?) .
a. ∅
*b. ?
c. ? ∪ ?
d. ? ∩ ?
32) Select the law that establishes that the two sets below are equal.
? ∩ (? ∪ ?) = ? ∩ (? ∩ ?)
a. Distributive law
b. Associative law
c. Absorption law
*d. De Morgan's law
33) ? = {a, ?}
? = {1,2,3}
Select the false statement.
a. ? ∩ ?8 = ∅
b. (?, 3) ∈ ? × ?
*c. |? × ?| = 5
d. (?, ?) ∈ ?8
34) ? = {a, ?}
? = {1,2,3}
Select the the expression that is an element of ? × ? × ? .
*a. (?, 2,3)b. (?, ?, 1)
c. (?, 28)
d. (2,1,1)
35) Select the collection of sets that forms a partition of:
{1, 2, 3, 4, 5, 6, 7, 8}
a. {1, 2, 5, 7}
{3, 4}
{8}
*b. {1, 2, 5, 7}
{3, 4, 6}
{8}
c. {0, 1, 2, 5, 7}
{3, 4, 6, 8}
d. {1, 2, 5, 7}
{3, 4, 6, 8}
{2, 4}
36) Select the collection of sets that forms a partition of ? .
a. {? ∈ ?: ? < 2}
{? ∈ ?: 2 < ? < 4}
{? ∈ ?: 4 ≤ ?}
b. {? ∈ ?: ? < 4}
{? ∈ ?: 2 ≤ ? ≤ 4}
{? ∈ ?: 2 < ?}
*c. {? ∈ ?: ? < 2}
{? ∈ ?: 2 ≤ ? < 4}
{? ∈ ?: 4 ≤ ?}
d. {? ∈ ?: ? ≤ 2}
{? ∈ ?: 2 ≤ ? < 4}
{? ∈ ?: 4 ≤ ?}37) The function ?: {0,1}8 → {0,1}j is defined as:
For every ? ∈ {0,1}8, ?(?) = 0? .
Select the set corresponding to the range of ? .
a. {01, 00}
b. {00, 01, 10, 11}
*c. {000, 001, 010, 011}
d. {000, 001, 010, 011, 100, 101, 110, 111}
38) Two functions, f and g, map real numbers to integers. The functions f and g are
defined as:
?(?) = ⌊? + l
8
⌋?(?) = ⌈? − l
8
⌉
Select the value for x such that ?(?) ≠ ?(?) .
a. 0
b. 2
*c. 2.5
d. 2.75
39) ?: {0,1}j → {0,1}j
f(x) is obtained by removing the second bit from x and placing the bit at the end of the
string. For example, f(101) = 110.
Select the correct description of the function f.
*a. One-to-one and onto
b. One-to-one but not onto
c. Onto but not one-to-one
d. Neither one-to-one nor onto
40) ?: ?O → ?O. ?(?) = ? + 3
Select the correct description of the function f.
a. One-to-one and onto*b. One-to-one but not onto
c. Onto but not one-to-one
d. Neither one-to-one nor onto
41) A = {a, b, c, d}
X = {1, 2, 3, 4}
Each choice defines a function whose domain is A and whose target is X. Select the
function that has a well-defined inverse.
a. f = {(a, 3), (b, 4), (c, 3), (d, 4)}
b. f = {(a, 3), (b, 3), (c, 3), (d, 3)}
*c. f = {(a, 3), (b, 4), (c, 2), (d, 1)}
d. f = {(a, 3), (b, 4), (c, 2), (d, 4)}
42) Select the function that does not have a well-defined inverse.
a. ?: ? → ?
?(?) = ⌈? + 2⌉
b. ?: ? → ?
?(?) = −2? + 5
*c. ?: ? → ?
?(?) = ⌈?⌉
d. ?: ? → ?
?(?) = 3? + 4
43) A and B are finite sets. The function ?: ? → ? is a bijection. Select the true
statement.
a. ? ∘ ?sl = ?
b. ? ∘ ?sl = ?u
*c. ? ∘ ?sl = ?v
d. f may not have a well-defined inverse.44) ?(?) = ?8
?(?) = ⌈?/2⌉
Select the correct value for ? ∘ ?(−3/2) .
a. -1
*b. 0
c. 1
d. 3
[Show More]
.png)
 2e Peter Olver, Chehrzad Shakiban.png)
