Putting It Together: Set Theory and Logic
George Boole
Multiplication seems to be a natural interpretation of AND when applied to the values 0 and 1. Just think about the truth table for the operation [latex]\wedge[/latex], replacing T by 1 and F by 0.
| A |
B |
AB (A AND B) |
| 1 |
1 |
1 |
| 1 |
0 |
0 |
| 0 |
1 |
0 |
| 0 |
0 |
0 |
There is also an OR gate. Again, two inputs A and B determine the output C, however this time C = 1 if and only if either A or B (or both) is equal to 1. This operation, which corresponds to the logical expression [latex]A \vee B[/latex], is often interpreted as a kind of addition (A OR B = A + B), however it’s not a perfect analogy because [latex]1+1=1[/latex] in Boolean logic.
| A |
B |
A + B (A OR B) |
| 1 |
1 |
1 |
| 1 |
0 |
1 |
| 0 |
1 |
1 |
| 0 |
0 |
0 |
Finally, there is a gate whose output is the opposite state as its input. So if the input (A) is 1, then the output (C) will be 0, and vice versa. This is called the NOT gate. You have encountered “not” as the logical expression [latex]\sim\!\textrm{A}[/latex], but the usual notation in computer science for NOT A is [latex]\overline{\textrm{A}}[/latex]. The gate along with its truth table shown below.
| A |
[latex]\overline{\textrm{A}}[/latex] (NOT A) |
| 1 |
0 |
| 0 |
1 |
Moreover, numerical values can be represented by a string of 1’s and 0’s in what we call binary notation. Then the basic operations of addition, subtraction, multiplication, and division of binary number can actually be accomplished using the right combination of gates, in other words by Boolean logical operations.
However a proper discussion of binary arithmetical falls outside the scope of this discussion. Instead, let’s use Boolean logic and to find a simpler circuit equivalent to the one shown.
The given circuit has three gates. Can you find a circuit with only two gates that produces exactly the same output (Q) for all choices of input (A, B)?
Let’s translate the diagram into a Boolean expression. First, both A and B are negated to obtain [latex]\overline{\textrm{A}}[/latex] and [latex]\overline{\textrm{B}}[/latex], respectively. Those expressions in turn feed into the AND gate. So [latex]\textrm{Q} =\overline{\textrm{A}} \cdot \overline{\textrm{B}}[/latex]. In terms of the logical operations you have studied in this module,
[latex]\textrm{Q}=\overline{\textrm{A}}\cdot\overline{\textrm{B}}=(\sim\!\textrm{A})\wedge(\sim\!\textrm{B})[/latex]
You may recognize the expression as one side of De Morgan’s Law. Therefore, there is an equivalence,
[latex](\sim\!\textrm{A})\wedge(\sim\!\textrm{B})= \;\sim\!(\textrm{A} \vee \textrm{B}) = \overline{\textrm{A} + \textrm{B}}[/latex]
Finally, the last expression corresponds to a circuit diagram with only two gates, an OR and a NOT.
Licenses & Attributions
CC licensed content, Original
CC licensed content, Shared previously
George Boole
Multiplication seems to be a natural interpretation of AND when applied to the values 0 and 1. Just think about the truth table for the operation [latex]\wedge[/latex], replacing T by 1 and F by 0.
