Boolean Algebra Basics and Operations

unit 2 n.w
1 / 36
Embed
Share

Explore the fundamentals of Boolean algebra, including basic operations, expressions, truth tables, and key theorems. Learn how Boolean algebra relates to logic gates and switches, and understand how to simplify and manipulate algebraic expressions effectively.

  • Boolean Algebra
  • Operations
  • Logic Gates
  • Expressions
  • Truth Tables
rayaanacharya
ray_lia Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. UNIT 2 Boolean Algebra This chapter in the book includes: Objectives Study Guide 2.1 Introduction 2.2 Basic Operation 2.3 Boolean Expression and Truth Table 2.4 Basic Theorem 2.5 Commutative, Associative and Distributive Laws 2.6 Simplification Theorem 2.7 Multiplying Out and Factoring 2.8 DeMorgan s Laws Problems

  2. Objectives Topics introduced in this chapter: Understand the basic operations and laws of Boolean algebra Relate these operations and laws to AND, OR, NOT gates and switches Prove these laws using a truth table Manipulation of algebraic expression using - Multiplying out - Factoring - Simplifying - Finding the complement of an expression

  3. 2.1 Introduction Boolean Algebra Developed by George Boole Basic mathematics for logic design Restrict to switching circuits Two state values: 0, 1 Switching algebra Boolean Variable : X, Y, Can only have two state values: 0, 1 Representing True(1) or False (0)

  4. 2.2 Basic Operations Basic Operations of Boolean Algebra AND OR NOT Complement Inverse

  5. 2.2 Basic Operations (NOT) NOT (Inverter) 0 = 1 and 1 = 0 ? = 0 if ? =1 ? = 1 if ? = 0 and Gate Symbol

  6. 2.2 Basic Operations (AND) = = = = 0 0 0 0 1 0 1 0 0 1 1 1 AND A B 0 0 0 1 1 0 1 1 C = A B 0 0 0 1 Truth Table Gate Symbol

  7. 2.2 Basic Operations (OR) + = + = + = + = 0 0 0 0 1 1 1 0 1 1 1 1 OR A B 0 0 0 1 1 0 1 1 C = A + B 0 1 1 1 Truth Table Gate Symbol

  8. 2.2 Basic Operations ? Apply to Switch = T A B AND ? ? 1 2 = + T A B OR ? 2 1 ?

  9. 2.3 Boolean Expressions and Truth Tables Boolean Expression Consists of the basic operations to one or more Boolean variables or constants Precedence Parentheses () NOT AND OR Example ?? + ? + ?? ? ? + ?

  10. 2.3 Boolean Expressions and Truth Tables (?? + ?) Boolean Expression Logic Circuit for Boolean Expression ?? ? (?? + ?) ? ? ?

  11. 2.3 Boolean Expressions and Truth Tables + ?? Boolean Expression ? ? + ? Logic Circuit for Boolean Expression ? (? + ?) ?(? + ?) [? ? + ? ] ? + ?? ? ? ? + ? ? ?? ?

  12. 2.3 Boolean Expressions and Truth Tables Evaluation of Boolean Expression By substituting a value 0 or 1 for each variable Example Evaluation of when A=B=C=1, D=E=0 BE D C A + + )]' ( [ + + 1 ( 1 [ = + + 1 ( 1 [ = + = + = [ ( )]' 0 )] 1 0 )]' 0 0 0 0 A C D BE Literal Each appearance of a variable or its complement in a Boolean expression ' ' ' bc a b a c ab + + + ' ' ' b c Example 10 literals Corresponds to a gate input

  13. 2.3 Boolean Expressions and Truth Tables Truth Table Specifies the value of a Boolean expression for every possible combination of value of the variables in the expression Specifies the output values for a circuit logic gates in terms of the values of the input variables Example: 2-input logic circuit A B 0 0 0 1 1 0 1 1 A 1 1 0 0 F = A + B 1 1 0 1 ? ? ? ? = ? + ? ?

  14. 2.3 Boolean Expressions and Truth Tables ?? + ? = (? + ?)(? + ?) Proof an equation using truth table n variable needs 2 2 2 = 2? rows. n times Truth table (A + C) (B + C) A B C A + C B AB AB + C B + C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1

  15. 2.4 Basic Theorems + = = 0 1 X X X X Operations with 0, 1 + = = 1 1 0 0 X X + = = X X X X X X Idempotent Laws = ( )' ' X X Involution Laws + = = ' 1 ' 0 X X X X Complementary Laws + + = ( ' ) 1 1 AB D E Example + + = ( ' )( ' )' 0 AB D AB D

  16. 2.4 Basic Theorems with Switch Circuits Equivalent Switch Circuits

  17. 2.4 Basic Theorems with Switch Circuits Equivalent Switch Circuits

  18. 2.4 Basic Theorems with Switch Circuits Equivalent Switch Circuits

  19. 2.4 Basic Theorems with Switch Circuits Equivalent Switch Circuits

  20. 2.5 Commutative, Associative, and Distributive Laws = + = + = ) = ) XY YX X Y Y X Commutative Laws: ( ) ( XY Z X YZ = XYZ ( Associative Laws: + + + + = + + ( ) X Y Z X Y Z X Y Z Proof of Associative Law for AND X Y Z XY YZ (XY)Z X(YZ) 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1

  21. Associative Laws for AND and OR Associative Law Using AND Gates ??? = 1 iff ? = ? = ? = 1 Associative Law Using OR Gates ? + ? + ? = 0 iff ? = ? = ? =0

  22. Distributive Laws Distributive Laws: + ) = + Y ( X Z XY XZ + = + + ( )( ) X YZ X Y X Z Valid only Boolean algebra not for ordinary algebra Proof

  23. 2.6 Simplification Theorems Simplifying the corresponding logic circuit Why Simplify? + = + + = ' ( )( ) ' XY XY X X Y + X ) Y X Useful Theorems for Simplification + = = ( X ( XY + X = X X ' Y = X + + ) ' X Y Y XY XY Y X Y + = + = + = = 1 1 ( ) 1 X XY X XY X Y X X Proof + ) = + = + = ( X X Y XX XY X XY X + = + + = + = + ' Y ( )( ) ' Y ( 1 ) Y XY X Y Y X Y X Y Y Y Y Proof of XY +Y=X+Y with Switches Y Y X X X X

  24. 2.6 Simplification Theorems Application of Simplification Theorem to Equivalent Gate Circuits = + ' = ( ) F A A B AB

  25. 2.6 Simplification Theorems Example 1: Simplify ? = ? ?? + ? Solution: ?? ?? ??? ? = ? ??? ? = ?? ? ?? ? = ? + ?? = ? ? = ?

  26. 2.6 Simplification Theorems Example 2 Z = + + + + + + Simplify [ ' ][ ' ( )' ] A B C D EF A B C D EF Solution : = + = + If we let ' and Y = , X [ + A B C + D (by theore EF = + then ][ ] ' m 2 - 13) Z X Y X Y X = ' Z A B C

  27. 2.6 Simplification Theorems Example 3 Z = + + + + Simplify ( )( ' ' ) ' ( )' AB C B D C E AB C Solution : X = + = + If we let Z = ' ' and ' ' , B + D = C E Y AB C = + then Z ' C (by theore C + m 2 - 14D) XY Y X Y + + ' ' ' ( )' B D E AB

  28. 2.7 Multiplying Out and Factoring Multiplying out using distributive laws can obtain a sum-of-products (SOP) form CD + + ' ' ' AB E AC E Sum-of-product form: + ' + ABC DEFG H + + + ' ' A B C D E + ) + ( A B CD EF Not in Sum-of-product form

  29. 2.7 Multiplying Out and Factoring Example: Multiply out (A+BC)(A+D+E) (Solution 1) = = )( = + Let , , X ( A Y BC + Z D ) E ( + + ) = + + = + Then )( ) A BC + A D E = X Y + X Z X YZ = + + ( A BC D E A BCD BCE (Solution 2) + + + = + 1 ( + + + + ( )( ) A BC A D E A AD + AE + ABC BCD BCE = + + + ) A D E + BC BCD BCE = + A BCD BCE

  30. 2.7 Multiplying Out and Factoring Factoring using distributive laws can obtain a product-of-sums (POS) form + + ' + + ' + ( A B )( ' C D E )( A C E ) ' Product-of-sum form + + + ( AB )( D ) A B C D E F + ' ( ' ) C E

  31. 2.7 Multiplying Out and Factoring Example1: Factor A+B CD (Solution) = = = Let , CD + , ' X + X A Y B Z CD = + = + + + Then ' ( )( ) A = B YZ X Y X Z = + + + ( ' )( ) ( ' )( )( ) A B A CD A B A C A D

  32. Circuits for Sum-of-Products Form AB + CD E + AC E A + B + C + D E

  33. Circuits for Product-of-Sums Form (A +B )(C + D + E)(A + C + E ) AB C(D + E)

  34. 2.8 DeMorgans Laws + = ( )' ' ' X Y X + Y DeMorgan s Laws = ( )' ' ' XY X Y Proof ( X + Y ) ( XY ) X Y X + Y XY X Y X Y X + Y 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 DeMorgan s Laws for n variables + + + + = ( ... = )' ' ' '... X ' X X X X + X X + X + X 1 2 3 1 2 3 n X n + ( ... )' ' ' ' ... ' X X X X X X 1 2 3 1 2 3 n n Example: Find the complement of (A +B)C . = + ]' ' ) ' [( + ' + = + = + ' ( )' C ( )' ' ( )' ' ( )' C ( )' ' A B C A B A B AB C

  35. 2.8 DeMorgans Laws (Dual) = + = ' = + + ' ' ( ' )' ' ( ' )' ( )' ' ( ' )( ) F A B + ' AB + A + ' B AB A B A B Complement of F=A B+AB = = + ' ' ' AA AB B A BB A B AB A B A B A B A B F = A B+AB A B F = A B + AB 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 Dual is formed by replacing AND with OR, OR with AND, 0 with 1, 1 with 0 = + + + + + + = D D ( ...) ... ( ...) ... XYZ X Y Z X Y Z XYZ Other method to obtain dual of an expression Complement the entire expression and complement each variable C + = = ' + C + = + D AB ( ' )' AB ( )' ' C ' A ( B C ) ', so AB ( ' ) A ( B ) ' C

Related


No related presentations.

More Related Content