Boolean functions

Table of contents

1. Introduction
2. Mathematical definition
3. Important concepts
4. Further reading
5. References

Introduction

A mathematical expression consisting of Boolean variables combined using the Boolean algebra operators: logical addition (OR), multiplication (AND) and negation (NOT) is a Boolean function.

Mathematical definition

If $k$ is the number of Boolean variables of the function, then the function $f(x_1,\ldots,x_k)$ and its domain and codomain are defined as $f:\{0,1\}^k\rightarrow\{0,1\}$

Important concepts

The following is a list of definitions for fundamental concepts used in Boolean functions:

• Literal: A logic variable or its complement $(x,\overline{x},y_0,\ldots)$.
• Product term: An expression where literals are combined by the logical AND operator $(x\overline{y}z,\ldots)$.
• Sum term: An expression where literals are combined by the logical OR operator $(y+\overline{z},\ldots)$.
• Normal term: A (product or sum) term without repeated variables.
• Sum of Products (SoP): A sum of product terms $(\overline{x}+xwz+x\overline{y})$.
• Product of Sums (PoS): A product of sum terms $((x+y+z)(z+\overline{w})(z+\overline{x}))$.

Further reading

• Section 3.2 “Switching functions” in [1].
• Section 1.3 “Boolean Functions” in [2].
• Chapter 3 “Boolean Algebra and Logic” in [3].

References

• [1]Z. Kohavi and N. K. Jha, Switching and Finite Automata Theory. Cambridge University Press, 2010 [Online]. Available at: https://books.google.cl/books?id=jZIxam8Rb9AC
• [2]G. Donzellini, L. Oneto, D. Ponta, and D. Anguita, Introduction to Digital Systems Design. Springer International Publishing, 2018 [Online]. Available at: https://books.google.cl/books?id=va1qDwAAQBAJ
• [3]M. Ferdjallah, Introduction to Digital Systems: Modeling, Synthesis, and Simulation Using VHDL. Wiley, 2011 [Online]. Available at: https://books.google.cl/books?id=kJRoR8AAu1AC

1. Every Boolean Function can be expressed as ________ ?
   1. Algebraic expression
      • Laplace expression
      • Binomial expression
2. SOP (Sum of Product) is referred as ________ ?
   1. (x+xwz+xy)
      • ((x+y+z)(z+w)(z+x))

---