Short Notes: Combinational Circuit | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


                                                               
 
Combinational circuit 
Introduction 
The combinational circuit consist of logic gates whose outputs at any time is determined directly from the present 
combination of input without any regard to the previous input. A combinational circuit performs a specific information 
processing operation fully specified logically by a set of Boolean functions. 
A combinatorial circuit is a generalized gate. In general such a circuit has m inputs and n outputs.  Such a circuit can 
always be constructed as n separate combinatorial circuits, each with exactly one output. For that reason, some texts 
only discuss combinatorial circuits with exactly one output. In reality, however, some important sharing of intermediate 
signals may take place if the entire n-output circuit is constructed at once. Such sharing can significantly reduce the 
number of gates required to build the circuit.  
When we build a combinatorial circuit from some kind of specification, we always try to make it as good as possible. 
The only problem is that the definition of "as good as possible" may vary greatly. In some applications, we simply want 
to minimize the number of gates (or the number of transistors, really). In other, we might be interested in as short a 
delay (the time it takes a signal to traverse the circuit) as possible, or in as low power consumption as possible. In 
general, a mixture of such criteria must be applied. 
Describing existing circuits using Truth tables 
To specify the exact way in which a combinatorial circuit works, we might use different methods, such as logical 
expressions or truth tables.  
A truth table is a complete enumeration of all possible combinations of input values, each one with its associated output 
value.  
When used to describe an existing circuit, output values are (of course) either 0 or 1. Suppose for instance that we wish 
to make a truth table for the following circuit:  
 
All we need to do to establish a truth table for this circuit is to compute the output value for the circuit for each possible 
combination of input values. We obtain the following truth table:  
  w x y | a b 
  ----------- 
  0 0 0 | 0 1 
  0 0 1 | 0 1 
  0 1 0 | 1 1 
  0 1 1 | 1 0 
  1 0 0 | 1 1 
  1 0 1 | 1 1 
  1 1 0 | 1 1 
  1 1 1 | 1 0 
Page 2


                                                               
 
Combinational circuit 
Introduction 
The combinational circuit consist of logic gates whose outputs at any time is determined directly from the present 
combination of input without any regard to the previous input. A combinational circuit performs a specific information 
processing operation fully specified logically by a set of Boolean functions. 
A combinatorial circuit is a generalized gate. In general such a circuit has m inputs and n outputs.  Such a circuit can 
always be constructed as n separate combinatorial circuits, each with exactly one output. For that reason, some texts 
only discuss combinatorial circuits with exactly one output. In reality, however, some important sharing of intermediate 
signals may take place if the entire n-output circuit is constructed at once. Such sharing can significantly reduce the 
number of gates required to build the circuit.  
When we build a combinatorial circuit from some kind of specification, we always try to make it as good as possible. 
The only problem is that the definition of "as good as possible" may vary greatly. In some applications, we simply want 
to minimize the number of gates (or the number of transistors, really). In other, we might be interested in as short a 
delay (the time it takes a signal to traverse the circuit) as possible, or in as low power consumption as possible. In 
general, a mixture of such criteria must be applied. 
Describing existing circuits using Truth tables 
To specify the exact way in which a combinatorial circuit works, we might use different methods, such as logical 
expressions or truth tables.  
A truth table is a complete enumeration of all possible combinations of input values, each one with its associated output 
value.  
When used to describe an existing circuit, output values are (of course) either 0 or 1. Suppose for instance that we wish 
to make a truth table for the following circuit:  
 
All we need to do to establish a truth table for this circuit is to compute the output value for the circuit for each possible 
combination of input values. We obtain the following truth table:  
  w x y | a b 
  ----------- 
  0 0 0 | 0 1 
  0 0 1 | 0 1 
  0 1 0 | 1 1 
  0 1 1 | 1 0 
  1 0 0 | 1 1 
  1 0 1 | 1 1 
  1 1 0 | 1 1 
  1 1 1 | 1 0 
                                                               
 
 
Specifying circuits to build 
When used as a specification for a circuit, a table may have some output values that are not specified, perhaps because 
the corresponding combination of input values can never occur in the particular application. We can indicate such 
unspecified output values with a dash -.  
For instance, let us suppose we want a circuit of four inputs, interpreted as two nonnegative binary integers of two 
binary digits each, and two outputs, interpreted as the nonnegative binary integer giving the quotient between the two 
input numbers. Since division is not defined when the denominator is zero, we do not care what the output value is in 
this case. Of the sixteen entries in the truth table, four have a zero denominator. Here is the truth table:  
  x1 x0 y1 y0 | z1 z0 
  ------------------- 
   0  0  0  0   | -  - 
   0  0  0  1   | 0  0 
   0  0  1  0   | 0  0 
   0  0  1  1   | 0  0 
   0  1  0  0   | -  - 
   0  1  0  1   | 0  1 
   0  1  1  0   | 0  0 
   0  1  1  1   | 0  0 
   1  0  0  0   | -  - 
   1  0  0  1   | 1  0 
   1  0  1  0   | 0  1 
   1  0  1  1   | 0  0 
   1  1  0  0   | -  - 
   1  1  0  1   | 1  1 
   1  1  1  0   | 0  1 
   1  1  1  1   | 0  1 
Unspecified output values like this can greatly decrease the number of circuits necessary to build the circuit. The reason 
is simple: when we are free to choose the output value in a particular situation, we choose the one that gives the fewest 
total number of gates.  
Circuit minimization is a difficult problem from complexity point of view. Computer programs that try to optimize 
circuit design apply a number of heuristics to improve speed. In this course, we are not concerned with optimality. We 
are therefore only going to discuss a simple method that works for all possible combinatorial circuits (but that can waste 
large numbers of gates).  
A separate single-output circuit is built for each output of the combinatorial circuit.  
Our simple method starts with the truth table (or rather one of the acceptable truth tables, in case we have a choice). Our 
circuit is going to be a two-layer circuit. The first layer of the circuit will have at most 2
n
 AND-gates, each with n inputs 
(where n is the number of inputs of the combinatorial circuit). The second layer will have a single OR-gate with as many 
inputs as there are gates in the first layer. For each line of the truth table with an output value of 1, we put down a AND-
gate with n inputs. For each input entry in the table with a 1 in it, we connect an input of the AND-gate to the 
corresponding input. For each entry in the table with a 0 in it, we connect an input of the AND-gate to the corresponding 
input inverted.  
The output of each AND-gate of the fist layer is then connected to an input of the OR-gate of the second layer.  
As an example of our general method, consider the following truth table (where a - indicates that we don't care what 
value is chosen):  
Page 3


                                                               
 
Combinational circuit 
Introduction 
The combinational circuit consist of logic gates whose outputs at any time is determined directly from the present 
combination of input without any regard to the previous input. A combinational circuit performs a specific information 
processing operation fully specified logically by a set of Boolean functions. 
A combinatorial circuit is a generalized gate. In general such a circuit has m inputs and n outputs.  Such a circuit can 
always be constructed as n separate combinatorial circuits, each with exactly one output. For that reason, some texts 
only discuss combinatorial circuits with exactly one output. In reality, however, some important sharing of intermediate 
signals may take place if the entire n-output circuit is constructed at once. Such sharing can significantly reduce the 
number of gates required to build the circuit.  
When we build a combinatorial circuit from some kind of specification, we always try to make it as good as possible. 
The only problem is that the definition of "as good as possible" may vary greatly. In some applications, we simply want 
to minimize the number of gates (or the number of transistors, really). In other, we might be interested in as short a 
delay (the time it takes a signal to traverse the circuit) as possible, or in as low power consumption as possible. In 
general, a mixture of such criteria must be applied. 
Describing existing circuits using Truth tables 
To specify the exact way in which a combinatorial circuit works, we might use different methods, such as logical 
expressions or truth tables.  
A truth table is a complete enumeration of all possible combinations of input values, each one with its associated output 
value.  
When used to describe an existing circuit, output values are (of course) either 0 or 1. Suppose for instance that we wish 
to make a truth table for the following circuit:  
 
All we need to do to establish a truth table for this circuit is to compute the output value for the circuit for each possible 
combination of input values. We obtain the following truth table:  
  w x y | a b 
  ----------- 
  0 0 0 | 0 1 
  0 0 1 | 0 1 
  0 1 0 | 1 1 
  0 1 1 | 1 0 
  1 0 0 | 1 1 
  1 0 1 | 1 1 
  1 1 0 | 1 1 
  1 1 1 | 1 0 
                                                               
 
 
Specifying circuits to build 
When used as a specification for a circuit, a table may have some output values that are not specified, perhaps because 
the corresponding combination of input values can never occur in the particular application. We can indicate such 
unspecified output values with a dash -.  
For instance, let us suppose we want a circuit of four inputs, interpreted as two nonnegative binary integers of two 
binary digits each, and two outputs, interpreted as the nonnegative binary integer giving the quotient between the two 
input numbers. Since division is not defined when the denominator is zero, we do not care what the output value is in 
this case. Of the sixteen entries in the truth table, four have a zero denominator. Here is the truth table:  
  x1 x0 y1 y0 | z1 z0 
  ------------------- 
   0  0  0  0   | -  - 
   0  0  0  1   | 0  0 
   0  0  1  0   | 0  0 
   0  0  1  1   | 0  0 
   0  1  0  0   | -  - 
   0  1  0  1   | 0  1 
   0  1  1  0   | 0  0 
   0  1  1  1   | 0  0 
   1  0  0  0   | -  - 
   1  0  0  1   | 1  0 
   1  0  1  0   | 0  1 
   1  0  1  1   | 0  0 
   1  1  0  0   | -  - 
   1  1  0  1   | 1  1 
   1  1  1  0   | 0  1 
   1  1  1  1   | 0  1 
Unspecified output values like this can greatly decrease the number of circuits necessary to build the circuit. The reason 
is simple: when we are free to choose the output value in a particular situation, we choose the one that gives the fewest 
total number of gates.  
Circuit minimization is a difficult problem from complexity point of view. Computer programs that try to optimize 
circuit design apply a number of heuristics to improve speed. In this course, we are not concerned with optimality. We 
are therefore only going to discuss a simple method that works for all possible combinatorial circuits (but that can waste 
large numbers of gates).  
A separate single-output circuit is built for each output of the combinatorial circuit.  
Our simple method starts with the truth table (or rather one of the acceptable truth tables, in case we have a choice). Our 
circuit is going to be a two-layer circuit. The first layer of the circuit will have at most 2
n
 AND-gates, each with n inputs 
(where n is the number of inputs of the combinatorial circuit). The second layer will have a single OR-gate with as many 
inputs as there are gates in the first layer. For each line of the truth table with an output value of 1, we put down a AND-
gate with n inputs. For each input entry in the table with a 1 in it, we connect an input of the AND-gate to the 
corresponding input. For each entry in the table with a 0 in it, we connect an input of the AND-gate to the corresponding 
input inverted.  
The output of each AND-gate of the fist layer is then connected to an input of the OR-gate of the second layer.  
As an example of our general method, consider the following truth table (where a - indicates that we don't care what 
value is chosen):  
                                                               
 
  x y z | a b 
  ----------- 
  0 0 0 | - 0 
  0 0 1 | 1 1 
  0 1 0 | 1 - 
  0 1 1 | 0 0 
  1 0 0 | 0 1 
  1 0 1 | 0 - 
  1 1 0 | - - 
  1 1 1 | 1 0 
The first step is to arbitrarily choose values for the undefined outputs. With out simple method, the best solution is to 
choose a 0 for each such undefined output. We get this table:  
  x y z | a b 
  ----------- 
  0 0 0 | 0 0 
  0 0 1 | 1 1 
  0 1 0 | 1 0 
  0 1 1 | 0 0 
  1 0 0 | 0 1 
  1 0 1 | 0 0 
  1 1 0 | 0 0 
  1 1 1 | 1 0 
Now, we have to build two separate single-output circuits, one for the a column and one for the b column.  
A=x'y'z+x'yz'+xyz 
B=x'y'z+xy'z' 
For the first column, we get three 3-input AND-gates in the first layer, and a 3-input OR-gate in the second layer. We get 
three AND -gates since there are three rows in the a column with a value of 1. Each one has 3-inputs since there are 
three inputs, x, y, and z of the circuit. We get a 3-input OR-gate in the second layer since there are three AND -gates in 
the first layer.  
Here is the complete circuit for the first column:  
 
For the second column, we get two 3-input AND -gates in the first layer, and a 2-input OR-gate in the second layer. We 
get two AND-gates since there are two rows in the b column with a value of 1. Each one has 3-inputs since again there 
are three inputs, x, y, and z of the circuit. We get a 2-input AND-gate in the second layer since there are two AND-gates 
in the first layer.  
Here is the complete circuit for the second column:  
Page 4


                                                               
 
Combinational circuit 
Introduction 
The combinational circuit consist of logic gates whose outputs at any time is determined directly from the present 
combination of input without any regard to the previous input. A combinational circuit performs a specific information 
processing operation fully specified logically by a set of Boolean functions. 
A combinatorial circuit is a generalized gate. In general such a circuit has m inputs and n outputs.  Such a circuit can 
always be constructed as n separate combinatorial circuits, each with exactly one output. For that reason, some texts 
only discuss combinatorial circuits with exactly one output. In reality, however, some important sharing of intermediate 
signals may take place if the entire n-output circuit is constructed at once. Such sharing can significantly reduce the 
number of gates required to build the circuit.  
When we build a combinatorial circuit from some kind of specification, we always try to make it as good as possible. 
The only problem is that the definition of "as good as possible" may vary greatly. In some applications, we simply want 
to minimize the number of gates (or the number of transistors, really). In other, we might be interested in as short a 
delay (the time it takes a signal to traverse the circuit) as possible, or in as low power consumption as possible. In 
general, a mixture of such criteria must be applied. 
Describing existing circuits using Truth tables 
To specify the exact way in which a combinatorial circuit works, we might use different methods, such as logical 
expressions or truth tables.  
A truth table is a complete enumeration of all possible combinations of input values, each one with its associated output 
value.  
When used to describe an existing circuit, output values are (of course) either 0 or 1. Suppose for instance that we wish 
to make a truth table for the following circuit:  
 
All we need to do to establish a truth table for this circuit is to compute the output value for the circuit for each possible 
combination of input values. We obtain the following truth table:  
  w x y | a b 
  ----------- 
  0 0 0 | 0 1 
  0 0 1 | 0 1 
  0 1 0 | 1 1 
  0 1 1 | 1 0 
  1 0 0 | 1 1 
  1 0 1 | 1 1 
  1 1 0 | 1 1 
  1 1 1 | 1 0 
                                                               
 
 
Specifying circuits to build 
When used as a specification for a circuit, a table may have some output values that are not specified, perhaps because 
the corresponding combination of input values can never occur in the particular application. We can indicate such 
unspecified output values with a dash -.  
For instance, let us suppose we want a circuit of four inputs, interpreted as two nonnegative binary integers of two 
binary digits each, and two outputs, interpreted as the nonnegative binary integer giving the quotient between the two 
input numbers. Since division is not defined when the denominator is zero, we do not care what the output value is in 
this case. Of the sixteen entries in the truth table, four have a zero denominator. Here is the truth table:  
  x1 x0 y1 y0 | z1 z0 
  ------------------- 
   0  0  0  0   | -  - 
   0  0  0  1   | 0  0 
   0  0  1  0   | 0  0 
   0  0  1  1   | 0  0 
   0  1  0  0   | -  - 
   0  1  0  1   | 0  1 
   0  1  1  0   | 0  0 
   0  1  1  1   | 0  0 
   1  0  0  0   | -  - 
   1  0  0  1   | 1  0 
   1  0  1  0   | 0  1 
   1  0  1  1   | 0  0 
   1  1  0  0   | -  - 
   1  1  0  1   | 1  1 
   1  1  1  0   | 0  1 
   1  1  1  1   | 0  1 
Unspecified output values like this can greatly decrease the number of circuits necessary to build the circuit. The reason 
is simple: when we are free to choose the output value in a particular situation, we choose the one that gives the fewest 
total number of gates.  
Circuit minimization is a difficult problem from complexity point of view. Computer programs that try to optimize 
circuit design apply a number of heuristics to improve speed. In this course, we are not concerned with optimality. We 
are therefore only going to discuss a simple method that works for all possible combinatorial circuits (but that can waste 
large numbers of gates).  
A separate single-output circuit is built for each output of the combinatorial circuit.  
Our simple method starts with the truth table (or rather one of the acceptable truth tables, in case we have a choice). Our 
circuit is going to be a two-layer circuit. The first layer of the circuit will have at most 2
n
 AND-gates, each with n inputs 
(where n is the number of inputs of the combinatorial circuit). The second layer will have a single OR-gate with as many 
inputs as there are gates in the first layer. For each line of the truth table with an output value of 1, we put down a AND-
gate with n inputs. For each input entry in the table with a 1 in it, we connect an input of the AND-gate to the 
corresponding input. For each entry in the table with a 0 in it, we connect an input of the AND-gate to the corresponding 
input inverted.  
The output of each AND-gate of the fist layer is then connected to an input of the OR-gate of the second layer.  
As an example of our general method, consider the following truth table (where a - indicates that we don't care what 
value is chosen):  
                                                               
 
  x y z | a b 
  ----------- 
  0 0 0 | - 0 
  0 0 1 | 1 1 
  0 1 0 | 1 - 
  0 1 1 | 0 0 
  1 0 0 | 0 1 
  1 0 1 | 0 - 
  1 1 0 | - - 
  1 1 1 | 1 0 
The first step is to arbitrarily choose values for the undefined outputs. With out simple method, the best solution is to 
choose a 0 for each such undefined output. We get this table:  
  x y z | a b 
  ----------- 
  0 0 0 | 0 0 
  0 0 1 | 1 1 
  0 1 0 | 1 0 
  0 1 1 | 0 0 
  1 0 0 | 0 1 
  1 0 1 | 0 0 
  1 1 0 | 0 0 
  1 1 1 | 1 0 
Now, we have to build two separate single-output circuits, one for the a column and one for the b column.  
A=x'y'z+x'yz'+xyz 
B=x'y'z+xy'z' 
For the first column, we get three 3-input AND-gates in the first layer, and a 3-input OR-gate in the second layer. We get 
three AND -gates since there are three rows in the a column with a value of 1. Each one has 3-inputs since there are 
three inputs, x, y, and z of the circuit. We get a 3-input OR-gate in the second layer since there are three AND -gates in 
the first layer.  
Here is the complete circuit for the first column:  
 
For the second column, we get two 3-input AND -gates in the first layer, and a 2-input OR-gate in the second layer. We 
get two AND-gates since there are two rows in the b column with a value of 1. Each one has 3-inputs since again there 
are three inputs, x, y, and z of the circuit. We get a 2-input AND-gate in the second layer since there are two AND-gates 
in the first layer.  
Here is the complete circuit for the second column:  
                                                               
 
 
Now, all we have to do is to combine the two circuits into a single one:  
 
While this circuit works, it is not the one with the fewest number of gates. In fact, since both output columns have a 1 in 
the row correspoding to the inputs 0 0 1, it is clear that the gate for that row can be shared between the two subcircuits:  
 
In some cases, even smaller circuits can be obtained, if one is willing to accept more layers (and thus a higher circuit 
delay).  
Page 5


                                                               
 
Combinational circuit 
Introduction 
The combinational circuit consist of logic gates whose outputs at any time is determined directly from the present 
combination of input without any regard to the previous input. A combinational circuit performs a specific information 
processing operation fully specified logically by a set of Boolean functions. 
A combinatorial circuit is a generalized gate. In general such a circuit has m inputs and n outputs.  Such a circuit can 
always be constructed as n separate combinatorial circuits, each with exactly one output. For that reason, some texts 
only discuss combinatorial circuits with exactly one output. In reality, however, some important sharing of intermediate 
signals may take place if the entire n-output circuit is constructed at once. Such sharing can significantly reduce the 
number of gates required to build the circuit.  
When we build a combinatorial circuit from some kind of specification, we always try to make it as good as possible. 
The only problem is that the definition of "as good as possible" may vary greatly. In some applications, we simply want 
to minimize the number of gates (or the number of transistors, really). In other, we might be interested in as short a 
delay (the time it takes a signal to traverse the circuit) as possible, or in as low power consumption as possible. In 
general, a mixture of such criteria must be applied. 
Describing existing circuits using Truth tables 
To specify the exact way in which a combinatorial circuit works, we might use different methods, such as logical 
expressions or truth tables.  
A truth table is a complete enumeration of all possible combinations of input values, each one with its associated output 
value.  
When used to describe an existing circuit, output values are (of course) either 0 or 1. Suppose for instance that we wish 
to make a truth table for the following circuit:  
 
All we need to do to establish a truth table for this circuit is to compute the output value for the circuit for each possible 
combination of input values. We obtain the following truth table:  
  w x y | a b 
  ----------- 
  0 0 0 | 0 1 
  0 0 1 | 0 1 
  0 1 0 | 1 1 
  0 1 1 | 1 0 
  1 0 0 | 1 1 
  1 0 1 | 1 1 
  1 1 0 | 1 1 
  1 1 1 | 1 0 
                                                               
 
 
Specifying circuits to build 
When used as a specification for a circuit, a table may have some output values that are not specified, perhaps because 
the corresponding combination of input values can never occur in the particular application. We can indicate such 
unspecified output values with a dash -.  
For instance, let us suppose we want a circuit of four inputs, interpreted as two nonnegative binary integers of two 
binary digits each, and two outputs, interpreted as the nonnegative binary integer giving the quotient between the two 
input numbers. Since division is not defined when the denominator is zero, we do not care what the output value is in 
this case. Of the sixteen entries in the truth table, four have a zero denominator. Here is the truth table:  
  x1 x0 y1 y0 | z1 z0 
  ------------------- 
   0  0  0  0   | -  - 
   0  0  0  1   | 0  0 
   0  0  1  0   | 0  0 
   0  0  1  1   | 0  0 
   0  1  0  0   | -  - 
   0  1  0  1   | 0  1 
   0  1  1  0   | 0  0 
   0  1  1  1   | 0  0 
   1  0  0  0   | -  - 
   1  0  0  1   | 1  0 
   1  0  1  0   | 0  1 
   1  0  1  1   | 0  0 
   1  1  0  0   | -  - 
   1  1  0  1   | 1  1 
   1  1  1  0   | 0  1 
   1  1  1  1   | 0  1 
Unspecified output values like this can greatly decrease the number of circuits necessary to build the circuit. The reason 
is simple: when we are free to choose the output value in a particular situation, we choose the one that gives the fewest 
total number of gates.  
Circuit minimization is a difficult problem from complexity point of view. Computer programs that try to optimize 
circuit design apply a number of heuristics to improve speed. In this course, we are not concerned with optimality. We 
are therefore only going to discuss a simple method that works for all possible combinatorial circuits (but that can waste 
large numbers of gates).  
A separate single-output circuit is built for each output of the combinatorial circuit.  
Our simple method starts with the truth table (or rather one of the acceptable truth tables, in case we have a choice). Our 
circuit is going to be a two-layer circuit. The first layer of the circuit will have at most 2
n
 AND-gates, each with n inputs 
(where n is the number of inputs of the combinatorial circuit). The second layer will have a single OR-gate with as many 
inputs as there are gates in the first layer. For each line of the truth table with an output value of 1, we put down a AND-
gate with n inputs. For each input entry in the table with a 1 in it, we connect an input of the AND-gate to the 
corresponding input. For each entry in the table with a 0 in it, we connect an input of the AND-gate to the corresponding 
input inverted.  
The output of each AND-gate of the fist layer is then connected to an input of the OR-gate of the second layer.  
As an example of our general method, consider the following truth table (where a - indicates that we don't care what 
value is chosen):  
                                                               
 
  x y z | a b 
  ----------- 
  0 0 0 | - 0 
  0 0 1 | 1 1 
  0 1 0 | 1 - 
  0 1 1 | 0 0 
  1 0 0 | 0 1 
  1 0 1 | 0 - 
  1 1 0 | - - 
  1 1 1 | 1 0 
The first step is to arbitrarily choose values for the undefined outputs. With out simple method, the best solution is to 
choose a 0 for each such undefined output. We get this table:  
  x y z | a b 
  ----------- 
  0 0 0 | 0 0 
  0 0 1 | 1 1 
  0 1 0 | 1 0 
  0 1 1 | 0 0 
  1 0 0 | 0 1 
  1 0 1 | 0 0 
  1 1 0 | 0 0 
  1 1 1 | 1 0 
Now, we have to build two separate single-output circuits, one for the a column and one for the b column.  
A=x'y'z+x'yz'+xyz 
B=x'y'z+xy'z' 
For the first column, we get three 3-input AND-gates in the first layer, and a 3-input OR-gate in the second layer. We get 
three AND -gates since there are three rows in the a column with a value of 1. Each one has 3-inputs since there are 
three inputs, x, y, and z of the circuit. We get a 3-input OR-gate in the second layer since there are three AND -gates in 
the first layer.  
Here is the complete circuit for the first column:  
 
For the second column, we get two 3-input AND -gates in the first layer, and a 2-input OR-gate in the second layer. We 
get two AND-gates since there are two rows in the b column with a value of 1. Each one has 3-inputs since again there 
are three inputs, x, y, and z of the circuit. We get a 2-input AND-gate in the second layer since there are two AND-gates 
in the first layer.  
Here is the complete circuit for the second column:  
                                                               
 
 
Now, all we have to do is to combine the two circuits into a single one:  
 
While this circuit works, it is not the one with the fewest number of gates. In fact, since both output columns have a 1 in 
the row correspoding to the inputs 0 0 1, it is clear that the gate for that row can be shared between the two subcircuits:  
 
In some cases, even smaller circuits can be obtained, if one is willing to accept more layers (and thus a higher circuit 
delay).  
                                                               
 
Boolean functions 
Operations of  binary variables can be described by mean of appropriate mathematical function called Boolean function. 
A Boolean function define a mapping from a set of binary input values into a set of output values. A Boolean function is 
formed with binary variables, the binary operators AND and OR and the unary operator NOT.  
For example , a Boolean function f(x
1,
x
2,
x
3,
……,x
n
) =y defines a mapping from an arbitrary combination of binary input 
values (x
1,
x
2,
x
3,
……,x
n
)  into a binary value y. a binary function with n input variable can operate on 2
n
 distincts values. 
Any such function can be described by using a truth table consisting of 2
n
 rows and n columns. The content of this table 
are the values produced by that function when applied to all the possible combination of the n input variable. 
Example 
x y x.y 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
The function f, representing x.y, that is f(x,y)=xy. Which mean that f=1 if x=1 and y=1 and f=0 otherwise. 
For each rows of the table, there is a value of the function equal to 1 or 0. The function f is equal to the sum of all rows 
that gives a value of 1. 
A Boolean function may be transformed from an algebraic expression into a logic diagram composed of AND, OR and 
NOT gate. When a Boolean function is implemented with logic gates, each literal in the function designates an input to a 
gate and each term  is implemented with a logic gate . e.g. 
 F=xyz 
 F=x+y'z 
Complement of a function 
The complement of a function F is F' and is obtained from an interchange of 0’s to 1’s and 1’s to 0’s in the value of F. 
the complement of a function may be derived algebraically trough De Morgan’s theorem  
(A+B+C+….)'= A'B'C'….  
 (ABC….)'= A'+ B'+C'…… 
The generalized form of de Morgan’s theorem state that the complement of function is obtained by interchanging AND 
and OR and complementing each literal.  
F=X'YZ'+X'Y'Z' 
F'=( X'YZ'+X'Y'Z')'  
 =( X'YZ')'.( X'Y'Z')' 
 =( X''+Y'+Z'')( X''+Y''+Z'') 
=( X+Y'+Z)( X+Y+Z)