CPSC 121 2021S2
HW 1
Solutions
Instructions:
1. Do not change the problem statements we are giving you. Simply add your
solutions by editing this latex document. To make it easier for the TAs to find
your solutions, please use the soln environment we provided as follows:
\begin{soln}
My solution is here.
\end{soln}
Your solution will then appear in blue, and be easier to differentiate from the
questions.
2. If you need more space, add a page between the existing pages using the
\newpage command.
3. Export the completed assignment as a PDF file for upload to gradescope.
4. On Gradescope, upload only one copy per partnership. You must identify
you group via Gradescope, not doing so may result in loosing some marks
5. You must also tell us, via Gradescope, where each of the problem parts
appears on your submission. You MUST align the regions for every problem,
even if your assignment solution isn’t complete. We will not be able to mark
any problem we can’t find. After uploading the .pdf you will a screen, where
you can click each question on the left, and click the corresponding page(s) for
which the question appears in. Because of this matching process, please allocate
at least 5 minutes prior to the deadline for submission. You must match your
answers with each question, not doing so may result in loosing some marks.
Academic Conduct: I certify that my assignment follows the academic
conduct rules for of CPSC 121 as outlined on the course website. As part of
those rules, when collaborating with anyone outside my group, (1) I and my
collaborators took no record but names away, and (2) after a suitable break,
my group created the assignment I am submitting without help from anyone
other than the course staff.
1
, CPSC 121 2021S2
1. [8 marks] For this question, you will prove that every truth table can be implemented
by a circuit that uses only 2-to-1 multiplexers. See your lecture slides (Module 3) for a
propositional logic definition and truth table for a 2-to-1 multiplexer.
a. [2 marks] Show that ∼ can be simulated using a 2-to-1 multiplexer. That is, design
a circuit whose only component is a 2-to-1 multiplexer, that takes as input a signal x
along with optional constant-0 or constant-1 values, and whose output is ∼ x.
b. [2 marks] Show that ∧ can be simulated using 2-to-1 multiplexers. That is, design a
circuit whose only component is a 2-to-1 multiplexer, that takes as inputs two signals
x and y along with optional constant-0 or constant-1 values, and whose output is x ∧ y.
c. [2 marks] Show that ∨ can be simulated using 2-to-1 multiplexers. That is, design a
circuit whose only component is a 2-to-1 multiplexer, that takes as inputs two signals
x and y along with optional constant-0 or constant-1 values, and whose output is x ∨ y.
d. [2 marks] The 2-to-1 multiplexer is more powerful than simply being able to simulate
the AND, OR, and NOT logic functions. Any arbitrary truth table in 2 variables (i.e. 4
rows) can be constructed using at most two 2-to-1 multiplexers. Design a circuit whose
only components are 2-to-1 multiplexers, that takes as inputs two signals x and y along
with optional constant-0 or constant-1 values, and whose output is ∼(x⊕y) (exclusive-
NOR).
Since for every truth table over k atomic propositions, we can write a propositional formula
that matches the truth table using ∼, ∨ and ∧, your answers to parts (a), (b) and (c)
show that you can implement any specified logic function with a circuit that uses only
2-to-1 multiplexers.
Solution for all parts:
2
HW 1
Solutions
Instructions:
1. Do not change the problem statements we are giving you. Simply add your
solutions by editing this latex document. To make it easier for the TAs to find
your solutions, please use the soln environment we provided as follows:
\begin{soln}
My solution is here.
\end{soln}
Your solution will then appear in blue, and be easier to differentiate from the
questions.
2. If you need more space, add a page between the existing pages using the
\newpage command.
3. Export the completed assignment as a PDF file for upload to gradescope.
4. On Gradescope, upload only one copy per partnership. You must identify
you group via Gradescope, not doing so may result in loosing some marks
5. You must also tell us, via Gradescope, where each of the problem parts
appears on your submission. You MUST align the regions for every problem,
even if your assignment solution isn’t complete. We will not be able to mark
any problem we can’t find. After uploading the .pdf you will a screen, where
you can click each question on the left, and click the corresponding page(s) for
which the question appears in. Because of this matching process, please allocate
at least 5 minutes prior to the deadline for submission. You must match your
answers with each question, not doing so may result in loosing some marks.
Academic Conduct: I certify that my assignment follows the academic
conduct rules for of CPSC 121 as outlined on the course website. As part of
those rules, when collaborating with anyone outside my group, (1) I and my
collaborators took no record but names away, and (2) after a suitable break,
my group created the assignment I am submitting without help from anyone
other than the course staff.
1
, CPSC 121 2021S2
1. [8 marks] For this question, you will prove that every truth table can be implemented
by a circuit that uses only 2-to-1 multiplexers. See your lecture slides (Module 3) for a
propositional logic definition and truth table for a 2-to-1 multiplexer.
a. [2 marks] Show that ∼ can be simulated using a 2-to-1 multiplexer. That is, design
a circuit whose only component is a 2-to-1 multiplexer, that takes as input a signal x
along with optional constant-0 or constant-1 values, and whose output is ∼ x.
b. [2 marks] Show that ∧ can be simulated using 2-to-1 multiplexers. That is, design a
circuit whose only component is a 2-to-1 multiplexer, that takes as inputs two signals
x and y along with optional constant-0 or constant-1 values, and whose output is x ∧ y.
c. [2 marks] Show that ∨ can be simulated using 2-to-1 multiplexers. That is, design a
circuit whose only component is a 2-to-1 multiplexer, that takes as inputs two signals
x and y along with optional constant-0 or constant-1 values, and whose output is x ∨ y.
d. [2 marks] The 2-to-1 multiplexer is more powerful than simply being able to simulate
the AND, OR, and NOT logic functions. Any arbitrary truth table in 2 variables (i.e. 4
rows) can be constructed using at most two 2-to-1 multiplexers. Design a circuit whose
only components are 2-to-1 multiplexers, that takes as inputs two signals x and y along
with optional constant-0 or constant-1 values, and whose output is ∼(x⊕y) (exclusive-
NOR).
Since for every truth table over k atomic propositions, we can write a propositional formula
that matches the truth table using ∼, ∨ and ∧, your answers to parts (a), (b) and (c)
show that you can implement any specified logic function with a circuit that uses only
2-to-1 multiplexers.
Solution for all parts:
2
