Entry

Computer: Algorithm: Logic: How to build logic control structure via De Morgan law? [AND / OR / NOT]

Nov 18th, 2006 06:26
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 18 November 2020 - 11:47 am -------------------
Computer: Algorithm: Logic: How to build logic control structure via 
De Morgan law? [AND / OR / NOT]
---
Rewriting, replacing, optimizing, minimizing and simplifying your
logical expressions in your computer programs
You can possibly use this ideas to analyze, replace or rewrite, check,
minimize and simplify your (Boolean) logical expressions, which you use
in your computer programs, possibly writing this logical expressions as
short or optimized as possible, or using this ideas as building blocks
when you have to create the simplest or most esthetically beautiful
logical graphs (which you use in your BNF or EBNF).
You can e.g. also use this de Morgan logic laws to verify the 
correctness of
your replaced logical expressions.
===
August de Morgan logical laws used here are:
 1. -A negated sum of ORs equals a sum of negated ANDs
      NOT( A1 OR A2 OR A3 OR ... OR ALast ) = ( NOT A1 ) AND ( NOT 
A2 ) AND ( NOT A3 ) AND ... AND ( NOT ALast )
 2. -A negated sum of ANDs equals a sum of negated ORs
      NOT( A1 AND A2 AND A3 ... AND ALast ) = ( NOT A1 ) OR ( NOT A2 ) 
OR ( NOT A3 ) OR ... OR ( NOT ALast )
===
For example
 If you use in your computer pogram
  NOT ( ( end of file ) OR ( error ) )
 then this is, by applying the corresponding de Morgan logic law, thus
 equivalent to writing
  ( NOT end of file ) AND ( NOT error )
===
For example
 If you use in your computer pogram
  NOT ( ( end of file ) AND ( error ) )
 then this is, by applying the corresponding de Morgan logic law, thus
 equivalent to writing
  ( NOT end of file ) OR ( NOT error )
---
This August De Morgan laws allow you to exchange AND and OR and to
distribute or collect the NOT over the logical terms, while the
resulting expressions remain equivalent.
===
    For example, show that
     NOT ( A1 OR A2 )
    is equal to
     ( NOT A1 ) AND ( NOT A2 )
    ===
    Method: Using a truth table
    ===
     Truth table for NOT ( A1 OR A2 )
     +---------------------------------+
     |    |    |           | -------   |
     | A1 | A2 | A1 + A2   | A1 + A2   |
     +----+----+-----------+-----------|
     |  0 |  0 | 0 + 0 = 0 |    1      |
     |  0 |  1 | 0 + 1 = 1 |    0      |
     |  1 |  0 | 1 + 0 = 1 |    0      |
     |  1 |  1 | 1 + 1 = 1 |    0      |
     +---------------------------------+
    ===
    Truth table for ( NOT A1 ) AND ( NOT A2 )
     +---------------------------------+
     |    |    | --  | --  | --   --   |
     | A1 | A2 | A1  | A2  | A1 . A2   |
     +----+----+-----+-----+-----------|
     |  0 |  0 |  1  |  1  | 1 . 1 = 1 |
     |  0 |  1 |  1  |  0  | 1 . 0 = 0 |
     |  1 |  0 |  0  |  1  | 0 . 1 = 0 |
     |  1 |  1 |  0  |  0  | 0 . 0 = 0 |
     +---------------------------------+
    ===
    The two logical expressions are thus equal to each other.
    This because the logical values (in the final result in the right
    most column) are equal in the two tables (while starting with the
    same values of A1 and A2)
===
    For example, show that
     NOT ( A1 AND A2 )
    is equal to
     ( NOT A1 ) OR ( NOT A2 ).
    ===
    Method: Using a truth table
     ===
     Truth table for NOT ( A1 AND A2 )
     +---------------------------------+
     |    |    |           | -------   |
     | A1 | A2 | A1 . A2   | A1 + A2   |
     +----+----+-----------+-----------|
     |  0 |  0 | 0 . 0 = 0 |    1      |
     |  0 |  1 | 0 . 1 = 0 |    1      |
     |  1 |  0 | 1 . 0 = 0 |    1      |
     |  1 |  1 | 1 . 1 = 1 |    0      |
     +---------------------------------+
     ===
     Truth table for ( NOT A1 ) OR ( NOT A2 )
     +---------------------------------+
     |    |    | --  | --  | --   --   |
     | A1 | A2 | A1  | A2  | A1 + A2   |
     +----+----+-----+-----+-----------|
     |  0 |  0 |  1  |  1  | 1 + 1 = 1 |
     |  0 |  1 |  1  |  0  | 1 + 0 = 1 |
     |  1 |  0 |  0  |  1  | 0 + 1 = 1 |
     |  1 |  1 |  0  |  0  | 0 + 0 = 0 |
     +---------------------------------+
     ===
     The two logical expressions are thus equal to each other.
     This because the logical values (in the final result in the right
     most column) are equal in the two tables (while starting with the
     same values of A1 and A2)
     Note:
     You use here addition '+' for OR
     and multiplication '.' for AND,
     using the rules
      1 . 1 = 1
      1 . 0 = 0
      0 . 1 = 0
      0 . 0 = 0
      1 + 1 = 1
      0 + 1 = 1
      1 + 0 = 1
      0 + 0 = 0
     because that should let you mentally calculate easily
     (you calculate e.g. 1 OR 1, which gives 1 instead more easily as
      adding and multiplying is more familiar to you as 1 + 1, which
      gives also 1. Similar for 1 AND 0, this gives 0. But also 1 . 0
      gives 0).
===
1. -NOT( A1 OR A2 OR A3 OR ... OR ALast ) = ( NOT A1 ) AND ( NOT A2 ) 
AND ( NOT A3 ) AND ... AND ( NOT ALast )
    1. -Or thus applied to computer programming
        1. -In general
            ->-[ NOT ]->-+->-[ A1     ]->-+
                         |                |
                         +->-[ A2     ]->-+->-
                         |                |
                         ...            ...
                         |                |
                         +->-[ ALast  ]->-+
            =
            ->-[ NOT A1 ]->-[ NOT A2  ]->-[ NOT A3  ]->-...->-[ NOT 
ALast ]->-
        2. -For example
            Applying the August de Morgan law
             NOT ( A OR B ) = ( NOT A ) OR ( NOT B)
            to the case where you want to know the equivalence for not
            finding the end of a file or also not finding an error.
             NOT ( ( End of file ) OR ( Error ) )
            Now using de Morgan' law you can write this as
             = ( NOT ( End of file ) ) AND ( NOT ( Error ) )
            Or showing this in a graph
             ->-[ NOT ]->-+->-[ End of file ]->-+
                          |                     |
                          +->-[ Error       ]->-+->-
            =
            ->-[ NOT End of file ]->-[ NOT Error ]->-
===
2. -NOT( A1 AND A2 AND A3 ... AND ALast ) = ( NOT A1 ) OR ( NOT A2 ) 
OR ( NOT A3 ) OR ... OR ( NOT ALast )
    1. -Or thus applied to computer programming
        1. -In general
            ->-[ NOT    ]->-( [     A1  ]->-[     A2  ]->-...->-[   
ALast ] )->-
            =
            ->-+->-[ NOT A1    ]->-+
               |                   |
               +->-[ NOT A2    ]->-+->
               |                   |
               ...               ...
               |                   |
               +->-[ NOT ALast ]->-+
        2. -For example
            Applying the August de Morgan law
             NOT ( A AND B ) = ( NOT A ) OR ( NOT B)
            to the case where you want to know the equivalence for not
            finding the end of a file and also not finding an error.
             NOT ( ( End of file ) AND ( Error ) )
            Now using de Morgan' law you can write this as
             = ( NOT ( End of file ) ) OR ( NOT ( Error ) )
            Or showing this in a graph
            ->-[ NOT    ]->-( [ End of file ]->-[ Error ] )->-
            =
             ->-[ NOT ]->-(-+->-[ End of file ]->-+
                            |                     |
                            +->-[ Error       ]->-+-)->-
===
Internet: see also:
---
August De_Morgan's_laws
http://en.wikipedia.org/wiki/De_Morgan%27s_laws
---
Quine-McCluskey_algorithm
http://en.wikipedia.org/wiki/Quine-McCluskey_algorithm
---
Karnaugh map
http://en.wikipedia.org/wiki/Karnaugh_map
---
Truth table
http://en.wikipedia.org/wiki/Truth_table
----------------------------------------------------------------------