1.3.1: Logic Gates
- Page ID
A wire in a computer can be in one of two states, which we can think of as being on and
off. These two states can be naturally associated with the Boolean values T and F. When
a computer computes, the multitude of wires inside it are turned on and off in patterns
that are determined by certain rules. The rules involved can be most naturally expressed 2in terms of logic. A simple rule might be: “turn wire C on whenever wire A is on and
wire B is on”. This rule can be implemented in hardware as an AND gate. An and gate is an electronic component with two input wires and one output wire, whose job is to turn its output on when both of its inputs are on and to turn its output off in any other case. If we associate ‘on’ with T and ‘off’ with F, and if we give the names A and B to the inputs of the gate, then the gate computes the value of the logical expression A ∧ B. In effect, A is a proposition with the meaning “the first input is on”, and B is a proposition with the meaning “the second input is on”. The and gate functions to ensure that the output is described by the proposition A ∧ B. That is, the output is on if and only if the first input is on and the second input is on.
As you hopefully know from Computer Organisation, an OR gate is an electronic com- ponent with two inputs and one output which turns its output on if either (or both) of its inputs is on. If the inputs are given names A and B, then the or gate computes the logical value of A ∨ B. A NOT gate has one input and one output, and it turns its output off when the input is on and on when the input is off. If the input is named A, then the not gate computes the value of ¬A.
As I mentioned earlier, other textbooks might use different notations to represent a negation. For instance a bar over the variable x̄ or a ∼ symbol. In digital logic (and thus in your Computer Organisation course) you will also often find the + symbol to represent an ‘or’ and a · (dot) symbol to represent an ‘and’.
Other types of logic gates are, of course, possible. Gates could be made to computeA → B or A ⊕ B, for example. However, any computation that can be performed by logic gates can be done using only and, or, and not gates, as we will see below. (In practice, however, nand gates and nor gates, which compute the values of ¬(A ∧ B) and¬(A ∨ B) respectively, are often used because they are easier to build from transistors than and and or gates.)