Boolean Expressions & Functions

Boolean algebra is algebra of logic. It deals with variables that can have two discrete values, 0 (False) and 1 (True); and operations that have logical significance. The earpest method of manipulating symbopc logic was invented by George Boole and subsequently came to be known as Boolean Algebra.

Boolean algebra has now become an indispensable tool in computer science for its wide apppcabipty in switching theory, building basic electronic circuits and design of digital computers.

Boolean Functions

A Boolean function is a special kind of mathematical function $f: X^n ightarrow X$ of degree n, where $X = lbrace {0, 1} brace$ is a Boolean domain and n is a non-negative integer. It describes the way how to derive Boolean output from Boolean inputs.

Example − Let, $F(A, B) = A’B’$. This is a function of degree 2 from the set of ordered pairs of Boolean variables to the set $lbrace {0, 1} brace$ where $F(0, 0) = 1, F(0, 1) = 0, F(1, 0) = 0$ and $F(1, 1) = 0$

Boolean Expressions

A Boolean expression always produces a Boolean value. A Boolean expression is composed of a combination of the Boolean constants (True or False), Boolean variables and logical connectives. Each Boolean expression represents a Boolean function.

Example − $AB’C$ is a Boolean expression.

Boolean Identities

Double Complement Law

$sim(sim A) = A$

Complement Law

$A + sim A = 1$ (OR Form)

$A . sim A = 0$ (AND Form)

Idempotent Law

$A + A = A$ (OR Form)

$A . A = A$ (AND Form)

Identity Law

$A + 0 = A$ (OR Form)

$A . 1 = A$ (AND Form)

Dominance Law

$A + 1 = 1$ (OR Form)

$A . 0 = 0$ (AND Form)

Commutative Law

$A + B = B + A$ (OR Form)

$A. B = B . A$ (AND Form)

Associative Law

$A + (B + C) = (A + B) + C$ (OR Form)

$A. (B . C) = (A . B) . C$ (AND Form)

Absorption Law

$A. (A + B) = A$

$A + (A . B) = A$

Simppfication Law

$A . (sim A + B) = A . B$

$A + (sim A . B) = A + B$

Distributive Law

$A + (B . C) = (A + B) . (A + C)$

$A . (B + C) = (A . B) + (A . C)$

De-Morgan s Law

$sim (A . B) = sim A + sim B$

$sim (A+ B) = sim A . sim B$

Canonical Forms

For a Boolean expression there are two kinds of canonical forms −

The sum of minterms (SOM) form

The product of maxterms (POM) form

The Sum of Minterms (SOM) or Sum of Products (SOP) form

A minterm is a product of all variables taken either in their direct or complemented form. Any Boolean function can be expressed as a sum of its 1-minterms and the inverse of the function can be expressed as a sum of its 0-minterms. Hence,

F (pst of variables) = ∑ (pst of 1-minterm indices)

and

F (pst of variables) = ∑ (pst of 0-minterm indices)

Example

Let, $F(x, y, z) = x y z + x y z + x y z + x y z $

Or, $F(x, y, z) = m_0 + m_5 + m_6 + m_7$

Hence,

$F(x, y, z) = sum (0, 5, 6, 7)$

Now we will find the complement of $F(x, y, z)$

$F (x, y, z) = x y z + x y z + x y z + x y z $

Or, $F (x, y, z) = m_3 + m_1 + m_2 + m_4$

Hence,

$F (x, y, z) = sum (3, 1, 2, 4) = sum (1, 2, 3, 4)$

The Product of Maxterms (POM) or Product of Sums (POS) form

A maxterm is addition of all variables taken either in their direct or complemented form. Any Boolean function can be expressed as a product of its 0-maxterms and the inverse of the function can be expressed as a product of its 1-maxterms. Hence,

F(pst of variables) = $pi$ (pst of 0-maxterm indices).

and

F (pst of variables) = $pi$ (pst of 1-maxterm indices).

Example

Let $F(x, y, z) = (x + y + z) . (x+y+z ) . (x+y +z) . (x +y+z)$

Or, $F(x, y, z) = M_0 . M_1 . M_2 . M_4$

Hence,

$F (x, y, z) = pi (0, 1, 2, 4)$

$F (x, y, z) = (x+y +z ) . (x +y+z ) . (x +y +z) . (x +y +z )$

Or, $F(x, y, z) = M_3 . M_5 . M_6 . M_7$

Hence,

$F (x, y, z) = pi (3, 5, 6, 7)$

Logic Gates

Boolean functions are implemented by using logic gates. The following are the logic gates −

NOT Gate

A NOT gate inverts a single bit input to a single bit of output.

AND Gate

An AND gate is a logic gate that gives a high output only if all its inputs are high, otherwise it gives low output. A dot (.) is used to show the AND operation.

OR Gate

An OR gate is a logic gate that gives high output if at least one of the inputs is high. A plus (+) is used to show the OR operation.

NAND Gate

A NAND gate is a logic gate that gives a low output only if all its inputs are high, otherwise it gives high output.

NOR Gate

An NOR gate is a logic gate that gives high output if both the inputs are low, otherwise it gives low output.

XOR (Exclusive OR) Gate

An XOR gate is a logic gate that gives high output if the inputs are different, otherwise it gives low output.

X-NOR (Exclusive NOR) Gate

An EX-NOR gate is a logic gate that gives high output if the inputs are same, otherwise it gives low output.