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 earliest method of manipulating symbolic 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 applicability 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:Xn→X$f:X^n\to X$ of degree n, where X={0,1}$X=\{0,1\}$ 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′$F(A,B)=A^{\prime }{B}^{\prime }$. This is a function of degree 2 from the set of ordered pairs of Boolean variables to the set {0,1}$\{0,1\}$ where F(0,0)=1,F(0,1)=0,F(1,0)=0$F(0,0)=1,F(0,1)=0,F(1,0)=0$ and F(1,1)=0$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$A{B}^{\prime }C$ is a Boolean expression.

Boolean Identities

Double Complement Law

∼(∼A)=A$\sim (\sim A)=A$

Complement Law

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

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

Idempotent Law

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

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

Identity Law

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

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

Dominance Law

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

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

Commutative Law

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

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

Associative Law

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

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

Absorption Law

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

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

Simplification Law

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

A+(∼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)$

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

De-Morgan's Law

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

∼(A+B)=∼A.∼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 (list of variables) = ∑ (list of 1-minterm indices)

and

F' (list of variables) = ∑ (list of 0-minterm indices)

A	B	C	Term	Minterm
0	0	0	x’y’z’	m0
0	0	1	x’y’z	m1
0	1	0	x’yz’	m2
0	1	1	x’yz	m3
1	0	0	xy’z’	m4
1	0	1	xy’z	m5
1	1	0	xyz’	m6
1	1	1	xyz	m7

Example

Let, F(x,y,z)=x′y′z′+xy′z+xyz′+xyz$F(x,y,z)=x^{\prime }{y}^{\prime }{z}^{\prime }+x{y}^{\prime }z+xy{z}^{\prime }+xyz$

Or, F(x,y,z)=m0+m5+m6+m7$F(x,y,z)=m_0+m_5+m_6+m_7$

Hence,

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

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

F′(x,y,z)=x′yz+x′y′z+x′yz′+xy′z′$F^{\prime }(x,y,z)=x^{\prime }yz+x^{\prime }{y}^{\prime }z+x^{\prime }y{z}^{\prime }+x{y}^{\prime }{z}^{\prime }$

Or, F′(x,y,z)=m3+m1+m2+m4$F^{\prime }(x,y,z)=m_3+m_1+m_2+m_4$

Hence,

F′(x,y,z)=∑(3,1,2,4)=∑(1,2,3,4)$F^{\prime }(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(list of variables) = π$\pi$ (list of 0-maxterm indices).

and

F'(list of variables) = π$\pi$ (list of 1-maxterm indices).

A	B	C	Term	Maxterm
0	0	0	x + y + z	M0
0	0	1	x + y + z’	M1
0	1	0	x + y’ + z	M2
0	1	1	x + y’ + z’	M3
1	0	0	x’ + y + z	M4
1	0	1	x’ + y + z’	M5
1	1	0	x’ + y’ + z	M6
1	1	1	x’ + y’ + z’	M7

Example

Let F(x,y,z)=(x+y+z).(x+y+z′).(x+y′+z).(x′+y+z)$F(x,y,z)=(x+y+z).(x+y+z^{\prime }).(x+y^{\prime }+z).(x^{\prime }+y+z)$

Or, F(x,y,z)=M0.M1.M2.M4$F(x,y,z)=M_0.M_1.M_2.M_4$

Hence,

F(x,y,z)=π(0,1,2,4)$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′)$F^{″}(x,y,z)=(x+y^{\prime }+z^{\prime }).(x^{\prime }+y+z^{\prime }).(x^{\prime }+y^{\prime }+z).(x^{\prime }+y^{\prime }+z^{\prime })$

Or, F(x,y,z)=M3.M5.M6.M7$F(x,y,z)=M_3.M_5.M_6.M_7$

Hence,

F′(x,y,z)=π(3,5,6,7)$F^{\prime }(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.

A	~A
0	1
1	0

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.

A	B	A.B
0	0	0
0	1	0
1	0	0
1	1	1

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.

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1

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.

A	B	~(A.B)
0	0	1
0	1	1
1	0	1
1	1	0

NOR Gate

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

A	B	~(A+B)
0	0	1
0	1	0
1	0	0
1	1	0

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.

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

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.

A	B	A X-NOR B
0	0	1
0	1	0
1	0	0
1	1	1