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