Boolean algebra basics

Table of Contents

Boolean algebra basics contains a set of axioms, postulates, and theorems. It also contains a set of elements and operators. The operators are called the binary operators.

A set of elements is a collection of objects that have similar properties. This definition of a set is debatable, but that is not the scope of this article. The general notion of set is that it contains elements of similar nature.

Fundamental Postulates of Boolean Algebra

The fundamental postulates for Boolean Algebra are given below. Thought Boolean algebra was introduced by George Boole in 1845, the postulates were formulated by E.V.Huntington in 1904, that every Boolean algebra must satisfy.

We only use two variable Boolean algebra as far as digital design is concerned. The 6 postulates in Boolean algebra basics are listed below.

Closure
Associative law
Commutative law
Identity element
Inverse
Distributive law

Let us discuss each of them, one at a time.

Closure

A set S is closed with respect to binary operator * if for every pair of an element in set S, the binary operator specifies a rule to find an element in S.

Example,

N is set of natural numbers,

\begin{aligned} &N = \{1, 2, 3, 4, ...\} \end{aligned}

Suppose + is the binary operator, then you take any number a and b in N,

\begin{aligned} &a + b \in N\\ &3 + 2 = 5\\ &2, 3 \in N \\ &5 \in N.\\ \end{aligned}

but when we do subtraction.

\begin{aligned} &a - b \notin N\\ &2 - 4 = -2\\ &2, 4 \in N \hspace{3px} and \hspace{3px} -2 \notin N\\ \end{aligned}

The subtraction (-) is not a binary operator because it does not satisfy closure property.

Associativity Law

A binary operator (*) is associative on a set S whenever following is true.

\begin{aligned}&x*(y*z) = (x * y) * z , \\\\ &\forall x, y, z \in S \end{aligned}

For example, the multiplication is an associative binary operator on a set of natural numbers N.

\begin{aligned} &= 2 \times ( 4 \times 1)\\ &= 2 \times 4 = 8\\ \end{aligned}

It is equal to the following.

Communicative Law

A binary operator * is communicative on a set S, whenever

\begin{aligned} &x * y = y * x, \\\\ &\forall x, y \in S \end{aligned}

The addition operator (+) and multiplication (x) are communicative on a set of natural numbers (N).

For example,

\begin{aligned} &5 + 4 = 4 + 5 = 9\\\\ &and\\\\ &4 \times 2 = 2 \times 4 = 8 \end{aligned}

Identity Element

A set S has an identity element with respect to a binary operation * on S, if there exists an element such that

\begin{aligned} &x * e = e * x = x,\\\\ &for \hspace{3px} any \hspace{3px} x \in S \end{aligned}

The identity element for a set S is always unique to the set. Consider the following example, where + is the binary operation on a set of integers, Z and 0 is the identity element.

\begin{aligned} Z = 4 + 0 = 0 + 4 = 4\\ Z = 8 + 0 = 0 + 8 = 8 \end{aligned}

Inverse

A set S with identity element is said to have an inverse with respect to binary operation *, whenever, for all

\begin{aligned} &x \in S,\\ &\exists y \in S \mid x * y = e\end{aligned}

Let us take the previous example of addition + on a set of integers Z, with identity element 0.

Let x be an element in Z,

\begin{aligned} &x \in Z\\ &x = 5\\ \end{aligned}

Then, -x also belong to Z, let us call it y.

\begin{aligned} &y \in Z\\ &y = -5\\ &x + y = 0 \end{aligned}

Therefore, a set of integers have inverse with respect to binary operation – addition.

Distributive Law

The distributive law is a very important property of algebraic structures. If * and. are two binary operations on set S, then * is said to distributive over. whenever

\begin{aligned} &x * ( y . z) = (x * y) . (x * z)\\\\ &\forall x,y,z \in S \end{aligned}

Also, . is distributive over * whenever

\begin{aligned} &x \cdot (y \cdot z) = (x \cdot y) \cdot (x \cdot z)\\\\ &\forall x, y, z \in S \end{aligned}

From the above postulate in Boolean algebra basics, it clear that all binary operators cannot hold all six properties. In fact, the modern algebra studies these algebraic structures formally and trying to find interesting properties. The topics of study are groups, sub-groups, monoid, rings, and fields.