CMSC 250, Fall 2021
Midterm #1 Solutions
First & Last Name:
UID (9 digits):
Section number (4 digits):
University Honor Pledge:
I pledge on my honor that I have not given or received
any unauthorized assistance on this assignment/examination.
Please sign or initial below:
NOTES
• Please silence and put away all electronic devices.
• You may not use a calculator.
• Write neatly – if we cannot read your answer, you will receive no credit.
• You have 75 minutes for the exam.
• You may not leave the classroom during the last 5 minutes of the exam.
• You may assume that an Integer + Integer = Integer, and that Integer∗Integer
= Integer.
• You many use only the Laws of Equivalence found in Table 1.
• You may use only the Rules of Inference found in Table 2.
• These tables are on a page attached at the end. Remove that page now!
Your Name:
Problem 1: Statements [Total 12 pts]
Consider the statement:
“If Steve is not the cook, then we are having chicken for dinner.”
Assign:
p : “Steve is the cook”
q : “we are having chicken for dinner”
(a) Write the contrapositive in both English and Statement forms. [4 pts]
English: If we are not having chicken for dinner, then Steve is the cook
Statement: ∼q ⇒ p
(b) Write the converse in both English and Statement forms. [4 pts]
English: If we are having chicken for dinner, then Steve is not the cook
Statement: q ⇒ ∼p
(c) Write the inverse in both English and Statement forms. [4 pts]
English: If Steve is the cook, then we are not having chicken for dinner
Statement: p⇒ ∼q
Your Name:
Problem 2: Arguments [Total 20 pts]
(a) Determine if the following argument is valid using Truth Tables. Indicate the Critical Rows. [10 pts]
p⇒ (q ∧ r)
(p ∧ ∼q)⇒ r
∴ (p ∧ ∼r)⇒ q
p q r q ∧ r p ∧ ∼q p ∧ ∼r p⇒ (q ∧ r) (p ∧ ∼q)⇒ r (p ∧ ∼r)⇒ q Critical row?
T T T T F F T T T Yes
T T F F F T F T T
T F T F T F F T T
T F F F T T F F F
F T T T F F T T T Yes
F T F F F F T T T Yes
F F T F F F T T T Yes
F F F F F F T T T Yes
Valid (circle): yes no
Your Name:
(b) Using only the Rules of Inference found in Table 2 and Laws of Equivalence found in Table 1,
prove the following is valid. Note: c is contradiction, not another variable. [5 pts]
∼(p ∨ q)⇒ z
z ⇒ a
a⇒ c
∴ (p ∨ q)
Various Answers, Here is one:
∼(p ∨ q)⇒ z (1)
z ⇒ a (2)
a⇒ c (3)
∼(p ∨ q)⇒ a (4) Transitivity (1, 2)
∼(p ∨ q)⇒ c (5) Transitivity (3, 4)
∴ (p ∨ q) Contradiction (5)
(c) Using only the Rules of Inference found in Table 2 and Laws of Equivalence found in Table 1,
prove the following is valid. [5 pts]
(∼p ∨ q)⇒ r
r ⇒ (s ∨ t)
∼s ∧ ∼t
∴ p
Various Answers, Here is one:
(∼p ∨ q)⇒ r (1)
r ⇒ (s ∨ t) (2)
∼s ∧ ∼t (3)
(∼p ∨ q)⇒ (s ∨ t) (4) Transitivity (1, 2)
∼(s ∨ t) (5) DeMorgan’s (3)
∼(∼p ∨ q) (6) Modus Tollens (4, 5)
∼∼p ∧ ∼q (7) DeMorgan’s (6)
p ∧ ∼q (8) Double Negation (7)
∴ p Specialization (8)
Your Name:
Problem 3: Number Bases [Total 13 pts]
For each of the following, show the steps you used to arrive at your answer.
(a) Convert: 1425 =?10 [3 pts]
1(5)2 + 4(5)1 + 2(5)0 = 25 + 20 + 2 = 4710
(b) Convert: 101011102 =?8 [3 pts]
1(2)7 + 0(2)6 + 1(2)5 + 0(2)4 + 1(2)3 + 1(2)2 + 1(2)1 + 0(2)0 = 128 + 32 + 8 + 4 + 2 = 17410
174÷ 8 = 21 R 6
21÷ 8 = 2 R 5
2÷ 8 = 0 R 2
so 101011102 = 17410 = 2568
or
23 = 8, so 0102 = 2, 1012 = 5, 1102 = 6, thus 101011102 = 2568
(c) Convert: 9610 =?7 [3 pts]
96÷ 7 = 13 R 5
13÷ 7 = 1 R 6
1÷ 7 = 0 R 1
so 9610 = 1657
Your Name:
(d) Add: 21024 + 3234 =?4 [4 pts]
1 1
2 1 0 2
+ 3 2 3
3 0 3 1
so 21024 + 3234 = 30314
Your Name:
Problem 4: Parity [Total 6 pts]
Using the definitions given in lecture, show the following statements.
(a) Show that 238 is not odd. [2 pts]
If 238 is odd, then 238 = 2k + 1 where k is an integer. No such integer exists for this equation
to work.
(b) Show informally that when an even number is added to a product of two odd numbers the
resulting value is odd. [4 pts]
The product of two odd numbers can be represented as (2p + 1)(2q + 1) = 4pq + 2p + 2q + 1.
We then want to add an even number. An even number is one which can be written as 2k where k
is an integer. Thus (odd*odd) + even is 4pq + 2p + 2q) + 1 + 2k = 2(2pq + p + q + k) + 1. Since we
can assume an integer * interger = integer, and integer + integer = integer, then 2pq + p + q + k
is an integer. Hence an even number added to the product of two odd numbers can be written as
2m + 1, where m = 2pq + p + q + k and m is an integer. 2m + 1 is the definition of an odd number
so an even number added to the product of two odd numbers is odd
Problem 5: Primes and Composites [Total 6 pts]
Are the following numbers prime, composite or neither? Justify your answer using the definitions
used in class.
(a) 51 [2 pts]
51 is not prime as it has a positive divisor that is not 1 nor 51. That positive divisor being 3 (or 17)
(b) -546 [2 pts]
-546 is neither prime nor composite because we said any integer ≤ 1 is neither prime nor composite.
And -546 is less than 1.
(c) 17 [2 pts]
17 is prime as the only positive divisors are 1 and 17.
Your Name:
Problem 6: Divisibility [Total 6 pts]
Are the following statements true or false? Justify your answer using the definitions used in class.
(a) 3|87 [2 pts]
3|87 by definition means there is some integer k such that 3k = 87. Since there is some integer,
k = 29, this is true.
(b) −17|35 [2 pts]
−17|25 by definition means there is some integer k such that −17k = 35. Since there is no such
integer that makes this equation true, this statement is false.
(c) 4 – 15 [2 pts]
4 – 15 by definition means there is no integer k such that 4k = 15. Since there is no such integer
that makes this equation true, this statement is true.
Problem 7: Modular Arithmetic in CS [Total 6 pts]
What are the following values? Justify your answer using the definitions used in class
(a) 332 mod 3 = ? [2 pts]
332 mod 3 = r in equation 332 = 3k + r, where 0 ≤ r ≤ 3 by definition. The only k and r that
make this equation work are k = 110, r = 2. Thus 332 mod 3 = 2.
(b) -49 mod 11 = ? [2 pts]
-49 mod 11 = r in equation −49 = 11k + r, where 0 ≤ r ≤ 11 by definition. The only k and r that
make this equation work are k = −5, r = 6. Thus -49 mod 11 = 6.
(c) 4 mod 12 = ? [2 pts]
4 mod 12 = r in equation 4 = 12k + r, where 0 ≤ r ≤ 12 by definition. The only k and r that make
this equation work are k = 0, r = 4. Thus 4 mod 12 = 4.
Your Name:
Problem 8: Modular Arithmetic in Math [Total 6 pts]
Are the following true or false? Justify your answer using the definitions used in class.
(a) 49 ≡ 14 (mod 7) [2 pts]
By definition, 49 ≡ 14(mod 7) if 7|(49− 14) or 7|35. Since 7(5) = 35, this is true.
(b) 127 ≡ −13 (mod 11) [2 pts]
By definition, 127 ≡ −13(mod 11) if 11|(127 + 13) or 11|140. Since 11 – 140, this is false.
(c) 49 ≡ 14 (mod 5) [2 pts]
By definition, 49 ≡ 14(mod 5) if 5|(49− 14) or 5|35. Since 5(7) = 35, this is true.
Your Name:
Problem 9: Circuits [Total 15 pts]
(a) Circuit to Statement [5 pts]
What statement is computed by the following circuit? Do not simplify.
p
q
r
Statement:(∼(p ∨ ∼p) ∧ ∼(((p ∨ ∼p) ∧ r) ∧ (∼p ∨ (q ∧ ∼q)))) ∨ r
Your Name:
(b) Table to circuit [10 pts]
Given the the following input-output table, what is the statement and its corresponding circuit?
Use the methods shown in lecture and do not simplify either.
p q r Output
1 1 1 0
1 1 0 1
1 0 1 0
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 0
Statement:(p ∧ q ∧ ∼r) ∨ (∼p ∧ q ∧ ∼r)
Circuit:
p
q
r
Your Name:
Problem 10: Challenge Question [Total 10 pts]
Let 0 ≤ n ≤ 15 be represented in binary by n = XY ZW2. Draw a circuit which takes the four input
bits X, Y , Z, and W and outputs 1 if n ≡ 1 (mod 8) or n ≡ 3 (mod 8) and outputs 0 otherwise.
Hint 1: What do such numbers look like in binary?
Hint 2: It can be done with 5 or fewer gates.
Note that in this case, n = 1 ∨ n = 3,∨n = 9,∨n = 11. In binary, (or convert from base 10
to base 2), we should get 0001, 0011, 1001, 1011. Thus we need to have a circuit that represents
(∼x∧∼y∧∼z∧w)∨ (∼x∧∼y∧z∧w)∨ (x∧∼y∧∼z∧w)∨ (x∧∼y∧z∧w). Any circuit that shows
this would work. However, if you wanted to simplify this expression, you would get something like
∼y ∧ w. (Notice that the second bit (y) is always 0, and that the parity bit (the bit that make the
number odd or even aka w), is always 1). Then notice that x and z can be either 1 or 0.)
So to do this circuit with 4 inputs and 1 output (as asked), in 5 gates means having ∼y ∧ w and
then somehow getting rid of x and z. Recall (p∧ q)∨p ≡ p via the absorbtion laws. This is one such
way of getting of a variable (or input). Thus, the simplest gate (that we can find) is the following:
Y
W
X
Z
Tables!
Commutative Laws p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Associative Laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive Laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Identity Laws p ∧ t ≡ p p ∨ c ≡ p
Negation Laws p ∨ ∼p ≡ t p ∧ ∼p ≡ c
Double Negation Law ∼(∼p) ≡ p
Idempotent Laws p ∧ p ≡ p p ∨ p ≡ p
Universal Bound Laws p ∨ t ≡ t p ∧ c ≡ c
DeMorgan’s Laws ∼(p ∧ q) ≡ ∼p ∨ ∼q ∼(p ∨ q) ≡ ∼p ∧ ∼q
Absorption Laws p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
Negation Laws of t and c ∼t ≡ c ∼c ≡ t
Definition of Implication p⇒ q ≡ ∼p ∨ q
Definition of Biconditional p⇔ q ≡ (p⇒ q) ∧ (q ⇒ p) ≡ (p ∧ q) ∨ (∼p ∧ ∼q)
Contrapositive p⇒ q ≡ ∼q ⇒ ∼p
Table 1: Laws of Equivalence
Modus Ponens Modus Tollens Generalization
p⇒ q
p
∴ q
p⇒ q
∼q
∴ ∼p
p
∴ p ∨ q
Specialization Conjunction Elimination
p ∧ q
∴ p
p
q
∴ p ∧ q
p ∨ q
∼p
∴ q
Transitivity Cases Contradiction
p⇒ q
q ⇒ r
∴ p⇒ r
p ∨ q
p⇒ r
q ⇒ r
∴ r
∼p⇒ c
∴ p
Table 2: Rules of Inference