Boolean Expressions and Functions - Discrete Mathematics

What is Boolean algebra?

Algebra of logic is known as Boolean algebra. The variables which can have two discrete values 0 (False) and 1 (True) and the operations of logical significance are dealt with Boolean algebra.

Boolean algebra is widely accepted in switching theory, building basic electronic circuits and designing of the digital computers.

What are Boolean Functions?

A special mathematical function with n degrees and where X={0,1} is the Boolean domain with a being a non-negative integer.

The Boolean function helps in describing the way in which the Boolean output is derived 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 {0,1} where F(0,0)=1,F(0,1)=0,F(1,0)=0 and F(1,1)=0

What are Boolean Expressions?

A Boolean value is produced by an Boolean expression. Boolean constants (True or False), Boolean variables and logical connectives combine together to form a Boolean expression. A Boolean function is represented by a Boolean expression.

Example − AB′C is a Boolean expression.

What are the different Boolean Identities?

The following are some of the different Boolean Identitied:

Double Complement Law

∼(∼A)=A

Complement Law

A+∼A=1 (OR Form)

A.∼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

Simplification Law

A.(∼A+B)=A.B

A+(∼A.B)=A+B

Distributive Law

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

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

De-Morgan's Law

∼(A.B)=∼A+∼B

∼(A+B)=∼A.∼B

What are the canonical Forms of Boolean Expressions?

There are two kinds of canonical forms for Boolean expression:

  • The sum of minterms (SOM) form
  • The product of maxterms (POM) form

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

The product of all the variables either in direct or complemented form is known as minterm. The Boolean function is expressed as a sum of the 1-minterms and the inverse of function is represented as 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

Or, F(x,y,z)=m0+m5+m6+m7

Hence,

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

The complement form of F(x,y,z)

F′(x,y,z)=x′yz+x′y′z+x′yz′+xy′z′

Or, F′(x,y,z)=m3+m1+m2+m4

Hence,

F′(x,y,z)=∑(3,1,2,4)=∑(1,2,3,4)

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

All the variables in direct or complemented form when added is a maxterm. The Boolean function is expressed as the product of the 0-maxterms and the inverse of the function can be expressed as a product of its 1-maxterms.

Hence,

F(list of variables) = ππ (list of 0-maxterm indices).

and

F'(list of variables) = ππ (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)

Or, F(x,y,z)=M0.M1.M2.M4

Hence,

F(x,y,z)=π(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)=M3.M5.M6.M7

Hence,

F′(x,y,z)=π(3,5,6,7)

What are Logic Gates?

Logic gates are used for implementing the Boolean functions. Some of the logic gates are:

NOT Gate

A single bit input is inverted to a single bit of output by NOT gate.

A
~A
0
1
1
0

AND Gate

When the inputs are high, the logic gate that gives a high output, by the AND logic gate. The AND operation is showed by using a (.)

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

The logic gate that provides a low output if all the inputs are high, otherwise high output is NAND Gate.

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

NOR Gate

The Logic gate which gives high output when both the inputs are low, or vice versa is NOR logic gate.

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

XOR (Exclusive OR) Gate

The Logic gate that gives high output for different inputs and otherwise low is XOR gate.

A
B
AB
0
0
0
0
1
1
1
0
1
1
1
0

X-NOR (Exclusive NOR) Gate

The logic gate that gives high output for the same inputs, otherwise low output is EX-NOR gate.

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

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics