Introduction
Modern computers are constructed using
digital logic circuits which allow linear analog
electronic components like
transistors and
resistors to emulate
boolean logic functions. The fundamental unit of a digital logic circuit is called a
gate and all digital circuitry is built by interconnecting various gates.
Every basic gate has two
inputs and one
output, each of which can be in a high or low state ( i.e. voltage ). Each gate is defined by its
truth table which is a list of outputs for each set of possible inputs. One
exception is the
NOT gate which has one input and one output.
If we represent a high
state by one and a low state by zero, The possible inputs to a gate are 00, 01, 10, and 11. In the intersests of
brevity, we can represent a gate by the output it produces for each of these inputs respectively.
The possible logical gates (which have names) are:
AND - 0001
OR - 0111
NAND - 1110 (Not AND)
NOR - 1000 (Not OR)
XOR - 0110 (Exclusive OR)
XNOR - 1001 (Not Excusive OR)
IMP - 1101 (Logical implication)
NOT - Outputs the inverse of its input.
It is provable ( and obvious ) that any set of outputs can be generated by a
combination of AND, OR and NOT gates, or by a combination of NAND gates alone.
Boolean logic representation of arithmetic operations:
To perform
arithmetic operations, the
binary representations of the numbers involved is processed by an
array of gates.
For example, the operation of adding two binary digits has two inputs and two ouputs, with the following truth table.
The outputs are the
sum and
carry bits (S and C )
_______
_______ | A + B |
| A | B || S | C |
|---|---||---|---|
| 0 | 0 || 0 | 0 |
| 0 | 1 || 1 | 0 |
| 1 | 0 || 1 | 0 |
| 1 | 1 || 0 | 1 |
----------------
It is clear that the sum bit is A XOR B and the carry bit A AND B.
A circuit consisting of an AND gate and XOR gate with their inputs wired in parallel thus adds binary digits together and is called a
half adder. Similarly, all arithmetic operations can be carried out by
manipulating the bits using logic gates.
Now we are ready for :-
Arithmetic representation of boolean logic
While idly
pondering the above (Boolean logic representation of arithmetic operations) , I realized that the
converse was also
possible.
If we restrict our inputs to 1 and 0, we have:
A AND B = A * B
A OR B = A + B - ( A * B )
A XOR B = A + B - ( 2 * A * B )
NOT A = 1 - A
In
C++ code you could write:
bool AndFn( bool a, bool b ) { return bool( int(a) * int(b) ); }
bool OrFn( bool a, bool b ) { return bool( int(a) + int(b) - int(a) * int(b) ); }
bool XorFn( bool a, bool b ) { return bool( int(a) + int(b) - 2 * int(a) * int(b) ); }
bool NotFn( bool a ) { return bool( 1 - int(a) ); }
So it is possible to represent any
boolean expression as an arithmetic one.