Notes by Lex Toumbourou

Lesson 5.1 The basics

Video: 5.101 Introduction to Boolean algebra

• Boolean Algebra
  • History
    • 384-322 BC: Aristotle develops the foundations of logic.
    • 1854: George Boole published An investigation of the laws of thought
    • 1904: H.E. Huntington wrote Sets of independent postulates for the algebra of logic.
    • 1938: Claude Shannon wrote a thesis: A symbolic analysis of relay switching
  • Boolean algebra is the foundation of computer circuit analysis.
    • Basic building block for designing transistors, basic elements in processors.
    • Consider IoT fire system: when high heat is detected, spray water.
  • Two-valued Boolean Algebra
    • Most well-known form of Boolean algebra is 2 valued system:
      • variables take value in set {0, 1}
      • operators + and . correspond to OR and AND.
    • Used to describe and design digital circuits.
• Operations of Boolean Algebra
  • Based on 3 fundamental operations:
    • AND
      • logical product, intersection or conjunction
      • represented as x . y, $x \cap y$ or $x \wedge y$.
    • OR
      • logical sum, union or disjunction
      • represented as $x + y$, $x \cup y$, $x \lor y$
    • NOT
      • logical complement or negation
      • represented as $x'$, $\overline{x}$ or $\neg x$
  • When parentheses are not used, orperators have order of prefs: NOT > AND > OR.
• Operations of Boolean algebra
  • The truth tables for the 3 operations can be represented as follows:

5.103 Postulates of Boolean algebra

• Huntington's Postulates
  • Huntington's posulates define 6 axioms that must be satisfied by any Boolean algebra:
    • closure with respect to the operators:
      • any result of logical operation belongs to the set {0, 1}
    • identity eleements with respect to the operators:
      • $x + 0 = x$
      • $x \ . \ 1 = x$
    • commutativity with respect to the operators (dot and .):
      • $x + y = y + x$
      • $x . y = y . x$
    • distributivity:
      • $x(y + z) = (x . y) + (x . z)$
      • $x + (y . z) = (x + y) . (x + z)$
    • commutativity
      • $x + y = y + x$
      • $x . y = y. x$
    • distributivity
      • $x(y + z) = (x . y) + (x . z)$
      • $x + (y . z) = (x + y) . (x + z)$
    • complements exist for all elements
      • $x + x' = 1$
      • $x . x' = 0$
    • distinct elements
      • $0 \ne 1$

• Basic Theorems of Boolean Algebra

  • Using the 6 axioms of Boolean algebra, we can find these useful theorems for analysing and designing circuits
    • theorem 1: idempotent laws
      • $x + x = x$
      • $x . x = x$
    • theorem 2: tautology and contradiction
      • $x + 1 = 1$
      • $x . 0 = 0$
    • theorem 3: involution
      • $(x')' = x$
    • theorem 4: associative laws
      • $(x + y) +z = x + (y + z)$
      • $(x . y) . z = x . (y . z)$
    • theorem 5: absorption laws
      • $x + (x . y) = x$
      • $x . (x + y) = x$
    • theorem 6: uniqueness of complement
      • if $y + x = 1$ and $y . x = 0$ then $x = y'$
    • theorem 7: inversion law
      • $0' = 1$, $1' = 0$

  • De Morgan's Theorems

    • Theorem 1
      • The complement of a product of variables is equal to the sum of the complements of the variables: $\overline{x. y} = \overline{x} + \overline{y}$

    • Theorem 2

      • The complement of a sum of variables is equal to the product of the complements of the variables: $\overline{x + y} = \overline{x} . \overline{y}$

      

  • Proof of distributivity of + over .

    • A truth table to prove the distributivity of + over . using truth tables.
  • Principle of duality
    • Starting with a Boolean relation, we can build another equivalent Boolean relation by:
      • changing each OR (+) sign to an AND (.) sign
      • changing each AND (.) sign to an OR (+) sign.
      • changing each 0 to 1 and each 1 to 0.
    • Example
      • Since A + BC = (A + B)(A + C) (by distributive law), we can build another relation using the duality principle: $A(B + C) = AB + AC$
    • Examples
      • Consider the boolean equations:
        • $e1: (a . 1) . (0 + \overline{a}) = 0$
        • e2: $a + \overline{a} . b = a + b$
      • Dual equations of e1 and e2:
        • Dual of e1: $(a + 0) + (1 . \overline{a}) = 1$
        • Dual of e2: $a . (\overline{a} + b) = a . b$
  • Ways of proving theorems
  • 4 ways in general to prove equivalence of Boolean relations:
    • perfect induction by showing 2 expressions have identical truth tables: tedious if more than 2 vars.
    • axiomatic proof by applying Huntington's postulates or theorems to the expressions, until identical expressions are found.
    • duality principle every theorem in Boolean algebra remains valid if we interchange all ANDs and ORs and interchange all 0s and 1s.
    • contradiction by assuming the hypothesis is false then proviing that the conclusion is false.
  • Examples
    • Proving absorption theorem
      • The absorption theorem can be proved using perfect induction, by writing a truth table.
      • It can also be proved directly:
        • From $x + (x . y) = x$, if we apply the duality principle, we can deduce: $x . (x + y) = x$

\begin{align} x + (x . y) &= (x . 1) + (x . y) \text{ by } x .1 = x \\ &= x . (1 + y) \text{ by distributivity } \\ &= x . (y + 1) \text{ by commutativity } \\ &= x . 1 \text{ by } y + 1 = 1 \\ &= x \text{ by } x.1 = x \\ \end{align}

5.105 Boolean functions

• Boolean Function
  • A boolean function defines a mapping from one or multiple Boolean input values to a Boolean output value.
  • For $n$ Boolean input values, there are $2^n$ possible combinations.
    • For example, a 3-input function $f$ can be completely defined with an 8-row truth table.
  • Algebraic forms
    • There is only one way to represent a Boolean function in a truth table.
    • In algebraic form, a function can be expressed in a variety of ways:
      • For example these are both algebraic representations of the same truth table:
        • $f(x) = x + x' . y$
        • $f(x) = x + y$
  • Standardised forms of a function
    • The two most common standardised forms:
      • sum-of-products form
      • product-of-sums form
      • Sum-of-Products Form:
        • Variables built using the AND operator, are summed together using the OR operator.
        • Example: $f(x, y, z) = xy + xz + yz$
      • Product-of-Sums Form
        • Variables built using the OR operator, are multiplied together using the AND operator.
        • Example: $f(x, y, z) = (x + y)(x + z)(y + z)$
      • The sum-of-products form is easier to use so it's used by the course.
• Building a sum-of-products form
  • 1. Focus on the values of the variable that make the function equal to $1$.
  • 1. If an input equals $1$, it appear uncomplemented in the expression.
  • 1. If an input equals 0, it appears complemented in the expression (and its corresponding complete is used).
  • 1. the function f is then expressed as the sum of products of all the terms for which f = 1
  • Example
    • Let's consider the function f represented by the following truth trable.
      • Can be expressed as:
        • $f(x, y) = x ' y + xy' + xy$
• Useful functions
  • The "exclusive-or" function: $x \oplus y$:
    • defined as "true if either x or y is true, but not both"
    • represented by this truth table:
    • can be expressed as:
      • $x \oplus y = x ' y + xy'$
  • The "implies" function: $x \rightarrow y$:
    • defined as "if x then y"
    • represented by this truth table:
    • can be expressed as:
      • $x \rightarrow y = x' + y$