Coursera

Warning: You have already made the maximum number of submissions. Additional submissions will not count for credit. You are welcome to try it as a learning exercise.

This is the graded quiz for Combinational Digital Systems.

This quiz does contribute to your final grade.

You have one attempt only for this quiz.

You should do at least one practice quiz for this topic before you attempt this graded quiz.

Please read the following instructions carefully.

____________________________

This quiz has a total of 20 marks from 5 questions.

Question 1: (3 marks) Given a functional description of the behaviour of the output(s) of a combinational digital system in terms of the inputs, complete a truth table column for each output of the system. As a multiple choice, select which (if any) of several truth tables are correct.

For question one (1), you may want to print off and use this PDF file containing a blank truth to use in evaluating the correct answer.

Question 2:( 4 marks) Read a circuit diagram for a combinational digital system, and select from a list the one set of propositional logic formulas expressing each of the output signals in terms of the inputs which correspond exactly to the circuit diagram as given.

Question 3: (4 marks) Given a minimal DNF formula for each system output expressed in terms of the inputs, select which one of several K-maps correspond exactly to those DNF formulas.

Question 4: (4 marks) Given a truth table for combinational digital system, and with further use of K-maps for each output, select which one or more sets of propositional logic formulas give correct DNF characterisations of the outputs in terms of the inputs.

Question 5: (5 marks) Given a circuit diagram for a combinational digital system, use K-maps to determine whether or not that circuit is minimal DNF for the system.

For question five (5), you may want to print off and use this PDF file containing blank K-maps to use in working out the correct answer.

In accordance with the Coursera Honor Code, I (Anonymous Student) certify that the answers here are my own work.

Question 1

You are to design a digital system to assess the values of 2-bit binary numbers. The system has two 2-bit inputs p = p1 p0 and q = q1 q0, and two 1-bit outputs z and w. The 2-bit inputs take one of four values, 00, 01, 10 and 11, which are the 2-bit binary representations of the decimal numbers 0, 1, 2 and 3, respectively. The 1-bit output z is to have value 1 if and only if p is less than or equal to q in the normal ordering, while the output w is to have value 1 if and only if p is greater than or equal to q in the normal ordering.

Identify which (if any) of these truth tables are correct for this functional description?

tables

Question 2

This circuit diagram is for a combinational system with input signals p, q, r and s, and output signals z and w. The “ $\times$ 1” label merely indicates these are 1-bit signals, and is an artefact of the software used to generate the circuit diagram.

tables

Identify which one of these pairs of logic formulas correctly characterise the outputs z and w in terms of the inputs p, q, r and s, exactly as they are in the circuit diagram?

(a)

$z \equiv (\mathord\sim p \, \& \, r) \lor (r \, \& \, \mathord\sim s) \lor (q \, \& \, \mathord\sim s) \\ w \equiv (\mathord\sim r \, \& \, \mathord\sim s) \lor (q \, \& \, \mathord\sim s) \lor (p \, \& \, \mathord\sim r) \lor (p \, \& \, q \, \& \, \mathord\sim s)$

(b)

(c)

$z \equiv (\mathord\sim p \, \& \, r) \lor (r \, \& \, \mathord\sim s) \lor (q \, \& \, \mathord\sim s) \\ w \equiv (\mathord\sim r \, \& \, \mathord\sim s) \lor (q \, \& \, \mathord\sim s) \lor (\mathord\sim p \, \& \, r) \lor (p \, \& \, \mathord\sim q \, \& \, s)$

(d)

$z \equiv (\mathord\sim p \, \& \, r) \lor (\mathord\sim r \, \& \, s) \lor (q \, \& \, \mathord\sim s) \\ w \equiv (\mathord\sim r \, \& \, \mathord\sim s) \lor (q \, \& \, \mathord\sim s) \lor (p \, \& \, \mathord\sim r) \lor (p \, \& \, \mathord\sim q \, \& \, s)$

Question 3

Consider a combinational system with inputs p, q, r and s, and outputs z and w, where the outputs are characterised by minimal DNF formulas in terms of the inputs, as follows:

$z \equiv (\mathord\sim p \, \& \, \mathord\sim q \, \& \, r) \lor ( \mathord\sim p \, \& \, q \, \& \, s) \lor ( q \, \& \, \mathord\sim r \, \& \, s) \lor ( p \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \\ w \equiv (\mathord\sim p \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \lor ( \mathord\sim p \, \& \, \mathord\sim q \, \& \, r) \lor ( q \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \lor ( p \, \& \, q \, \& \, s)$

Which one of the following pairs of looped K-maps correspond to these two minimal DNF formulas?

There is such a correspondence when for each of the outputs z and w, every loop in the K-map for that output is matched up with exactly one of the conjunctions within the DNF formula for that output, so that the conjunction describes only the loop that is its match.

tables

(a)

(b)

(c)

(d)

Question 4

A combinational system with input signals p, q, r and s, and output signals z and w, is described by the following truth table:

tables

Identify which one or more of these pairs of logic formulas correctly characterise the outputs z and w in terms of the inputs p, q, r and s via DNF formulas?

You may wish to complete and use the K-maps for z and w.

(a)

$z \equiv (\mathord\sim p \, \& \, \mathord\sim q \, \& \, r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, \mathord\sim r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, \mathord\sim r \, \& \, s) \\ w \equiv (\mathord\sim p \, \& \, q \, \& \, \mathord\sim r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, r \, \& \, s) \lor (p \, \& \, \mathord\sim q \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \\ \qquad \lor\, (p \, \& \, \mathord\sim q \, \& \, r \, \& \, \mathord\sim s) \lor (p \, \& \, q \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \lor (p \, \& \, q \, \& \, r \, \& \, \mathord\sim s)$

(b)

$z \equiv (\mathord\sim p \, \& \, \mathord\sim q \, \& \, r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, \mathord\sim r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, r \, \& \, s) \\ w \equiv (\mathord\sim p \, \& \, q \, \& \, \mathord\sim r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, r \, \& \, s) \lor (p \, \& \, \mathord\sim q \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \\ \qquad \lor\, (p \, \& \, \mathord\sim q \, \& \, r \, \& \, \mathord\sim s) \lor (p \, \& \, q \, \& \, \mathord\sim r \, \& \, \mathord\sim s) \lor (p \, \& \, q \, \& \, r \, \& \, \mathord\sim s)$

(c)

$z \equiv (\mathord\sim p \, \& \, r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, s) \\ w \equiv (\mathord\sim p \, \& \, q \, \& \, \mathord\sim s) \lor (p \, \& \, \mathord\sim s)$

(d)

$z \equiv (\mathord\sim p \, \& \, r \, \& \, s) \lor (\mathord\sim p \, \& \, q \, \& \, s) \\ w \equiv (\mathord\sim p \, \& \, q \, \& \, s) \lor (p \, \& \, \mathord\sim s)$

Question 5

Consider the circuit diagram below for a combinational system with input signals p, q, r and s, and output signals z and w. The circuit is in standard DNF form. (As before, in Question 2, the “ $\times$ 1” label merely indicates these are 1-bit signals.) It has a total of 7 AND gates with a total input-count of 21 across those AND gates, where the total input-count for a set of gates is the result of adding up the input-size of each of the gates.

tables

We say a circuit diagram is a minimal DNF circuit for a combinational system if and only it is in standard DNF form and every other circuit diagram in standard DNF form that implements the same system has at least as many AND gates, and those AND gates have a total input-count at least as large as that of the given circuit diagram. Equivalently, a circuit diagram in standard DNF form is not a minimal DNF circuit for a combinational system if and only if there is another circuit diagram in standard DNF form implementing the same system that either has a smaller number of AND gates, or has the same number of AND gates but the total input-count of those AND gates is smaller than that of the given circuit diagram.

To answer this question, you should first complete K-maps for the two outputs of this system using the AND gates in the given circuit diagram (using the blank K-maps supplied in the attached worksheet). Then on a second set of K-maps with the same pattern of 1s, consider whether or not there is a better way of doing the looping, so as to result in a smaller circuit.

Identify which one of the following statements is correct.

(a) The circuit diagram above is a minimal DNF circuit for this combinational system.

(b) The circuit diagram above is not a minimal DNF circuit for this system because there is another DNF circuit for the same system with less than 7 AND gates.

(c) The circuit diagram above is not a minimal DNF circuit for this system because there is another DNF circuit for the same system which has 7 AND gates with a total input-count of less than 21.

In accordance with the Coursera Honor Code, I (Anonymous Student) certify that the answers here are my own work.

You cannot submit your work until you agree to the Honor Code. Thanks!

Logic: Language and Information 1

Top Navigation Bar

Logic: Language and Information 1
by Prof. Greg Restall, Dr Jen Davoren

Side Navigation Bar

Study resources

Assessments

Additional resources