Transcript Boolean Algebra_last_2

Boolean rules for simplification
Dr. Ahmed Telba
midterms
• Mid1
• Sunday 16 March 2014
• Mid2
• Sunday 26 April 2014
• exploration of Boolean algebra
•
•
•
•
•
•
•
•
•
•
Adding
0+0=0
0+1=1
1+0=1
1+1=1
Multiplication
0×0=0
0×1=0
1×0=0
1×1=1
•
•
•
•
•
•
REVIEW:
• Boolean addition is equivalent to the OR logic function, as well as parallel switch contacts.
• Boolean multiplication is equivalent to the AND logic function, as well as series switch
contacts.
• Boolean complementation is equivalent to the NOT logic function, as well as normally closed
relay contacts.
Commutative Laws
•
•
•
•
•
•
•
•
•
►The commutative law of addition for two variables is written as
A+B = B+A
This law states that the order in which the variables are OR ed makes no
difference.
Remember, in Boolean algebra as applied to logic circuits,
addition and the OR operation are the same. Fig-1 illustrates the
commutative law as applied to the OR gate and shows that it doesn't matter
to which input each variable is applied. (The symbol ≡ means "equivalent
to.").
Commutative laws
• ►The associative law of addition is written as follows for
three variables: adding using 2-input OR
• A + (B + C) = (A + B) + C
• The associative law of multiplication is written as follows for
three variables:
• A(BC) = (AB)C
• this law as applied to 2-input AND gates.
•
•
•
•
•
Distributive Law:
►The distributive law is written for three variables as follows:
A(B + C) = AB + AC
AB + AC = A(B + C).
Fig.(3) illustrates the distributive law in terms
of gate implementation.
Rules of Boolean Algebra
• Rules of Boolean Algebra
• Rule 1.
A+0=A
• Rule 2.
A+1=1
Rules
• Rule 3.
A.0=0
• Rule 4.
A.1=A
Rules
• Rule 5.
A+A=A
• Rule 6.
A + A” = 1
• Rule 7.
• Rule 8.
A.A=A
• Rule 9
• Rule 10.
A + AB = A
DEMORGAN'S THEOREMS

•
•
•
•
The complement of a product of variables is equal to the sum of the
complements of the variables,
Stated another way,
The complement of two or more ANDed variables is equivalent to the OR of the complements of
the individual variables.
The formula for expressing this theorem for two variables is
• DeMorgan's second theorem is stated as follows:
• The complement of a sum of variables is equal to the product of the
complements of the variables
• The formula for expressing this theorem for two variables is
EXAMPLES
• Logic
commutative property
Distributive
Boolean rules for simplification
•
•
•
•
•
Boolean rules for simplification
Boolean algebra finds its most practical use in the simplification of logic circuits. If we translate a logic circuit's function
into symbolic (Boolean) form, and apply certain algebraic rules to the resulting equation to reduce the number of terms
and/or arithmetic operations, the simplified equation may be translated back into circuit form for a logic circuit
performing the same function with fewer components. If equivalent function may be achieved with fewer components,
the result will be increased reliability and decreased cost of manufacture.
To this end, there are several rules of Boolean algebra presented in this section for use in reducing expressions to their
simplest forms. The identities and properties already reviewed in this chapter are very useful in Boolean simplification,
and for the most part bear similarity to many identities and properties of "normal" algebra. However, the rules shown in
this section are all unique to Boolean mathematics.
This rule may be proven symbolically by factoring an "A" out of the two terms,
then applying the rules of A + 1 = 1 and 1A = A to achieve the final result:
Circuit simplification examples
The Exclusive-OR function
• XNOR
Fan in
• Fan in IF you have gate with inputs more tan
you need then used figure
• If you have 2 input and you need 3 input used
this figure
Logical Expression
• If you have this fig haw many gates needed
• Important relations in simplifying logic systems
•
Draw the logic diagram of equation then simplified using Boolean and DeMorgan's
DeMorgan's Theorems
DeMorgan's Theorems
DeMorgan's Theorems
DeMorgan's Theorems
• REVIEW
• DeMorgan's Theorems describe the equivalence between gates with
inverted inputs and gates with inverted outputs.
• Simply put, a NAND gate is equivalent to a Negative-OR gate, and a NOR
gate is equivalent to a Negative-AND gate.
• When "breaking" a complementation bar in a Boolean expression, the
operation directly underneath the break (addition or multiplication)
reverses, and the broken bar pieces remain over the respective terms.
• It is often easier to approach a problem by breaking the longest
(uppermost) bar before breaking any bars under it. You must never
attempt to break two bars in one step!
• Complementation bars function as grouping symbols. Therefore, when a
bar is broken, the terms underneath it must remain grouped. Parentheses
may be placed around these grouped terms as a help to avoid changing
precedence.
Sum of minterms
• Find 1’s and write as AND then OR for all terms
Minterm representative (sum)
• If you have truth table shown
• Logic minterm equivalent
Product of Maxterms
• Product of Maxterms lock for 0 then anding
Using ∏
AND & OR implementation
Quiz #1
• Review of Boolean Algebra
DeMorgan’s Theorems
• AND USING NOR
Quiz # Answer