Problem Set 2
Contents
Problem Set 2#
Source: DL_P2.pdf Revision: 2/3/19
Warning
The overline symbol (A̅) may be hidden in Firefox if the default zoom level is used. The symbol below should have an overline like A̅. De or increase the zoom level if you encounter any Boolean equations.
\( \overline A \)
1#
Complete the truth tables below.
AND
#
A 
B 
F 

0 
0 
0 
0 
1 
0 
1 
0 
0 
1 
1 
1 
OR
#
A 
B 
F 

0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
1 
1 
XOR
#
A 
B 
F 

0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
1 
0 
INV
#
A 
F 

0 
1 
1 
0 
2#
Sketch nonminimized SOP and POS circuits for the truth table below.
A 
B 
C 
F 

0 
0 
0 
0 
0 
0 
1 
1 
0 
1 
0 
0 
0 
1 
1 
1 
1 
0 
0 
1 
1 
0 
1 
1 
1 
1 
0 
0 
1 
1 
1 
0 
SOP:
For SOP we look at the conditions which lead to a 1
and combine them using OR
:
\( F = ( \overline{A} \cdot \overline{B} \cdot C ) + ( \overline{A} \cdot B \cdot C ) + ( A \cdot \overline{B} \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot C ) \)
POS:
For POS we look at the conditions which lead to a 0
. In an AND
chain we only get a 1
if all the components are 1
, otherwise zero. So if none of these conditions is 1
then the output is 1
. So we should make sure that the individual conditions that lead to a 0
should lead to 0
if the condition is 1
. We can achieve that by negating the condition:
Let C
be the a condition that must lead to a 0
or must be False
and A
and B
the inputs:
\(
C = A \cdot B = \mathrm{False} \Rightarrow \overline{A \cdot B} = \overline{\mathrm{False}} \Rightarrow \overline{A} + \overline{B} = \mathrm{True}
\)
\( F = ( A + B + C ) \cdot ( A + \overline{B} + C ) \cdot ( \overline{A} + \overline{B} + C ) \cdot ( \overline{A} + \overline{B} + \overline{C} ) \)
3#
Complete the truth tables and provide minterm equations.
3.1#
\(F = \overline{A} \cdot B + C \)
A 
B 
C 
F 

0 
0 
0 

0 
0 
1 

0 
1 
0 

0 
1 
1 

1 
0 
0 

1 
0 
1 

1 
1 
0 

1 
1 
1 
A 
B 
C 
F 

0 
0 
0 
0 
0 
0 
1 
1 
0 
1 
0 
1 
0 
1 
1 
1 
1 
0 
0 
0 
1 
0 
1 
1 
1 
1 
0 
0 
1 
1 
1 
1 
\( F = ( \overline{A} \cdot \overline{B} \cdot C ) + ( \overline{A} \cdot B \cdot \overline{C} ) + ( \overline{A} \cdot B \cdot C ) + ( A \cdot \overline{B} \cdot C ) + ( A \cdot B \cdot C ) \)
3.2#
\( F = A \cdot B \cdot \overline{C} + B \cdot C \)
A 
B 
C 
F 

0 
0 
0 

0 
0 
1 

0 
1 
0 

0 
1 
1 

1 
0 
0 

1 
0 
1 

1 
1 
0 

1 
1 
1 
A 
B 
C 
F 

0 
0 
0 
0 
0 
0 
1 
0 
0 
1 
0 
0 
0 
1 
1 
1 
1 
0 
0 
0 
1 
0 
1 
0 
1 
1 
0 
1 
1 
1 
1 
1 
\( F = ( \overline{A} \cdot B \cdot C ) + ( A \cdot B \cdot \overline{C} ) + ( A \cdot B \cdot C ) \)
3.3#
\(F = B \cdot \overline{C} + \overline{B} \cdot C \)
A 
B 
C 
F 

0 
0 
0 

0 
0 
1 

0 
1 
0 

0 
1 
1 

1 
0 
0 

1 
0 
1 

1 
1 
0 

1 
1 
1 
A 
B 
C 
F 

0 
0 
0 
0 
0 
0 
1 
1 
0 
1 
0 
1 
0 
1 
1 
0 
1 
0 
0 
0 
1 
0 
1 
1 
1 
1 
0 
1 
1 
1 
1 
0 
\( F = ( \overline{A} \cdot \overline{B} \cdot C ) + ( \overline{A} \cdot B \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot C ) + ( A \cdot B \cdot \overline{C} ) \)
4#
Write the number of transistors required for each logic gate below inside the gate symbol, and then write the logic gate name below the symbol.
Note
The number of transistors can vary dependent on the semiconductor technology. Most likely the author means the number of transistor required in CMOS technology.
4.1#
When we push the bubbles to the output, we get a NOR
:
We need four transistors.
If we have two inputs, remember that we can connect two NFET transistors in series to the ground to build a logical gate. To have a logical zero, we have to activate them both. This corresponds to the NAND
logic. In CMOS we complement the NFETs with PFETs. NOR
is like NAND
an additional logic gate that we can build using four transistors. In NOR
we have two NFETs in parallel to the ground.
Besides NOR
and NAND
we can also build a NOT
using a single NFET to the ground and complementing that. If we activate the NFET the gate will output a zero, and thus invert our input. We need two transistors in total.
4.2#
This is an OR
. We need six transistors.
In CMOS the logic gates that we can build using minimal number of transistors are NOT
, NAND
and NOR
. We build other functions using these elementary gates.
To get an OR
, we have to connect an additional inverter (NOT
) after the NOR
. So we need \(4+2=6\) transistors.
4.3#
Three input NAND
. We need six transistors.
In 4.1 we already explained how to build a NAND
. Instead of two inputs now we have three inputs. So we have three NFETs in series connected to the ground and these transistors are complemented with three PFETs above which are in parallel to the supply rail.
4.4#
This is a NOT
. As discussed in 4.1 we need two transistors.
4.5#
This is a two input NOR
, we need four transistors. Same as 4.1.
4.6#
After bubblepushing we get a three input NAND
. We need six transistors, similar to ps02.4.3
.
5#
assign F = (A & ~B)  (~A & ~C)  (A & B & C)
Complete the following truth table based on the Verilog assignment statement
Write the minterm equation for F.
Write the maxterm equation for F.
A 
B 
C 
F 

0 
0 
0 

0 
0 
1 

0 
1 
0 

0 
1 
1 

1 
0 
0 

1 
0 
1 

1 
1 
0 

1 
1 
1 
We can fill the truth table from the Verilog line above by extending the first two products with the missing third variable which can be both 0
and 1
. In other words, we do not care what C
and B
are in the first and second term, respectively.
A 
B 
C 
F 

0 
0 
0 
1 
0 
0 
1 
0 
0 
1 
0 
1 
0 
1 
1 
0 
1 
0 
0 
1 
1 
0 
1 
1 
1 
1 
0 
0 
1 
1 
1 
1 
Minterm equation:
\( F = \mathrm{m}_0 + \mathrm{m}_2 + \mathrm{m}_4 + \mathrm{m}_5 + \mathrm{m}_7 \)
or in short:
\( F = \sum_{n=\left\{0,2,4,5,7\right\}} \mathrm{m}_n \)
If we wanted to write the terms out:
\( F = ( \overline{A} \cdot \overline{B} \cdot \overline{C} ) + ( \overline{A} \cdot B \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot \overline{C} ) + ( A \cdot \overline{B} \cdot C ) + ( A \cdot B \cdot C ) \)
Maxterm equation:
\( F = \prod_{n=\left\{1,3,6\right\}} \mathrm{m}_n \)
If we wanted to write all the terms out:
\( F = ( A + B + \overline{C} ) \cdot ( A + \overline{B} + \overline{C} ) \cdot ( \overline{A} + \overline{B} + C ) \)
6#
Sketch circuits and write Verilog assignment statements for the following logic equations.
Note
Sketching circuits based on logic gate symbols is enough. You can also draw circuits based on CMOS for a challenge.
6.1#
\( F = \overline{A} \cdot B \cdot C + A \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot C \)
module m (output F, input A,B,C);
assign F = ~A & B & C  A & ~B & ~C  ~A & C;
endmodule
CMOS circuit:
6.2#
\( F = \overline{ \overline{A} \cdot B \cdot \overline{C} } + \overline{ A + B } \)
module m (output F, input A,B,C);
assign F = ~(~A & B & ~C)  ~(A  B);
endmodule
6.3#
\( F = ( A + \overline{B} ) \cdot \overline{ \overline{B + C} \cdot \overline{A} } \)
module m (output F, input A,B,C);
assign F =
(A  ~B) &
~(~(~B  C) & A);
endmodule
6.4#
\( F = \sum \mathrm{m}(1, 2, 6) \)
This is a sum of three minterms (we have three arguments) with three inputs (the arguments go up to 6, so we have \(\lceil \log_{2} 6 \rceil = 3\) inputs).
Why three inputs? Because the output is obviously not dependent on further (e.g., fourth, fifth) inputs as the output apparently does not change if these further inputs are high (otherwise we would have higher numbers than 7 in our F
)
module m (output F, input A,B,C);
assign F = (~A & ~B & C) 
(~A & B & ~C) 
( A & B & ~C);
endmodule
6.5#
\( F = \prod \mathrm{M}(0, 7) \)
This is a product of two maxterms with three inputs.
module m (output F, input A,B,C);
assign F = ( A & B & C) &
(~A & ~B & ~C);
endmodule
7#
In a logic function with \(n\) inputs, there are \(2𝑛\) unique combinations of inputs and \(2^{2^𝑛}\) possible logic functions. The table below has four rows that show the four possible combinations of two inputs (\(2^2 = 4\)), and 16 output columns that show all possible twoinput logic function (\(2^{2^2}=16\)). Six of these output columns are associated with common logic functions of two variables.
Circle the six columns
label them with the appropriate logic gate name
Draw the circuit symbols for the functions represented.
A table like the one above for 3 inputs would need _________ rows and _________ columns.
A table like the one above for 4 inputs would need _________ rows and _________ columns.
A table like the one above for 5 inputs would need _________ rows and _________ columns
The six common logic functions with two variables:
NAND
: Column 8AND
: 9NOR
: 2OR
: 15XOR
: 6XNOR
: 10
ANSI, IEC and DIN circuit symbols
We discussed the following in the exercises Exercise 45 and Exercise 46:
A table like the one above for 3 inputs would need \(2^3 = 8\) rows and \(2^8 = 256\) columns.
A table like the one above for 4 inputs would need \(2^4 = 16\) rows and \(2^{16} = 64\,\mathrm{Ki}\) columns.
A table like the one above for 5 inputs would need \(2^5 = 32\) rows and \(2^{32} = 4\,\mathrm{Gi}\) columns
8#
Complete truth tables for the circuits shown below.
8.1#
The straightforward approach is that we calculate F
dependent on the inputs by propagating the individual values of the inputs for each of the eight conditions. This is a input to output approach.
An faster alternative is that we propagate from the output to the input. We have a NAND
connected to the output and a NAND
can be only 0
if the inputs are both 1
. Now we have two gates which must output a 0
:
NOR
: IfNOR
must deliver a1
, we should think about the conditions whenOR
outputs0
. BothA
andB
must be0
.OR
with a negatedC
. IfOR
must output a1
, then the inputs~C
andB
can be00
,10
,01
.
According to 1. A
and B
both must be 0
, and if we consider 2., then C
can be both 0
and 1
Now we can list all the input conditions for the inputs where F
is 0
.
A 
B 
C 

0 
0 
0 
0 
0 
1 
For the rest of the conditions F
must be 1
.
A 
B 
C 
F 

0 
0 
0 
0 
0 
0 
1 
0 
0 
1 
0 
1 
0 
1 
1 
1 
1 
0 
0 
1 
1 
0 
1 
1 
1 
1 
0 
1 
1 
1 
1 
1 
Note
Did you notice that we solved the problem using SOP logic by compiling the conditions which must occur to get a 1
?
8.2#
Let us use the same outputtoinput approach. This time we have an OR
at our output, so consider the case when OR
is 0
. If OR
must output 0
, then all the AND
s must output 0
. AND
s output 0
if their inputs are not 1
, so we get the following statements for the three AND
s from top to bottom.
ABC
must not be001
.BC
must not be10
.CA
must not be11
.
If these statements are true, then F
will Using these statements we can write:
A 
B 
C 
F 

0 
0 
1 
0 
0,1 
1 
0 
0 
1 
1 
1 
0 
In the rest of the conditions F
must be 1
. In summary:
A 
B 
C 
F 

0 
0 
0 
1 
0 
0 
1 
0 
0 
1 
0 
0 
0 
1 
1 
1 
1 
0 
0 
1 
1 
0 
1 
1 
1 
1 
0 
0 
1 
1 
1 
0 
Note
Did you notice that we solved the problem using POS logic by compiling the cases which must not occur to get a 1
?
9#
Show the total transistor count and gate/input number for the circuits below.
Sketch equivalent circuits using NAND gates that use fewer transistors (do not minimize the circuits).
G:
module m (output G, input A,B,C,D);
assign G = ~A & B & C  A & C  C & ~D;
endmodule
F:
module m (output F, input A,B,C);
assign F = ~A & B  B & ~C;
endmodule
Total transistor counts:
G
2x inverter: \(2 \cdot 2 = 4\)
1x
AND
with three inputs: \(6+2=8\)2x
AND
with two inputs: \(2 (4+2) = 12\)1x
OR
with three inputs: \(6+2=8\)Total: 32
F
2x inverter: \(2 \cdot 2 = 4\)
2x
AND
with two inputs: \(2 (4+2) = 12\)1x
OR
with two inputs: \(4+2=6\)Total: 22
Gate/input counts:
G: 4 gates / 10 inputs
F: 3 gates / 6 inputs
Equivalent circuits using NAND gates:
We can double negate the circuits and use De Morgan’s law to get NAND gates.
G:
module m (output G, input A,B,C,D);
// Original:
assign G = ~A & B & C  A & C  C & ~D;
// Double negation
assign G = ~~(A & B & C  A & C  C & ~D);
// De Morgan on the OR gate
// in other words pushing one bubble through OR
assign G = ~( ~(A & B & C) & ~(A & C) & ~(~C & ~D) );
endmodule
Now we have only NAND
gates and inverters.
Same for F:
module m (output F, input A,B,C);
// Original:
assign F = ~A & B  B & ~C;
// Double negation and De Morgan
assign F = ~( ~(~A & B) & ~(B & ~C) );
endmodule
Let us calculate the transistor counts to compare them:
G
2x inverter: \(2 \cdot 2 = 4\)
2x
NAND
with three inputs: \(2 \cdot 6 = 12\)2x
NAND
with two inputs: \(2 \cdot 4 = 8\)Total: 24 (compared to 32)
F
2x inverter: \(2 \cdot 2 = 4\)
3x
NAND
with two inputs: \(3 \cdot 4 = 12\)Total: 16 (compared to 22)
Finally the gate/input counts:
G: 4 gates / 10 inputs (compared to 4/10)
F: 3 gates / 6 inputs (compared to 3/6)
The gate/input counts do not change but the transistor count changes significantly.
10#
Simplify the following using Boolean algebra
10.1#
module m (output Y, input A,B,C,D);
assign Y = (A & B & ~C & D)  (A & C)  (~C & ~D)  (A & ~B & ~C & D)  (~A & C);
end module
Note
&
has the same precedence as 
in Verilog. Source; Systemverilog 2017 – Chapter 11.3.2
module m (output Y, input A,B,C,D);
// Original
assign Y =
(A & B & ~C & D) 
(A & C) 
(~C & ~D) 
(A & ~B & ~C & D) 
(~A & C);
// Factorize and separate (~C & D) from the first, third and fourth term
// according to the associative law and put them to the front according to the
// commutative law
assign Y =
(~C & D) & (A & B) 
(A & C) 
(~C & ~D) 
(~C & D) & (A & ~B) 
(~A & C);
// Reverse the distribution of the multiplicative (ANDed) term (~C & D) over
// additions (ORed)
assign Y =
(~C & D) & ( (A & B)  (A & ~B) ) 
(A & C) 
(~C & ~D) 
(~A & C);
// Use the same steps to factorize C from the second and fourth term
assign Y =
(~C & D) & ( (A & B)  (A & ~B) ) 
C & (A  ~A) 
(~C & ~D);
// Use complementation for OR in the second term (X OR NOT(X) is always true)
assign Y =
(~C & D) & ( (A & B)  (A & ~B) ) 
C & 1 
(~C & ~D);
// Use identity rule: (X AND 1)=X
assign Y =
(~C & D) & ( (A & B)  (A & ~B) ) 
C 
(~C & ~D);
// Reverse distribution of A in the first term
assign Y =
(~C & D) & ( A & (B  ~B) ) 
C 
(~C & ~D);
// Use complementation of OR and identity of AND on the same
assign Y =
(~C & D) & A 
C 
(~C & ~D);
// Factorize ~C and reverse its distribution on the first and third term
assign Y =
~C ( (D & A)  ~D ) 
C;
end module
10.2#
\( Y = \overline{AB} + \overline{B + C} + \overline{B} \)
module m (output Y, input A,B,C,D);
// Original
assign Y =
~(A & B) 
~(B  C) 
~B;
// De Morgan on the first and second term
assign Y =
(~A  ~B) 
(~B & ~C) 
~B;
// Getting rid of the parantheses on the first term
assign Y =
~A 
~B 
(~B & ~C) 
~B;
// Idempotence of OR in second and the fourth term
assign Y =
~A 
~B 
(~B & ~C);
// Factorize ~B out of the second and the third (reverse distributive)
assign Y =
~A 
~B & (1  ~C);
// Identity of OR in the second term
assign Y =
~A 
~B & ~C;
end module
11#
Timing diagrams show circuit inputs and outputs as they change over time. In the figure below, the signals A and B come from push buttons that are pressed at different times (in the first time slice, neither A or B are pressed, in the second time slice, B is pressed but A is not, etc.).
Complete the timing diagrams to show how the various logic gates respond to their inputs.
F1
:NAND
F2
:NOR
F3
:NAND
with~B
F4
:OR
F5
: after bubblepushingNOR
F6
: after bubblepushingAND