Boolean Algebra PDF

Content Complement Function Standard Form – Product of Sum (POS) – Sum of Product (SOP) – Minterm – Maxterm MOHD. YAMANI IDRIS/ 1 NOORZAILY MOHAMED NOOR  Boolean Function Boolean function is an expression form containing binar...

Content Complement Function Standard Form – Product of Sum (POS) – Sum of Product (SOP) – Minterm – Maxterm MOHD. YAMANI IDRIS/ 1 NOORZAILY MOHAMED NOOR  Boolean Function Boolean function is an expression form containing binary variable, three-operator binary which are OR, AND, and NOT, sign ‘ and sign = Answer is also in binary We always use sign ‘.’ for AND operator, ‘+’ for OR operator, ‘’’ or ‘¯’ for NOT operator. Sometimes we discard ‘.’ sign if there is no contradiction MOHD. YAMANI IDRIS/ 2 NOORZAILY MOHAMED NOOR  Boolean Function Example: From TT we see that F3=F4 Can you prove it using Boolean Algebra? MOHD. YAMANI IDRIS/ 3 NOORZAILY MOHAMED NOOR  Complement Function Given function F, complement function for this function is F’, it is obtained by exchanging 1 with 0 on the output function F. Example: F1=xyz’ Complement F1’ = (xyz’)’ = x’+y’+(z’)’ (DeMorgan) = x’+y’+z (Involution) MOHD. YAMANI IDRIS/ 4 NOORZAILY MOHAMED NOOR  Complement Function Generally, complement function can be obtained using repeatedly DeMorgan Theorem (A+B+C+…..+Z)’=A’.B’.C’.….Z’ (A.B.C.…..Z)’=A’+B’+C’+.….+Z’ MOHD. YAMANI IDRIS/ 5 NOORZAILY MOHAMED NOOR  Standard Form There are two standard form: Sum-of-Product (SOP) and Product-of- Sum (POS) Literals: Normal variable or in complement form. Example: x, x’, y, y’ **Product: single literal or several literals with logical product (AND) Example: x, xyz’, A’B, AB MOHD. YAMANI IDRIS/ 6 NOORZAILY MOHAMED NOOR  Standard Form **Sum: single literal or several literals with logical sum (OR) Example: x, x+y+z’, A’+B, A+B Sum-of-Product (SOP) expression: single product or several products with logical sum (OR) Example: x, x+yz’,xy’+x’yz, AB+A’B’ Product-of- Sum (POS) expression:single sum or several sum with logical product (AND) Example: x, x.(y+z’),(x+y’)(x’+y+z), (A+B)(A’+B’) MOHD. YAMANI IDRIS/ 7 NOORZAILY MOHAMED NOOR  Standard Form Every Boolean expression can be written either in Sum-of-Product (SOP) expression or Product-of- Sum (POS) MOHD. YAMANI IDRIS/ 8 NOORZAILY MOHAMED NOOR  Minterm & Maxterm Consider two binary variable x,y Every variable can exist as normal literal or in complement form (e.g. x,x’,&y,y’) For two variables, there are four possible combinations with operator AND such as: x’y’,x’y,xy’,xy This product is called minterm Minterm for n variables is the number of “product of n literal from the different variables” MOHD. YAMANI IDRIS/ 9 NOORZAILY MOHAMED NOOR  Minterm & Maxterm Generally, n variable will produce 2n minterm With similar approach, maxterm for n variables is “sum of n literal from the different variables” Example: x’+y’, x’+y, x+y’, x+y Generally, n variable will produce 2n maxterm MOHD. YAMANI IDRIS/ 10 NOORZAILY MOHAMED NOOR  Minterm & Maxterm Minterm and maxterm for 2 variables each is signed with m0 to m3 and M0 to M1. Every minterm is the complement of suitable maxterm Example: m2=xy’ m2’=(xy’)’=x’+(y’)’=x’+y =M2 MOHD. YAMANI IDRIS/ 11 NOORZAILY MOHAMED NOOR  Canonical Form What is canonical/normal form? – It is unique form to represent something Minterm is “product term’ – Can state Boolean Function in Sum-of-Minterm MOHD. YAMANI IDRIS/ 12 NOORZAILY MOHAMED NOOR Canonical Form: Sum of Minterm (SOM) Produce TT: Example MOHD. YAMANI IDRIS/ 13 NOORZAILY MOHAMED NOOR Canonical Form: Sum of Minterm (SOM) Produce Sum-of-Minterm by collecting minterm for the function (where the answer is 1) MOHD. YAMANI IDRIS/ 14 NOORZAILY MOHAMED NOOR Canonical Form: Product of Maxterm (POM) Maxterm is “sum term” For Boolean function, maxterm for function is term with answer 0 Can state Boolean function in Product-of- Maxterm form MOHD. YAMANI IDRIS/ 15 NOORZAILY MOHAMED NOOR Canonical Form: Product of Maxterm (POM) Example: MOHD. YAMANI IDRIS/ 16 NOORZAILY MOHAMED NOOR Canonical Form: Product of Maxterm (POM) Why? Take F2 as example Complement function for F2 is MOHD. YAMANI IDRIS/ 17 NOORZAILY MOHAMED NOOR Canonical Form: Product of Maxterm (POM) From the previous slide F2’=m0+m1+m2 Therefore: Notes: Complement of minterm = Maxterm Each Boolean function can be written in Sum-of- Product and Product-of-Sum expression MOHD. YAMANI IDRIS/ 18 NOORZAILY MOHAMED NOOR Canonical Form: Conversion SOPPOS Sum-of-Minterm => Product-of-Maxterm – Change m to M – Insert minterm which is not in SOM – E.g. F1(A,B,C)=  m(3,4,5,6,7)=  M(0,1,2) Product-of-Maxterm => Sum-of-Minterm – Change M to m – Insert maxterm which is not in POM – E.g. F2(A,B,C)=  M(0,3,5,6)=  m(1,2,4,7) MOHD. YAMANI IDRIS/ 19 NOORZAILY MOHAMED NOOR  Canonical Form: Conversion SOPPOS Sum-of-Minterm for F => Sum-of-Minterm for F’ – Minterm list which is not in SOM of F E.g. Product-of-Maxterm for F => Product-of- Maxterm for F’ – Maxterm list which is not in POM of F E.g. MOHD. YAMANI IDRIS/ 20 NOORZAILY MOHAMED NOOR Canonical Form: Conversion SOPPOS Sum-of-Minterm for F => Product-of-Maxterm for F’ – Change m to M – E.g. F1(A,B,C)=m(3,4,5,6,7) F1’(A,B,C)=M(3,4,5,6,7) Product-of-Maxterm for F=> Sum-of-Minterm for F’ – Change M to m – E.g. F2(A,B,C)=M(0,1,2) F2’(A,B,C)=m(0,1,2) MOHD. YAMANI IDRIS/ 21 NOORZAILY MOHAMED NOOR  Binary Function If n variable, therefore the are 2n possible minterm Each function can be expressed by Sum-of- 2n Minterm, therefore there are 2 different function In two variable case, there is 22=4 possible minterm, and there is 24=16 different binary function The 16 binary function is presented in the next slide MOHD. YAMANI IDRIS/ 22 NOORZAILY MOHAMED NOOR Binary Function MOHD. YAMANI IDRIS/ 23 NOORZAILY MOHAMED NOOR