====== Boolean Algebra ======

===== Introduction =====

The most obvious way to simplify //boolean expressions// is to manipulate them in the same way as normal algebraic expressions are manipulated. With regards to logic relations in digital forms, a set of rules for symbolic manipulation is needed in order to solve for the unknowns.

A set of rules formulated by the English mathematician [[wp>George Boole]] describe certain propositions whose outcome would be either //true// or //false//. With regard to digital logic, these rules are used to describe circuits whose state can be either, //1 (true)// or //0 (false)//. In order to fully understand this, the relation between the ''AND'' gate, ''OR'' gate and ''NOT'' gate operations should be appreciated. A number of rules can be derived from these relations as Table 1 demonstrates.

^ Table 1: Boolean postulates ^^
|  P1  | X = 0, X = 1 |
|  P2  | 0 · 0 = 0 |
|  P3  | 1 + 1 = 1 |
|  P4  | 0 + 0 = 0 |
|  P5  | 1 · 1 = 1 |
|  P6  | 1 · 0 = 0 · 1 = 0 |
|  P7  | 1 + 0 = 0 + 1 = 1 |

===== Laws of Boolean Algebra =====

//Table 2// shows the basic Boolean laws. Note that every law has two expressions, //**a**// and //**b**//. This is known as //duality//. These are obtained by changing every ''AND'' (·) to ''OR'' (+), every ''OR'' to ''AND'' and all 1's to 0's and vice-versa.

^ Table 2: Boolean laws ^^^^
|  **L1**  | Commutative law |  //**a**//  | A + B = B + A |
| ::: | ::: |  //**b**//  | A · B = B · A |
|  **L2**  | Associative Law |  //**a**//  | (A + B) + C = A + (B + C) |
| ::: | ::: |  //**b**//  | (A · B) · C = A · (B · C) |
|  **L3**  | Distributive Law |  //**a**//  | A · (B + C) = (A · B) + (A · C) |
| ::: | ::: |  //**b**//  | A + (B · C) = (A + B) · (A + C) |
|  **L4**  | Identity Law |  //**a**//  | A + A = A |
| ::: | ::: |  //**b**//  | A · A = A |
|  **L5**  | ... |  //**a**//  | (A · B) + (A · B) = A |
| ::: | ::: |  //**b**//  | (A + B) · (A + B) = A |
|  **L6**  | Redundancy Law |  //**a**//  | A + (A · B) = A |
| ::: | ::: |  //**b**//  | A · (A + B) = A |
|  **L7**  | ... |  //**a**//  | 0 + A = A |
| ::: | ::: |  //**b**//  | 0 · A = 0 |
|  **L8**  | ... |  //**a**//  | 1 + A = 1 |
| ::: | ::: |  //**b**//  | 1 · A = A |
|  **L9**  | ... |  //**a**//  | !A + A = 1 |
| ::: | ::: |  //**b**//  | !A · A = 0 |
|  **L10**  | ... |  //**a**//  | A + (!A · B) = A + B |
| ::: | ::: |  //**b**//  | A · (!A + B) = A · B |
|  **L11**  | De Morgan's Theorem |  //**a**//  | !(A + B) = !A ·! B |
| ::: | ::: |  //**b**//  | !(A · B) = !A + !B |

-----
<WRAP right info 60%>
Original text composed by David Belton - April 98\\
(Original page was at [[http://web.archive.org/web/20160828125329/http://www.ee.surrey.ac.uk/Projects/Labview/boolalgebra/|www.ee.surrey.ac.uk/Projects/Labview/boolalgrebra]] — now on web archive)\\
Edited by Federico Scala, January 2005\\
Wikified by Federico Scala, October 2017
</WRAP>