[1] 1.
[4] 2.
CPSC 121 Midterm 1 Wednesday 31 May 2017
Prove
Solution: √16=4=4 ∈Q.
1
Solution : Assume √4 15 ∈ Q.
⇒ √4 15 = a for some a,b ∈ Z, which can be reduced such that a,b share no common
b
A Quick Start
I’m Feeling Irrational Prove √4 15 ̸∈ Q.
√
16 ∈ Q.
[1] 3.
[1] 4.
[2] 5.
⇒a4 =3·5·b4 (1) ⇒ a4 has prime factors of 3 and 5
⇒ a has prime factors of 3 and 5, by the Fundamental Theorem of Arithmetic
⇒ a = 3 · 5 · k for some k ∈ Z (2) ⇒(3·5·k)4 =3·5·b4 by(1),(2)
⇒ 33 · 53 · k4 = b4
⇒ b4 has prime factors of 3 and 5
⇒ b has prime factors of 3 and 5, by the Fundamental Theorem of Arithmetic ⇒ a and b share common factors
This Exam is Divided Into Questions Prove 3 | 18.
Solution: 18=3·6
Winter is Coming
If Jon Snow lives in Winterfell, then Jon Snow lives in the North. Jon Snow lives in the North. What do we know about whether Jon Snow lives in Winterfell?
Solution : He may live in Winterfell, but we do not know for certain whether he does or not.
More Division is Coming
Prove that if 18 | n for some n ∈ Z, then 6 | n.
factors
⇒ 15 = a4
b4 ⇒ 15b4 = a4
[2] 6.
Solution : Let n ∈ Z be some value, for which 18 | n ⇒ n = 18k for some k ∈ Z
⇒n=3·6·k
⇒ n = 6j for some j ∈ Z, namely j = 3k
Build Us a Circuit
Write both a logical expression and a circuit representation for the following function, which is given in truth-table format. (Note: no points are awarded for optimizing the circuit to minimize the number of gates.)
a b c f(a,b,c) 000 0 001 0 010 0 011 1 100 1 101 0 110 1 111 0
Solution : Using DNF form:
(∼ a ∧ b ∧ c) ∨ (a∧ ∼ b∧ ∼ c) ∨ (a ∧ b∧ ∼ c)
How Many Segments?
In class, we created a seven-segment display to display ten different digits. But, such a design is not optimized, in that it uses more segments than necessary to display ten different outputs. Imagine our number system were base-43. How many different segments would we need, at a minimum, to display our different symbols? Justify your answer.
Solution: 25 = 32 < 43, so 5 segments would not suffice. But 26 = 64 ≥ 43, so 6 segments does suffice, making 6 segments the minimal number required.
(Alternately: you could justify your answer by noting ⌈log2 43⌉ = 6.)
[2] 7.
[2] 8.
Which is It?
Is the following a tautology, a contradiction, or a contingency? Justify your answer. a ⊕ b ↔ (a∧ ∼ b) ∨ (∼ a ∧ b)
Solution : It is a tautology.
a ⊕ b ↔ (a∧ ∼ b) ∨ (∼ a ∧ b)
≡ (a∧ ∼ b) ∨ (∼ a ∧ b) ↔ (a∧ ∼ b) ∨ (∼ a ∧ b) by the definition of ⊕.
Define p = (a∧ ∼ b) ∨ (∼ a ∧ b).
Then, our statement is equivalent to p ↔ p, which is a tautology from the truth table for ↔.
A Circuit That Recognizes Two Things
Design a circuit that takes in two 3 bit unsigned numbers, and returns true if and only if: the two numbers are equivalent, or if the two numbers differ by 4 and are both even.
[2] 9.
Solution :
[1] 10. What Does this Word Mean?
Define the following two propositions:
• r ≡ it is raining
• b ≡ Ryan is going to the beach
Translate the following into propositional logic: it is raining, but Ryan is going to the beach.
Solution : r ∧ b
[2] 11. A More General Multiplexer
In class, we designed a multiplexer that took three inputs: a and b, and a “choice” wire c to choose between a and b as the output. But, more generally, we could have a multiplexer with, e.g., 26 inputs, a through z, and multiple wires carrying a “choice” input. How many “choice” wires would you need to select from 26 inputs? Justify your answer.
Solution: 24 = 16 < 26, so 4 choice inputs would not suffice. But 25 = 32 ≥ 26, so 5 choice inputs do suffice, making 5 choice inputs the minimal number required.
(Alternately: you could justify your answer by noting ⌈log2 26⌉ = 5.)
[4] 12. Why We Use It
Assume we have 4 bits to represent a signed number, and we are using 2’s-complement representation. Prove that the sum of any value v, and its negative value −v in four- bit 2’s-complement, equates to all-zero bits, as computed by a four-bit ripple-carry adder.
Solution : Let v be some value representable in 4-bit 2’s-complement.
Define f to be v with all its bits flipped
⇒ v + f is made up of all 1 bits (because the sum of every bit-pair is 0+1 or 1+0) Note: v+(f+1)=(v+f)+1
(v + f) + 1 (i.e., all 1-bits plus 1), when computed through a ripple-carry adder, produces 0.
Therefore, flipping all the bits and adding 1 — i.e., computing f+1 — produces a negative representation in which addition works as expected in a ripple-carry adder.
[2] 13. Fixed-Point Fun
Prove that you can represent 1 in fixed-point base-16.
8
Solution: 1 = 2 = n forsomen,d∈Z(namely,n=2,d=1). 8 161 16d
[4] 14. More Fixed-Point Fun
Prove that there are numbers representable in fixed-point base-6 that cannot be rep- resented in fixed-point base-10.
Solution : We can represent 1 in fixed-point base-6, namely as 1 . 6 61
Now, we will prove you cannot represent 1 in fixed-point base-10 by contradiction. 6
Assume that you can represent 1 in fixed-point base-10.
6
⇒ 2d−1·5d = n by the Fundamental Theorem of Arithmetic (since 2, 3, and 5 are 3
prime)
Therefore, you can represent 1 in fixed-point base-6, but not in fixed-point base-10
6
[4] 15. The Fun Doesn’t Stop
Prove that every number representable in fixed-point base-8 can also be represented in fixed-point base-16.
Solution : Let v be a value representable in fixed-point base-8. ⇒v= n forsomen,d∈Z
⇒1=n forsomen,d∈Z 6 10d
⇒10d =n 6
⇒2d·5d =n 2·3
8d = n·2d
8d ·2d = n·2d 16d
= k forsomek∈Z(namelyk=n·2d) 16d
Therefore, v can be represented in fixed-point base-16.