Class notes
CPSC 121 Assignment 1 Solutions 2021
- Course
- CPSC 121
- Institution
- University Of British Columbia (UBC )
CPSC 121 Assignment 1 Solutions
[Show more]
Content preview
CPSC 121 2021S2HW 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller travissmith1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for CA$22.47. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75632 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now