The three types of logic gates are represented by standard symbols, as shown in Fig- ure 2.3. Since the inputs and outputs of logic gates are just wires carrying on/off signals, logic gates can be wired together by connecting outputs from some gates to inputs of other gates. The result is a logic circuit. An example is also shown in Figure 2.3.
Figure 2.3: The standard symbols for the three basic logic gates, and a logic circuit that computes the value of the logical expression (¬A) ∧ (B ∨ ¬(A ∧ C)). The input wires to each logic gate are on the left, with the output wire on the right. Note that when wires cross each other in a diagram such as this, the wires don’t actually intersect unless there is a black circle at the point where they cross.
The logic circuit in the figure has three inputs, labeled A, B, and C. The circuit com- putes the value of the compound proposition (¬A) ∧ (B ∨ ¬(A ∧ C)). That is, when Arepresents the proposition “the input wire labeled A is on,” and similarly for B and C, then the output of the circuit is on if and only if the value of the compound proposition(¬A) ∧ (B ∨ ¬(A ∧ C)) is true.
Given any compound proposition made from the operators ∧, ∨, and ¬, it is possible to build a logic circuit that computes the value of that proposition. The proposition itself is a blueprint for the circuit. As noted in Section 2.1, every logical operator that we have encountered can be expressed in terms of ∧, ∨, and ¬, so in fact every compound proposition that we know how to write can be computed by a logic circuit.
Given a proposition constructed from ∧, ∨, and ¬ operators, it is easy to build a circuit to compute it. First, identify the main operator in the proposition—the one whose value will be computed last. Consider (A ∨ B) ∧ ¬(A ∧ B). This circuit has two input values,A and B, which are represented by wires coming into the circuit. The circuit has an output wire that represents the computed value of the proposition. The main operator in (A ∨ B) ∧ ¬(A ∧ B), is the first ∧, which computes the value of the expression as a whole by combining the values of the subexpressions A ∨ B and ¬(A ∧ B). This ∧operator corresponds to an and gate in the circuit that computes the final output of the circuit.
Once the main operator has been identified and represented as a logic gate, you just have to build circuits to compute the input or inputs to that operator. In the example, the inputs to the main and gate come from two subcircuits. One subcircuit computes the value of A ∨ B and the other computes the value of ¬(A ∧ B). Building each subcircuit
1. We know that the final output of the circuit is computed by an AND gate, whose inputs are as shown.
2. These inputs, in turn come from an OR gate and a NOT gate, with inputs as shown.
3. The circuit is completed by adding an AND gate to compute the input for the NOT gate, and and connecting the circuit inputs, A and B, to the apropriate gate inputs.
Figure 2.4: Stages in the construction of a circuit that computes the compound proposition (A ∨ B) ∧ ¬(A ∧ B).
is a separate problem, but smaller than the problem you started with. Eventually, you’ll come to a gate whose input comes directly from one of the input wires—A or B in this case—instead of from a subcircuit.