display | more...
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.

    Log in or register to write something here or to contact authors.