(Usage hints for this presentation)

IT Systems, Summer Term 2024

Dr. Jens Lechtenbörger (License Information)

- How to implement Boolean functions systematically?

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

- Recall
- 0 and 1 represent False and True
- Rows of truth tables ordered by binary counting

- Write down the truth table for
`Nand`

now

- Part 1
- Break for self-study
- Part 2

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

**Algebra**\(B = \{0, 1\}\) with**three operations**for \(x, y \in B\):**Or**: \(x \lor y = \max(x, y)\) (\(= x+y = \text{Or}(x, y)\))**And**: \(x \land y = \min(x, y)\) (\(= x \cdot y = xy = \text{And}(x, y)\))**Not**: \(\lnot x = 1-x\) (\(=\bar{x} = \text{Not}(x)\))

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

Lots of laws/equalities can be proven, see later slide

**Boolean functions**have arguments and result in \(B\)\(k\)-ary function \(f: B^k \to B\) for \(k \geq 0\)

E.g., \(k=3\): \(f_0(x_1, x_2, x_3) = x_1 x_2 + \bar{x_3}\)

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\)

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\)

Index \(i\) with \(f(i) = 1\) is called

**positive index**- 0, 2, 4, 6, 7 are positive indices of \(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}\)

- 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\)

**Minterm for index \(i\)**, denoted**\(m_i\)**: Variable occurs negated if its value in row \(i\) is 0; otherwise, variable without negationE.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

- 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\)

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…)

- Previous theorem implies that
**every**Boolean function can be expressed using only And, Or, Not- DNF is a
**canonical**representation

- DNF is a
- 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) = ...`

- Recall:

- 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

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)

- 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.

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

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.

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.

Except where otherwise noted, the work “Boolean Logic I”, © 2024 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.