INF107

Boolean logic

Introduction

Let $\mathbb{B}$ be the two-element set $\{0,1\}$.

A logical variable is an element of $\mathbb{B}$. It has only two possible values: $0$ or $1$ (which can also be interpreted as false or true, respectively).

A logical function $F$ is a mapping from $\mathbb{B}\times \mathbb{B}\dots \times \mathbb{B}$ to $\mathbb{B}$ which maps an $n$-tuple of logical variables $(x_0,x_1,\dots ,x_{n-1})$, often called inputs, to a logical variable $y=F(x_0,x_1,\dots ,x_{n-1})$, often called output.

There are two categories of logic functions, depending on their temporal behavior.

A combinatorial function is a logical function for which the output depends only on the current state of the inputs:

$$\forall t,y(t)=F(x_0(t),x_1(t),\dots ,x_{n-1}(t))$$

A sequential function is a logical function for which the output depends on the current state of its inputs but also on their past states:

$$y(t)=F(x_0(t),x_1(t),\dots ,x_{n-1}(t),x_0(t-1),x_1(t-1)\dots )$$

In this chapter, we will deal only with combinatorial functions. Sequential functions will be introduced in the chapter Sequential logic.

Representations of logical functions

There are several methods to describe a combinatorial logical function. These methods are all equivalent and the choice of one or the other will only depend on the context of use.

Truth table

The first method consists in listing, for each of the possible values of its inputs, the value of the function’s output. This list, very often presented in the form of a table, is called truth table.

The major drawback of this method is that this table can be very large. Indeed, if the function takes as input $n$ logical variables, it takes $2^n$ rows in this table to list all the possible values of the inputs.

Example of a truth table of a function taking as input two logical variables $a$ and $b$:

Example of a function taking two logical variables as input

$a$ and $b$

Analytical equation

This method consists in giving the equation of the output of the function based on its inputs. The list and meaning of operators will be given in the section on basic logic functions. You will learn more about the way we can manipulate and simplify Boolean equations in the section on Boolean Algebra.

Example of a function taking three logical variables as input $a,b$ and $c$: $z=a\cdot b+\overline{c}$.

Schematic representation

This method consists of graphically representing a Boolean function using nodes with standardised symbols ¹ for basic functions and edges to indicate the connection of an output to an input.

Functional description

This method consists in describing, in natural language, the behavior of the output according to the inputs of the function.

Example: the output $z$ is 1 if, and only if, at least one of $a$ or $b$ is 1.

Hardware description language

This method consists in describing the function in a particular language, called Hardware Description Language — HDL, easily understood by a computer. There are several HDLs auch as SystemVerilog or VHDL. In this course, we are not going to consider HDLs, you will encounter them in the second semester.