Designing a Circuit for a Given Input/Output Table
Design a circuit for the following input/output table:

Inputs

Outputs

P

Q

R

S

1

1

1

0

1

1

0

1

1

0

1

0

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

0

0

0

0

1

First we construct a Boolean expression with this table as its truth table using disjunctive normal form. Rows 2 and 8 are the only rows with output.
Row 2 gives us P Ù Q Ù Ø R.
Row 8 gives us Ø P Ù Ø Q Ù Ø R.
Combining these results in disjunctive normal form: (P Ù Q Ù Ø R) Ú (Ø P Ù Ø Q Ù Ø R).
Now draw this circuit:

 

 

 

 

 

 

 

Equivalently, application of the distributive law gives us: Ø R Ù ((P Ù Q ) Ú (Ø P Ù Ø Q))

 

 

 

An equivalent circuit requiring one less gate.

Designing a Full Adder 

Example

Boolean expressions, Pierce arrow and Scheffer stroke (optional)

If we NOT the output of an AND-gate we get a NAND-gate. A NAND-gate is a single gate that acts like an AND-gate followed by a NOT-gate. The output of a NAND-gate is 0 when and only when, both input signals are 1. Similarly for a NOR-gate. NOT the output of an OR-gate and we see that the output signal for a NOR-gate is 1 when and only when both input signals are 0. The logic symbols for these two gates are: the Scheffer stroke | for the NAND, and the Peirce arrow ¯ for the NOR.

It can be shown that any Boolean expression is equivalent to one written entirely with Scheffer strokes or entirely with Peirce arrows. Thus any digital logic circuit is equivalent to one that uses only NAND-gates or only NOR-gates.

Example: Rewriting expressions using the Scheffer stroke

  1. Show that Ø p º p ½ p.
    2.

    Ø p

    º

    Ø (p Ù p)

    idempotent
     

    º

    p ½ p

    definition of Scheffer stroke
  2. Show that (p ½ q) ½ (p ½ q) º p Ù q.

(p ½ q) ½ (p ½ q)

º

Ø [(p ½ q) Ù (p ½ q)]

definition of Scheffer stroke
 

º

Ø (p ½ q)

idempotent
 

º

Ø [Ø (p Ù q) ]

definition of Scheffer stroke
 

º

p Ù q

double negation

Showing two circuits are equivalent

 Using basic Boolean algebra properties (Theorem 1.1.1) one can simplify the Boolean expression for a circuit. This new, logically equivalent Boolean expression can then be used to construct a simpler circuit. Another technique to finding a simpler circuit is to find an equivalent circuit that uses fewer gates. Trial and error, intuition and insight are valid tools when pursuing this latter method.