## faqts : Computers : Programming : Algorithms : Logic

##### + Search    Did You Find This Entry Useful? 2 of 3 people (67%) answered YesRecently 2 of 3 people (67%) answered Yes

### 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 2006 - 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
===
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       ]->-+-)->-
===