© P.Prinetto - all rights reserved Version 1.1 3.1.13.1 – An introduction to Boolean AlgebrasECE 465An introduction to Boolean AlgebrasPaolo PRINETTOPolitecnico di Torino (Italy)University of Illinois at Chicago, IL (USA)[email protected]@uic.eduwww.testgroup.polito.itLecture 3.123.1 Goal• This lecture first provides several definitions of Boolean Algebras, and then focuses on some significant theorems and properties. • It eventually introduces Boolean Expressionsand Boolean Functions.33.1 Prerequisites• Students are assumed to be familiar with the fundamental concepts of:− Algebras, as presented, for instance, in:⋅ F.M. Brown: “Boolean reasoning: the logic of boolean equations,” Kluwer Academic Publisher, Boston MA (USA), 1990, (chapter 1, pp. 1-21)43.1 Prerequisites (cont’d)− Number systems and codes, as presented, for instance, in:⋅ E.J.McCluskey: “Logic design principles with emphasis on testable semicustom circuits”, Prentice-Hall, Englewood Cliffs, NJ, USA, 1986, (chapter 1, pp. 1-28) or53.1 Prerequisites (cont’d)⋅ [Haye_94] chapter 2, pp. 51-123or⋅ M. Mezzalama, N. Montefusco, P. Prinetto:“Aritmetica degli elaboratori e codifica dell’informazione”,UTET, Torino (Italy), 1989 (in Italian), (chapter 1, pp. 1-38).63.1 Homework• Prove some of the properties of Boolean Algebras, presented in slides 39 ÷ 59.© P.Prinetto - all rights reserved Version 1.1 3.1.23.1 – An introduction to Boolean AlgebrasECE 46573.1 Further readings• Students interested in a deeper knowledge of the arguments covered in this lecture can refer, for instance, to:− F.M. Brown: “Boolean reasoning: the logic of boolean equations,” Kluwer Academic Publisher, Boston MA (USA), 1990, (chapter 2, pp. 23-69 )83.1 Outline• Boolean Algebras Definitions • Examples of Boolean Algebras• Boolean Algebras properties• Boolean Expressions• Boolean Functions.93.1 Boolean Algebras Definitions Boolean Algebras are defined, in the literature, in many different ways:• definition by lattices• definition by properties• definition by postulates [Huntington].103.1 Definition by latticesA Boolean Algebra is a complemented distributive lattice.113.1 Definition through propertiesA Boolean Algebra is an algebraic system ( B , + , · , 0 , 1 )where:• B is a set, called the carrier• + and · are binary operations on B• 0 and 1 are distinct members of Bwhich has the following properties:123.1 P1: idempotent∀ a ∈ B:• a + a = a • a · a = a© P.Prinetto - all rights reserved Version 1.1 3.1.33.1 – An introduction to Boolean AlgebrasECE 465133.1 P2: commutative∀ a, b ∈ B:• a + b = b + a • a · b = b · a 143.1 P3: associative∀ a, b, c ∈ B:• a + (b + c) = (a + b) + c = a + b + c• a · (b · c) = (a · b) · c = a · b · c 153.1 P4: absorptive∀ a, b ∈ B: • a + (a · b) = a • a · (a + b) = a 163.1 P5: distributiveEach operation distributes w.r.t. the other one: a · (b + c) = a · b + a · ca + b · c = (a + b) · (a + c)173.1 P6: existence of the complement• ∀ a ∈ B, ∃ a’ ∈ B |− a + a’ = 1− a · a’ = 0.The element a’ is referred to as complement of a.183.1 Definition by postulatesA Boolean Algebra is an algebraic system ( B , + , · , 0 , 1 )where:• B is a set• + and · are binary operations in B• 0 and 1 are distinct elements in Bsatisfying the following postulates:© P.Prinetto - all rights reserved Version 1.1 3.1.43.1 – An introduction to Boolean AlgebrasECE 465193.1 A1: closure∀ a, b ∈ B:• a + b ∈ B• a · b ∈ B203.1 A2 : commutative∀ a, b ∈ B: • a + b = b + a • a · b = b · a213.1 A3: distributive∀ a, b, c ∈ B: • a · (b + c) = a · b + a · c• a + b · c = (a + b) · (a + c)223.1 A4: identities∃ 0 ∈ B | ∀ a ∈ B, a + 0 = a∃ 1 ∈ B | ∀ a ∈ B, a · 1 = a233.1 A5: existence of the complement∀ a ∈ B, ∃ a’ ∈ B |• a + a’ = 1• a · a’ = 0.243.1 Some definitions• The elements of the carrier set B={0,1} are called constants• All the symbols that get values ∈ B are calledvariables (hereinafter they will be referred to as x1, x2, …,xn)• A letter is a constant or a variable• A literal is a letter or its complement.© P.Prinetto - all rights reserved Version 1.1 3.1.53.1 – An introduction to Boolean AlgebrasECE 465253.1 Outline• Boolean Algebras Definitions⇒Examples of Boolean Algebras• Boolean Algebras properties• Boolean Expressions• Boolean Functions.263.1 Examples of Boolean AlgebrasLet us consider some examples of Boolean Algebras:• the algebra of classes• propositional algebra• arithmetic Boolean Algebras• binary Boolean Algebra• quaternary Boolean Algebra.273.1 The algebra of classesSuppose that every set of interest is a subset of a fixed nonempty set S.We call • S a universal set • its subsets the classes of S.The algebra of classes consists of the set 2S(the set of subsets of S) together with two operations on 2S , namely union and intersection.283.1 This algebra satisfies the postulates for a Boolean Algebra, provided the substitutions:B ↔ 2S+ ↔∪· ↔∩0 ↔∅1 ↔ SThus, the algebraic system ( 2S, ∪, ∩, ∅, S )ia a Boolean Algebra.The algebra of classes (cont'd)293.1 PropositionsA proposition is a formula which is necessarily TRUE or FALSE (principle of the excluded third), but cannot be both (principle of no contradiction).As a consequence, Russell's paradox :“this sentence is false”is not a proposition, since if it is assumed to be TRUE its content implies that is is FALSE, and vice-versa.303.1 Propositional calculusLet:P a set of propositional functionsF the formula which is always false (contradiction)T the formula which is always true (tautology)∨ the disjunction (or)∧ the conjunction (and)¬ the negation (not)© P.Prinetto - all rights reserved Version 1.1 3.1.63.1 – An introduction to Boolean AlgebrasECE 465313.1 The system( P, ∨ , ∧ , F , T )is a Boolean Algebra:• B ↔ P• + ↔ ∨• · ↔ ∧• 0 ↔ F• 1 ↔ TPropositional calculus (cont'd)323.1 Arithmetic Boolean AlgebraLet:• n be the result of a product of the elements of a set of prime numbers• D the set of all the dividers of n • lcm the operation that evaluates the lowest common multiple• GCD the operation that evaluates the Greatest Common Divisor.333.1 The algebraic system:( D, lcm, GCD, 1, n )Is a Boolean Algebra:• B ↔ D• + ↔