Boolean Algebra
BRIEF ON CHAPTER
- Boolean Algebra: A modern algebra which uses the set of numbers 0 and 1, the logic number used to solve logic problems.
- Binary Decisions: The decision which results into either Yes(True) or No (False). Also called logical statement or truth function.
- Truth Table: A table representing all possible input-output combinations for a given logical problem/ expression.
- Tautology: A Boolean expression that always results in True or 1.
- Fallacy: A Boolean expression that always results in False or 0.
- Canonical Expression: A Boolean expression having all minterms or maxterms.
- Minterm: Product of all the literals (with or without the bar) within the logic system.
- Maxterm: Sum of all the literals(with or without bar) within the logic system.
- Logical Operator: Operator which is used to form compound statements is called logical operator.
Laws of Boolean Algebra
Law
|
OR Form
|
AND Form
|
1. Cumulative Law
|
X+Y = Y+X
|
X.Y = Y.X
|
2. Associate Law
|
X+(Y+Z) = (X+Y)+Z
|
X.(Y.Z) = (X.Y).Z
|
3. Distributive Law
|
X.(Y+Z) = X.Y + X.Z
|
X+ Y.Z =(X+Y).(X+Z)
|
4. Identity Law
|
0+X = X
|
1.X = X
|
5. Inverse Law
|
X+X’ = 1
|
X.X’=0
|
6. Idempotence Law
|
X+X = X
|
X.X = X
|
7. Absorption Law
|
X+X.Y = X
|
X. (X+Y)=X
|
8. Demorgan’s Law
|
(X+Y)’ = X’ . Y’
|
(X.Y)’ = X’+Y’
|
- Duality Principle: Any algebraic quality derived fromt eh axioms of Boolean algebra remains true if the operators OR and AND and the identity elements - 0 and 1 are interchanged. This property is called duality principle.:
- Karnaugh Map: Karnaugh Map is a graphical method of presenting the information represented in truth table. The Karnaugh Map is extensively used for the simplification of Boolean expression with up to six variables. The Map consists of 2n squares for n-variables function or expression with each cell representative a minterm or a maxterm.
- Logic Gates: Gates are basic circuits that hve at least one (and usually more) output and exactly one output. Input and output values are the logical values - True and False. In computer architecture, it is common to use 0 for false and 1 for true.
Truth Tables for the Laws of Boolean
Boolean
Expression |
Description
|
Equivalent
Switching Circuit |
Boolean Algebra
Law or Rule |
A + 1 = 1
|
A in parallel
with
closed = "CLOSED" |
 |
Annulment
|
A + 0 = A
|
A in parallel
with
open = "A" |
 |
Identity
|
A . 1 = A
|
A in series with
closed = "A" |
 |
Identity
|
A . 0 = 0
|
A in series with
open = "OPEN" |
 |
Annulment
|
A + A = A
|
A in parallel
with
A = "A" |
 |
Idempotent
|
A . A = A
|
A in series with
A = "A" |
 |
Idempotent
|
NOT A = A
|
NOT NOT A
(double negative) = "A" |
Double Negation
|
|
A + A = 1
|
A in parallel
with
NOT A = "CLOSED" |
 |
Complement
|
A . A = 0
|
A in series with
NOT A = "OPEN" |
 |
Complement
|
A+B = B+A
|
A in parallel
with B =
B in parallel with A |
 |
Commutative
|
A.B = B.A
|
A in series with
B =
B in series with A |
 |
Commutative
|
A+B = A.B
|
invert and
replace OR with AND
|
de Morgan’s
Theorem
|
|
A.B = A+B
|
invert and
replace AND with OR
|
de Morgan’s
Theorem
|
Description of the Laws of Boolean Algebra
·
Identity Law –
A term OR
with a “0” or AND
with a “1” will always equal that term.
o A + 0 = A A
variable OR with 0 is always equal to the variable.
o A . 1 = A A
variable AND with 1 is always equal to the variable.
·
Idempotent Law –
An input that is AND
or OR
with itself is equal to that input.
o A + A = A A
variable OR with itself is always equal to the variable.
o A . A = A A
variable AND with itself is always equal to the variable.
·
Complement Law –
A term AND
with its complement equals “0” and a term OR with its complement equals “1”.
o A . A = 0 A
variable AND with its complement is always equal to 0.
o A + A = 1 A
variable OR with its complement is always equal to 1.
·
Commutative Law –
The order of application of two separate terms is not important.
o A . B = B
. A The order in
which two variables are AND makes no difference.
o A + B = B
+ A The order in
which two variables are OR makes no difference.
·
Double Negation Law –
A term that is inverted twice is equal to the original term.
o
A = A A
double complement of a variable is always equal to the variable.
·
Distributive Law –
This law permits the multiplying or factoring out of an expression.
o A(B +
C) = A.B + A.C (OR
Distributive Law)
o A +
(B.C) = (A + B).(A + C) (AND
Distributive Law)
·
Absorptive Law –
This law enables a reduction in a complicated expression to a simpler one by
absorbing like terms.
o A +
(A.B) = A (OR
Absorption Law)
o A(A +
B) = A (AND
Absorption Law)
·
Associative Law –
This law allows the removal of brackets from an expression and regrouping of
the variables.
o A
+ (B + C) = (A + B) + C = A + B +
C (OR Associate Law)
o A(B.C) = (A.B)C = A
. B . C (AND Associate Law)
·
de Morgan´s
Theorem – There are two “de Morgan´s”
rules or theorems,
(1)
Two separate terms NOR
together is the same as the two terms inverted (Complement) and AND for example: A+B = A . B
(2)
Two separate terms NAND
together is the same as the two terms inverted (Complement) and OR for example: A.B = A + B
Laws of Boolean
Algebra Example No1
Using the
above laws, simplify the following expression: (A + B)(A + C)
Q =
|
(A + B).(A + C)
|
|
A.A + A.C + A.B + B.C
|
– Distributive law
|
|
A + A.C + A.B + B.C
|
– Idempotent AND law (A.A = A)
|
|
A(1 + C) + A.B + B.C
|
– Distributive law
|
|
A.1 + A.B + B.C
|
– Identity OR law (1 + C = 1)
|
|
A(1 + B) + B.C
|
– Distributive law
|
|
A.1 + B.C
|
– Identity OR law (1 + B = 1)
|
|
Q =
|
A + (B.C)
|
– Identity AND law (A.1 = A)
|
Then
the expression: (A
+ B)(A + C) can be simplified to A + (B.C) as in the
Distributive law.
No comments
Post your comments