Boolean Logic I

(Usage hints for this presentation)

IT Systems, Summer Term 2024
Dr. Jens Lechtenbörger (License Information)

Chair of Data Science: Machine Learning and Data Engineering (Prof. Gieseke)
Dept. of Information Systems
University of Münster, Germany

1. Introduction

1.1. Today’s Core Question

How to implement Boolean functions systematically?

1.2. Learning Objectives

Generate DNF from truth table
Simplify Boolean expressions
Transform DNF graphically to All-Nand circuit
Build chips of project 1

1.3. Retrieval Practice

Recall
- 0 and 1 represent False and True
- Rows of truth tables ordered by binary counting
Write down the truth table for Nand now

Agenda

2. Boolean Logic

2.1. Boolean Algebra

Mathematical view on logic, going back to (Boole 1847)

Boolean algebra formalizes a branch of logic in mathematical terms. It is named after George Boole, who wrote two seminal books on this topic in the middle of the nineteenth century.
- Algebra \(B = \{0, 1\}\) with three operations for \(x, y \in B\):
  
  As you see here, Boolean algebra is defined with three operations over a set with two elements, namely 0 and 1, which represent truth values.
  - Or: \(x \lor y = \max(x, y)\) (\(= x+y = \text{Or}(x, y)\))
    
    The Or operation can be defined as maximum of two values: If at least one value is 1, the result is 1. You see typical symbols that are used to denote this operation. Subsequently, we usually use the plus sign. Consequently, we may refer to the result of the operation as sum (with the special interpretation that the “sum” of one and one equals one).
  - And: \(x \land y = \min(x, y)\) (\(= x \cdot y = xy = \text{And}(x, y)\))
    
    The And operation can be defined as minimum of two values: If at least one value is 0, the result is 0. Again, you see typical symbols that are used to denote this operation. Subsequently, we usually use multiplication, which does not require any symbol. Consequently, we may refer to the result of the operation as product.
  - Not: \(\lnot x = 1-x\) (\(=\bar{x} = \text{Not}(x)\))
    
    The Not operation flips, or inverts, or negates a value. Subsequently, we usually use an overline to indicate a negation.
- Precedence: Not binds strongest, then And, then Or
  - E.g.: \(\lnot{x_1} x_2 + \lnot{x_3} = ((\lnot{x_1}) x_2) + (\lnot{x_3})\)
  - Use parentheses for more complex cases or if in doubt
  As usual, parentheses can be used to structure more complex expressions. Without parentheses, the precedence rules shown here apply.
- Lots of laws/equalities can be proven, see later slide
  
  Based on this definition, lots of laws or equalities among Boolean expressions can be proven. This will be revisited on later slides.

2.2. Boolean Functions and Truth Tables

Boolean functions have arguments and result in \(B\)
- \(k\)-ary function \(f: B^k \to B\) for \(k \geq 0\)
  
  Boolean functions can take any number of Boolean arguments and return a Boolean value. Although the special case of 0 arguments is included here, we do not consider such degenerate functions subsequently. In case you are curious, a function without arguments denotes a constant.
  - E.g., \(k=3\): \(f_0(x_1, x_2, x_3) = x_1 x_2 + \bar{x_3}\)
    
    Consider the Boolean function \(f_0\), which takes 3 arguments. Clearly, this function will produce a uniquely defined output value for each of the possible combinations of input values.
  - Can use truth table with \(2^k\) rows and \(k+1\) columns to represent \(f\)
    
    \(x_1\) \(x_2\) \(x_3\) \(f_0(x_1, x_2, x_3)\)
    
    0 0 0 1
    
    0 0 1 0
    
    0 1 0 1
    
    0 1 1 0
    
    1 0 0 1
    
    1 0 1 0
    
    1 1 0 1
    
    1 1 1 1
    - See table to right for \(f_0\)
    Please convince yourself that the values in the final column of the truth table here are those produced by the expression defining \(f_0\).
  - Interpret argument in row as binary number, called index: \((x_1 x_2 \ldots k_k)_2\)
    - For \(k=3\), count from \(0 = (000)_2\) to \(2^k - 1 = 7 = (111)_2\)
    Note that the truth table lists all possible input combinations for 3 variables.
    
    Moreover, each input combination can be understood as binary number in the range from 0 to 7. Concerning terminology, this binary number is called index.
  - Index \(i\) with \(f(i) = 1\) is called positive index
    - 0, 2, 4, 6, 7 are positive indices of \(f_0\)
    If the output value produced for an index is 1, the index is a positive one. (Otherwise, the index is negative.)
    
    Please verify that the indices listed here are the positive ones for \(f_0\).
  - Minterm: Product/And-operation, in which each variable occurs once, potentially negated
    - E.g., \(x_1 x_2 x_3\), \(x_1 x_2 \bar{x_3}\)
    Again concerning terminology, a minterm is a product that combines all input variables, where each variable may be negated or not. Examples are shown here.

\(x_1\)	\(x_2\)	\(x_3\)	\(f_0(x_1, x_2, x_3)\)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

2.3. Boolean Function as Sum of Products

Representation Theorem
- Every Boolean function \(f\) can be uniquely represented as sum of all minterms for its positive indices \(I\), i.e.: \(f = \sum_{i \in I} m_i\)
  
  An important theorem of Boolean logic states that every Boolean function can be uniquely represented as sum of products. More precisely, we sum up minterms for the positive indices.
  - Minterm for index \(i\), denoted \(m_i\): Variable occurs negated if its value in row \(i\) is 0; otherwise, variable without negation
    
    In that sum, the binary representation of an index number specifies which variables to negate in a minterm: If the bit for a variable is 0, it is negated. If the bit is 1, the variable is not negated.
    - E.g., \(k=3\): \(m_0 = \bar{x_1} \bar{x_2} \bar{x_3}\), \(m_6 = x_1 x_2 \bar{x_3}\)
      
      \(x_1\) \(x_2\) \(x_3\) \(f_0(x_1, x_2, x_3)\)
      
      0 0 0 1
      
      0 0 1 0
      
      0 1 0 1
      
      0 1 1 0
      
      1 0 0 1
      
      1 0 1 0
      
      1 1 0 1
      
      1 1 1 1
      
      For example, in minterm 0 the binary representation contains three zeros. Hence, all three variables are negated.
      
      As another examples, as 6 is 1 1 0 in binary, in minterm 6 the first two variables are not negated, while the third one is negated.
  - Theorem applied to \(f_0\) with \(I = \{0, 2, 4, 6, 7\}\)
    - \(f_0 = m_0 + m_2 + m_4 + m_6 + m_7\)
    - \(f_0 = \bar{x_1} \bar{x_2} \bar{x_3} + \bar{x_1} {x_2} \bar{x_3} + {x_1} \bar{x_2} \bar{x_3} + {x_1} {x_2} \bar{x_3} + x_1 x_2 x_3\)
      
      Here you see the result of applying the theorem to \(f_0\).
  - Such a sum (logical Or) of products (logical And) is also called Disjunctive Normal Form (DNF)
    - Disjunction is another word for logical Or
    - (Conjunction is another word for logical And; conjunctive normal form exists as well…)
    As we sum up minterms, which are products of variables, the result is called sum of products. As disjunction is another word for logical Or, the result is also called disjunctive normal form, DNF for short. Besides, conjunctive normal forms exists as well, but we do not consider them.

\(x_1\)	\(x_2\)	\(x_3\)	\(f_0(x_1, x_2, x_3)\)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

2.3.1. Observations

Previous theorem implies that every Boolean function can be expressed using only And, Or, Not
- DNF is a canonical representation
We say that {And, Or, Not} is functionally complete
In Nand To Tetris, along the way (by construction) we prove that {Nand} is functionally complete
- Recall: Not(x) = Nand(x, x), And(x, y) = ...

2.4. Laws of Boolean Algebra

Sample laws
- Commutativity: \(xy = yx\), \(x+y = y+x\)
- Associativity: \((xy)z = x(yz)\), \((x+y)+z = x+(y+z)\)
- Fusion: \((x+y)x = x\), \((xy)+x = x\)
- Distributivity: \(x(y+z) = xy+xz\), \(x+yz = (x+y)(x+z)\)
- Complements: \(x+\bar{x} = 1\), \(x\bar{x} = 0\)
- De Morgan: \(\overline{x+y} = \bar{x}\bar{y}, \overline{xy} = \bar{x}+\bar{y}\)
- \(x+0=x\), \(x+1 = 1\), \(x\cdot 0 = 0\), \(x\cdot 1 = x\)
- \(x = x+x = xx = \bar{\bar{x}}\)
- Use above laws for simplifications, proofs of equality

2.5. Sample Proof with Truth Table

Proof for one of the De Morgan rules: \(\overline{xy} = \bar{x}+\bar{y}\)

Sub-expressions in truth table

\(x\)	\(y\)	\(xy\)	\(\boldsymbol{\overline{xy}}\)	\(\bar{x}\)	\(\bar{y}\)	\(\boldsymbol{\bar{x}+\bar{y}}\)
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Note that column values corresponding to left- and right-hand side of rule are identical (highlighted)
Thus, expressions are equal (as Boolean functions)

In this case, the values in the columns for the left and right hand side are equal. Thus, the functions represented by both columns are equal.

3. Self-Study Tasks

3.1. DNF

What do the gates And, Or, Nand do?
Consider \(f_1(x_1, x_2, x_3) = \bar{x_1}\overline{(\bar{x_2} + \bar{x_3})} + x_1x_3\).
- Write down the truth table for \(f_1\). Then determine its positive indices and its DNF as sum of minterms.
- Simplify the DNF of \(f_1\) using laws of Boolean algebra. (The next presentation contains examples.)

You can verify your answers in Learnweb.

3.2. Sample proofs

Prove laws of Boolean algebra that seem surprising
- E.g., second De Morgan rule

Bibliography

Boole, George. 1847. The Mathematical Analysis of Logic, Being an Essay towards a Calculus of Deductive Reasoning. https://www.gutenberg.org/files/36884/36884-pdf.pdf.

License Information

Source files are available on GitLab (check out embedded submodules) under free licenses. Icons of custom controls are by @fontawesome, released under CC BY 4.0.