# Department of Computer and Information Science, School of

Department of Computer and Information Science, School of Science, IUPUI CSCI 240 Boolean Algebra Standard Forms Dale Roberts, Lecturer Computer Science, IUPUI E-mail: [email protected] Dale Roberts

Standard Form Like regular algebra, Boolean equations can be expressed as a sum of products. Each product is a term of the equation. Consider the term xyxz. We define a term to be a Fundamental Product (FP) if it does not repeat any literal. Since our term repeats x, is it not FP. You can always minimize a term to make it FP. xyxz = xxyz = 0yz (which law) = 0 (which law?) An expression E is sum-of-products form if it is the sum of one or more FPs, none of which is included in another. Dale Roberts Sum-of-Products Form

1. Consider E=xz + yz + xyz. This is a sum of products, but is not sum-of-products form because xz is contained within xyz. i.e. it can be reduced. (which law?) 2. Consider E=xz + xyz + xyz. This is already sum-of-products form. Any non-zero Boolean expression can be changed to sumof-products form. (By duality, there is also a product-ofsums form, but it is used less often.) Dale Roberts Converting to Sum-of-Products Form 1. 2. 3.

4. Use DeMorgans Laws and Involution to move complements inside parenthesis until only variables are complemented. Use distributive law to transform in to sum of products Use commutative, idempotent, and complement laws to transform each term into 0 or FP. Use absorption law to make sum-of-products form. Example Consider E=((ab)c)((a+c)(b+c)) E=((ab)+c)((a+c)+(b+c)) DeMorgans Law E=(ab+c)(ac+bc) DeMorgans and Involution Laws

E=abac + abbc +acc + bcc Distributive Law E=abc + abc + ac + 0 Idempotent and Complement E=ac + abc Absorption Law Dale Roberts Complete Sum-of-Products Form A complete sum-of-products form is a sum-of-products form where each term involves all the variables. (Each term will have the same number of literals. You can add missing variables by multiplying by 1, where 1 is of the form x + x. Theorem: Every non-zero Boolean expression can be

placed in complete sum-of-products form, and it is unique. Dale Roberts Complete Sum-of-Products Example Express E(x,y,z) = (x + y) + xy in complete sum-ofproducts form. E = xy + xy DeMorgans Law. If we didnt know z was involved, wed think we were done. E=xy(z + z) + xy(z + z) E=xyz + xyz + xyz + xyz Distributive Law (Dont simplify using Absorption, or youll take it back out of Complete S-O-P form)

Dale Roberts Sources Lipschutz, Discrete Mathematics Mowle, A Systematic Approach to Digital Logic Design Dale Roberts

## Recently Viewed Presentations

• Phylogenetics I Evolution Evolution of new organisms is driven by Mutations The DNA sequence can be changed due to single base changes, deletion/insertion of DNA segments, etc. Selection bias Theory of Evolution Basic idea speciation events lead to creation of...
• 7±2 Deadly Sins in Media Violence Research. Craig A. Anderson, Distinguished Professor. Digital Media & Developing Minds Congress. Cold Spring Harbor Laboratory, Oct. 15-18, 2018
• 1.1 How Economists Think. Economists assume that people customarily engage in rational behaviour. Each one of us makes choices by logically weighing the personal benefits and costs of every available action then selects the most attractive option based on our...
• LGBT Pioneers in STEM The lesbian, gay, bisexual and trans people who impacted on science, technology, maths and science and who helped change the world
• Partial Molar Quantities, Activities, Mixing Properties Composition (X) is a critical variable, as well at temperature (T) and pressure (P) Variation of a thermodynamic parameter with number of moles of one component, all other compositional variables, T, P held constant
• Proyecto de mejora continua de la calidad por EE.SS., programa de monitoreo de PMCC. Micro Redes, Hospitales III-1. Porcentaje de proyectos de mejora de la calidad implementados. N° de proyectos de salud de mejora de la calidad de atención en...
• Path to Confederation Notes. Lord Elgin and the Rebellion Losses Bill. What was the Rebellion Losses Bill? ... George Brown of Clear Grits joins Cartier and Macdonald to form the . Great Coalition Government. Goal: Confederation of all the colonies.
• "Pure Vowels" "Diphthongs - Vowel pairs" ... In Romance languages, like French and Spanish, vowels are predictable. Take for example the word "banana." In Spanish the three "a" sounds are identical, but in English, the because the stress falls on...