PROBLEM: Find an additional representative circuit for the input/output table of Example 8.3.9.

Example 8.3.9 Equivalence Classes of Digital Logic Circuits In Example 8.3.3 it was shown that the relation of equivalence among circuits is an equiv alence relation. Let S be the set of all digital logic circuits with exactly two inputs and one output. The binary relation E is defined on S as follows: For all C1 and C2 in S Ci E C2 G has the same input/output table as C2. Describe the equivalence classes of this relation. How many distinct equivalence classes are there? Find two different circuits that are in one of the classes. Solution Given a circuit C, the equivalence class of C is the set of all circuits with two input signals and one output signal that have the same input/output table as C. Now each input/output table has exactly four rows, corresponding to the four possible combinations of inputs: 11, 10, 01, and 00. A typical input/output table is the following: Inp Output 0 0 0 0