2. What is base or radix of number system? Answer: The total number of digits used by the particular number system is called base or radix of that number system. For example, Base of Binary number system is 2 because it uses two digits 0 and 1 only.
3. List the types of number system with their bases. Answer: There are four types of number system and their bases are given below:
|
Number System |
Base |
|
(i) Binary Number System |
2 |
|
(ii) Octal Number System |
8 |
|
(iii) Decimal Number System |
10 |
|
(iv) Hexadecimal Number System |
16 |
· Define Binary number system.
Answer: The number system having
base two(2) and consists of digits: 0 and 1 is called Binary number system.
· Define Octal number system.
Answer: The number system having
base eight(8) and consists of digits: 0,1,2,3,4,5,6, and 7 is called Octal
number system.
· Define Decimal (Denary) number system.
Answer: The number system having
base ten(10) and consists of digits: 0,1,2,3,4,5,6,7,8 and 9 is called
Decimal(Denary) number system.
· Define Hexadecimal number system.
Answer: The number system having
base sixteen(16) and consists of digits: 0,1,2,3,4,5,6,7,8, 9 and alphabets
A,B,C,D,E and F is called Hexadecimal number system.
Where,
|
A |
B |
C |
D |
E |
F |
|
10 |
11 |
12 |
13 |
14 |
15 |
· Why do digital computers use binary number system for its
operations?
Answer: The number system having
base two and consists of digits: 0 and 1 is called Binary number system. It has
two bits 0 and 1. An electronic circuit has two states either ON & OFF state.
The bit 1 represents high voltage (ON state) and the bit 0 represents the low
voltage (OFF state) of an electronic circuit. That's why a digital computer
uses binary number for its operations.
· Fundamentals Rule for Number
Conversion:
· Decimal
to Binary, Octal, and Hexadecimal Conversion
Conversion 1: (42)10=(?)2
|
2 |
42 |
Remainder |
 |
|
2 |
21 |
0 |
|
|
2 |
10 |
1 |
|
|
2 |
5 |
0 |
|
|
2 |
2 |
1 |
|
|
2 |
1 |
0 |
|
|
0 |
1 |
∴(42)10=(101010)2
Conversion 2: (42.54)10=(?)2
|
2 |
42 |
Remainder |
|
|
2 |
21 |
0 |
|
|
2 |
10 |
1 |
|
|
2 |
5 |
0 |
|
|
2 |
2 |
1 |
|
|
2 |
1 |
0 |
|
|
0 |
1 |
∴(42)10=(101010)2
Also,
|
Fraction x 2 = Product |
Integer Part |
 |
|
0.54x2=1.08 |
1 |
|
|
0.08x2=0.16 |
0 |
|
|
0.16x2=0.32 |
0 |
|
|
0.32x2=0.64 |
0 |
|
|
0.64x2=1.28 |
1 |
∴(42.54)10=(101010.10001)2
Conversion 3: (123)10=(?)8
|
8 |
123 |
Remainder |
|
|
8 |
15 |
3 |
|
|
8 |
1 |
7 |
|
|
0 |
1 |
∴(123)10=(173)8
Conversion 4: (123.54)10=(?)8
|
8 |
123 |
Remainder |
|
|
8 |
15 |
3 |
|
|
8 |
1 |
7 |
|
|
0 |
1 |
∴(123)10=(173)8
Also,
|
Fraction x 8 = Product |
Integer Part |
|
|
0.54x8=4.32 |
4 |
|
|
0.32x8=2.56 |
2 |
|
|
0.56x8=4.48 |
4 |
|
|
0.48x8=3.84 |
3 |
|
|
0.84x8=6.72 |
6 |
∴(123.54)10=(173.42436)8
Conversion 5: (123)10=(?)16
|
16 |
123 |
Remainder |
|
|
16 |
7 |
11 (B) |
|
|
0 |
7 |
∴(123)10=(7B)16
Conversion 6: (123.54)10=(?)16
|
16 |
123 |
Remainder |
|
|
16 |
7 |
11 (B) |
|
|
0 |
7 |
∴(123)10=(7B)16
Also,
|
Fraction x 16 = Product |
Integer Part |
|
|
0.54x16=8.64 |
8 |
|
|
0.64x16=10.24 |
10(A) |
|
|
0.24x16=3.84 |
3 |
|
|
0.84x16=13.44 |
13(D) |
|
|
0.44x16=7.04 |
7 |
∴(123.54)10=(7B.8A3D7)16
· Binary,
Octal, and Hexadecimal to Decimal Conversion
Other systems(Binary, Octal &
Hexadecimal) are converted into decimal number by calculating sum of product of
each given digit and its corresponding place value ( in terms of power of its
base which begins from 0 and increases for integer part and from -1 and
decreases for a fractional part)
Conversion 7 : (101010)2=(?)10
Answer:
|
Face Value |
1 |
0 |
1 |
0 |
1 |
0 |
|
Place Value |
25 |
24 |
23 |
22 |
21 |
20 |
=1x25+0x24+1x23+0x22+1x21+0x20
=1×32+0×16+1×8+0×4+1×2+0×1
=32+0+8+0+2+0
=(42)10
∴(101010)2=(42)10
Conversion 8: (101.101)2=(?)10
Answer:
|
Face Value |
1 |
0 |
1 |
.1 |
0 |
1 |
|
Place Value |
22 |
21 |
20 |
2-1 |
2-2 |
2-3 |
=1x22+0x21+1x20+1x2-1+0x2-2+1x2-3
=1×4+0×2+1×1+1×0.5+1×0.25+0×0.125
=4+0+1+0.5+0+0.125
=(5.625)10
∴(101.101)2=(5.625)10
Conversion 9: (345)8=(?)10
Answer:
|
Face Value |
3 |
4 |
5 |
|
Place Value |
82 |
81 |
80 |
=3x82+4x81+5x80
=3×64+4×8+5×1
=192+32+5
=(229)10
∴(345)8=(229)10
Conversion 10: (31.76)8=(?)10
Answer:
|
Face Value |
3 |
1 |
.7 |
6 |
|
Place Value |
81 |
80 |
8-1 |
8-2 |
=3x81+1x80+7x8-1+6x8-2
=3x8+1x1+7x0.125+6x0.015625
=24+1+0.875+0.09375
=(25.96875)10
∴(31.76)8=(25.96875)10
Conversion 11: (ABC)16=(?)10
Answer:
We Know ,
|
A |
B |
C |
D |
E |
F |
|
10 |
11 |
12 |
13 |
14 |
15 |
Now,
|
Face Value |
A |
B |
C |
|
Place Value |
162 |
161 |
160 |
=Ax162+Bx161+Cx160
=10×256+11×176+12×1
=2560+176+12
=(2748)10
∴(ABC)16=(2748)10
Conversion 12: (3F.7A)16=(?)10
Answer:
|
Face Value |
3 |
F |
.7 |
A |
|
Place Value |
161 |
160 |
16-1 |
16-2 |
=3x161+Fx160+7x16-1+Ax16-2
=3x16+15x1+7x0.0625+10x0.00390625
=48+15+0.4375+0.0390625
=(63.4765625)10
∴(3F.7A)16=(63.4765625)10
· Binary
to Octal Conversion
A binary number is converted into an
octal number by making a group of 3 BITS and grouping should be done from right
to left for integer part and left to right for fraction part. So, this method
is called Grouping Method. If there are less than 3 BITS in the last
group then required number of zeroes can be added in the left-hand side for
integer part and in the right-hand side for the fraction part to make the group
of 3 BITS. Then equivalent octal value of each group is written using Binary -
Octal conversion table.
|
Table I: Binary-Octal Conversion
Table |
|
|
Binary (2) |
Octal (23=8) |
|
000 |
0 |
|
001 |
1 |
|
010 |
2 |
|
011 |
3 |
|
100 |
4 |
|
101 |
5 |
|
110 |
6 |
|
111 |
7 |
Conversion 13: (1011101)2=(?)8
Answer:
|
3 BITS Group |
001 |
011 |
101 |
|
Octal Value |
1 |
3 |
5 |
∴(1011101)2=(135)8
Conversion 14: (1011101.1011001)2=(?)8
Answer:
|
3 BITS Group |
001 |
011 |
101 |
.101 |
100 |
100 |
|
Octal Value |
1 |
3 |
5 |
.5 |
4 |
4 |
∴(1011101.1011001)2=(135.544)8
· Binary
to Hexadecimal Conversion
A binary number is converted into
hexadecimal number by making a group of 4 BITS and grouping should be done from
right to left for integer part and left to right for fraction part. So, this
method is called Grouping Method. If there are less than 4 BITS in the
last group then required number of zeroes can be added in the left-hand side
for integer part and in the right-hand side for the fraction part to make the
group of 4 BITS. Then equivalent octal value of each group is written using
Binary - Hexadecimal conversion table.
|
Table II: Binary-Hexadecimal
Conversion Table |
|
|
Binary (2) |
Hexadecimal (24=16) |
|
0000 |
0 |
|
0001 |
1 |
|
0010 |
2 |
|
0011 |
3 |
|
0100 |
4 |
|
0101 |
5 |
|
0110 |
6 |
|
0111 |
7 |
|
1000 |
8 |
|
1001 |
9 |
|
1010 |
A |
|
1011 |
B |
|
1100 |
C |
|
1101 |
D |
|
1110 |
E |
|
1111 |
F |
Conversion 15: (1011101)2=(?)16
Answer:
|
4 BITS Group |
0101 |
1101 |
|
Hexadecimal |
5 |
13(D) |
∴(1011101)2=(5D)16
Conversion 16: (1011101.101111)2=(?)16
Answer:
|
4 BITS Group |
0101 |
1101 |
.1011 |
1100 |
|
Hexadecimal |
5 |
13(D) |
.11(B) |
12(C) |
∴(1011101.101111)2=(5D.BC)16
· Octal
to Binary Conversion
Octal number is converted into
binary number by breaking each digits of the given octal number into a group of
3 BITS using Table I: Binary-Octal Conversion Table. So, this
method is called Breaking Method.
Conversion 17: (567)8=(?)2
Answer:
|
Octal Digits |
5 |
6 |
7 |
|
Equivalent BITS |
101 |
110 |
111 |
∴(567)8=(101110111) 2
Conversion 18: (567.123)8=(?)2
Answer:
|
Octal Digits |
5 |
6 |
7 |
.1 |
2 |
3 |
|
Equivalent BITS |
101 |
110 |
111 |
.001 |
010 |
011 |
∴(567.123)8=(101110111.001010011)2
· Hexadecimal
to Binary Conversion
Hexadecimal number is converted into
binary number by breaking each digits of the given hexadecimal number into a
group of 4 BITS using Table II: Binary-Hexadecimal Conversion Table. So, this
method is called Breaking Method.
Conversion 19: (A43)16=(?)2
Answer:
|
Hexadecimal Digits |
A |
4 |
3 |
|
Equivalent BITS |
1010 |
0100 |
0011 |
∴(A43)16=(101001000011) 2
Conversion 20: (4A3.EF)16=(?)2
Answer:
|
Hexadecimal Digits |
4 |
A |
3 |
.E |
F |
|
Equivalent BITS |
0100 |
1010 |
0011 |
.1110 |
1111 |
∴(4A3.EF)16=(010010100011.11101111)2
· Octal
to Hexadecimal Conversion
Octal number is converted into hexadecimal number by using any one of the
following two double conversion methods.
Method I:
Octal → Binary
Binary → Hexadecimal
Method II:
Octal → Decimal
Decimal → Hexadecimal
Conversion 21: (567)8=(?)16
Answer:
Method - I
Here, given octal number is first converted into equivalent
binary number as:
|
Octal Digits |
5 |
6 |
7 |
|
Equivalent BITS |
101 |
110 |
111 |
∴(567)8=(101110111)2
Now, obtained binary number is converted into hexadecimal number as:
|
4 BITS Group |
0001 |
0111 |
0111 |
|
Hexadecimal Digits |
1 |
7 |
7 |
So, (101110111)2=(177)16
∴(567)8=(177)16
Method - II
Here, given octal number is first converted into equivalent
decimal number.
|
Face Value |
5 |
6 |
7 |
|
Place Value |
82 |
81 |
80 |
=5x82+6x81+7x80
=5×64+6×8+7×1
=320+48+7
=(375)10
Now, the obtained decimal number is converted into hexadecimal number as:
|
16 |
375 |
Remainder |
|
|
16 |
23 |
7 |
|
|
16 |
1 |
7 |
|
|
0 |
1 |
So, (375)10=(177)16
∴(567)8=(177)16
Conversion 22: (123.456)8=(?)16
Answer: Here, given octal number is
first converted into equivalent binary number as:
|
Octal Digits |
1 |
2 |
3 |
.4 |
5 |
6 |
|
Equivalent BITS |
001 |
010 |
011 |
.100 |
101 |
110 |
∴(123.456)8=(1010011.100101110)2
Now, obtained binary number is converted into hexadecimal number as:
|
4 BITS Group |
0101 |
0011 |
.1001 |
0111 |
0000 |
|
Hexadecimal Digits |
5 |
3 |
.9 |
7 |
0 |
So, (1010011.100101110)2=(53.970)16
∴(123.456)8=(53.97)16
· Hexadecimal
to Octal Conversion
Hexadecimal number is converted into octal number by using any one of the
following two double conversion methods.
Method I:
Hexadecimal → Binary
Binary → Octal
Method II:
Hexadecimal → Decimal
Decimal → Octal
Conversion 23: (5E7)16=(?)8
Answer:
Method - I
Here, given octal number is first converted into equivalent
binary number as:
|
Hexadecimal Digits |
5 |
E |
7 |
|
Equivalent BITS |
0101 |
1110 |
0111 |
∴(5E7)16=(10111100111)2
Now, obtained binary number is converted into octal number as:
|
3 BITS Group |
010 |
111 |
100 |
111 |
|
Octal Digits |
2 |
7 |
4 |
7 |
So, (10111100111)2=(2747)8
∴(5E7)16=(2747)8
Method - II
Here, given hexadecimal number is first converted into
equivalent decimal number.
|
Face Value |
5 |
E |
7 |
|
Place Value |
162 |
161 |
160 |
=5x162+Ex161+7x160
=5×256+14×16+7×1
=1280+224+7
=(1511)10
Now, the obtained decimal number is converted into hexadecimal number as:
|
8 |
1511 |
Remainder |
|
|
8 |
188 |
7 |
|
|
8 |
23 |
4 |
|
|
8 |
2 |
7 |
|
|
0 |
2 |
So, (1511)10=(2747)8
∴(5E7)16=(2747)8
Conversion 24: (5E7.3D)16=(?)8
Answer: Here, given hexadecimal
number is first converted into equivalent binary number as:
|
Hexadecimal Digits |
5 |
E |
7 |
.3 |
D |
|
Equivalent BITS |
0101 |
1110 |
0111 |
.0011 |
1101 |
∴(5E7.3D)16=(10111100111.00111101)2
Now, obtained binary number is converted into octal number as:
|
3 BITS Group |
010 |
111 |
100 |
111 |
.001 |
111 |
101 |
|
Octal Digits |
2 |
7 |
4 |
7 |
.1 |
7 |
5 |
So, (10111100111.00111101)2=(2747.175)16
∴(5E7.3D)16=(2747.175)16
Boolean Algebra:
In 1938 Claude Shannon showed how
the basic rules of logic, first given by George Boole in 1854 in his book
entitled “The Laws of Thought” , could be used to design circuits.
- Boolean algebra is used to design and simplify circuits
of electronic devices.
- Each input and output can be thought as a member of the
set {0,1}.
- The basic elements of circuits are called gates. Each
type of gate implements a Boolean operation.
Definition of Boolean Algebra:
- The branch of mathematics that includes methods for
manipulating logical variables and logical expressions is called Boolean
algebra.
- It is used to analyze and simplify the digital (logic)
circuits.
- It uses only the binary numbers i.e. 0 and 1.
- It is also called Binary Algebra or Logical Algebra.
# Difference between Boolean Algebra and Ordinary Algebra
|
Boolean
Algebra |
Ordinary
Algebra |
|
1. It is an algebra of logic based
on a binary number system. |
1. It is general purpose algebra
based on the decimal number system. |
|
2. It is used in the field of
digital electronics. |
2. It is used in the field of
mathematics. |
|
3. Basic operations used in Boolean algebra are: AND, OR
and NOT operations. |
3. Basic operations used in Ordinary algebra are:
addition, subtraction, multiplication and division. |
|
4. No coefficient and power are used in Boolean algebra as
A+A=A and A.A=A. |
4. Coefficient and power are used in Ordinary algebra as
A+A=2A and A.A=A2. |
|
5. It holds both distributed laws: A+(B.C)=(A+B).(A+C) and A.(B+C)=(A.B)+(A.C) |
5. It holds only one distributive law: A.(B+C)=(A.B)+(A.C) |
# Define Boolean variable /Logical
variable.
Ans: A variable with its value
either true or false is called Boolean variable. It is also known as a logical
variable. True and false are only two possible vBoolean values for Boolean
variables.
# Define Boolean expression with
example.
Ans: A Boolean expression is a
string of symbols representing logical variables and logical operations which
is evaluated to give a logical value. Example:
a.
A+A’B
b.
AB+A’BC+BC’
# Define the truth table.
Ans: The tabular representation of
Boolean function used in logic to compute the functional values of logical
expressions on each of their functional arguments is called truth table.
OR
A table which represents the
input-output relationship of the binary variable is called a truth table.
For example: truth table of AND gate
|
Inputs |
Output |
|
|
A |
B |
C=A.B |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
# Define logic function.
Ans: A logic function is an
expression expressed algebraically with binary variables, logical operation
symbols, parenthesis and equal sign, is called logic function. It is also known
as Boolean function. For a given value of the binary variables, the logic
function can be either 1 or 0. For example, in the logic function F= A+B, the
value of F is 0 if A=0 and B=0 otherwise the value of F is 1.
# Basic Logical / Boolean Operation
An operator is a special symbol that
indicates the operation to be carried out between two operands. An operation is
the action to be carried out upon operands. There are three basic Boolean
operations: AND, OR, NOT operations.
AND Operation
|
Inputs |
Output |
|
|
A |
B |
C=A.B |
|
False |
False |
False |
|
False |
True |
False |
|
True |
False |
False |
|
True |
True |
True |
OR Operation
It is also known as logical
addition. It is carried out by plus(+) operator or simply by OR. It
generates true output if at least one input is true; otherwise it generates
false output. The logical equation of OR operation is written as C=A.B or C= A OR
B. The truth table of OR operation is given below:
|
Inputs |
Output |
|
|
A |
B |
C=A+B |
|
False |
False |
False |
|
False |
True |
True |
|
True |
False |
True |
|
True |
True |
True |
NOT Operation
It is also called a logical
complement. It is carried out by the prime ( ‘ ) operator or bar ( __ ). It
generates true output if the input is false; otherwise it generates false
output. The logical equation of NOT operation is written as C=A’. The truth
table of NOT operation is given below:
|
Input |
Output |
|
A |
C=A’ |
|
True |
False |
|
False |
True |
# Define logic gate.
Ans:
An electronic circuit which
generates only one output signal from one or more input signals is called a
logic gate. The manipulation of binary information is done by using a logic
gate. It is the basic building block of computers and other digital devices.
There are three basic logic gates.
1.
AND gate
2.
OR gate
3.
NOT gate
Derived gates
4.
NAND gate
5.
NOR gate
6.
XOR(Exclusive OR) gate
7.
XNOR(Exclusive NOR) gate
1.
AND gate:
It
is an electronic circuit used to perform logical multiplication (or AND
operation). It is denoted by dot operator (.) . It accepts two or more inputs
and generates only one output. It generates one or true or ON output if all the
inputs are 1 or true or ON otherwise, it generates 0 or False or OFF output.
a.
Graphical
Symbol of AND gate
b.
Boolean
Expression of AND gate:
Z=X.Y
c.
Truth table
of AND gate
|
Inputs |
Output |
|
|
X |
Y |
Z=X.Y |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
d.
Venn Diagram
of AND gate:
2.
OR gate:
It is an electronic circuit used to
perform logical addition (or OR operation), and for that, it uses plus
operator(+). It also accepts two or more inputs and generates only one output.
It generates 1 or true or ON output if at least any one of input is true
otherwise; it generates 0 or false or OFF output.
a.
Graphical
Symbol of OR gate:
b.
Boolean
Expression of OR gate:
Z=X+Y
c.
Truth Table
of OR gate:
|
Inputs |
Output |
|
|
X |
Y |
Z=X+Y |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
d.
Venn Diagram
of OR gate:
3.
NOT gate:
It is an electronic circuit used to perform logical complement (or NOT
operation), and for that, it uses a prime or bar operator (’ or __). It
accepts only one input and generates only one output. It generates 1 or true or
ON output if the input is false otherwise; it generates 0 or false or OFF
output. So, it is also known as Inverter.
a.
Graphical
Symbol of NOT gate:
b.
Boolean
Expression of NOT gate:
Z=X’
c.
Truth Table
of NOT gate:
|
Input |
Output |
|
X |
Z=X’ |
|
0 |
1 |
|
1 |
0 |
d.
Venn Diagram
of NOT gate:
4.
NAND gate:
It is an electronic circuit used to perform complement of logical
multiplication (or complement of AND operation). It uses dot operator (.) and
prime operator(’). It is the integration of NOT gate and AND gate that means NOT+AND=NAND.
It also accepts two or more inputs and generates only one output. It generates
1 or true or ON output if at least any one of the input is false otherwise; it generates
0 or false or OFF output.
a.
Graphical
Symbol of NAND gate
b.
Boolean
Expression of NAND gate
Z=(X.Y)’
c.
Truth Table
of NAND gate
|
Inputs |
Output |
|
|
X |
Y |
Z=(X.Y)’ |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
d.
Venn Diagram
of NAND gate
5.
NOR gate:
It is an electronic circuit used to perform complement of logical addition(or
complement of OR operation). It uses plus operator(+) and prime (’). It is the
integration of NOT gate and OR gate that means NOT+OR=NOR. It also
accepts two or more inputs and generates only one output. It generates 1 or
true or ON output if all the inputs are false otherwise; it generates 0 or
false or OFF output.
a.
Graphical
Symbol of NOR gate
b.
Boolean
Expression of NOR gate
Z=(X+Y)’
c.
Truth Table
of NOR gate
|
Inputs |
Output |
|
|
X |
Y |
Z=(X+Y)’ |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
0 |
d.
Venn Diagram
of NOR gate
6.
XOR
(Exclusive OR) gate:
It is an electronic circuit used to perform logical “either / or” operation. It
also accepts two or more inputs and generates only one output. It generates 1
or true or ON output if the number of 1 or true or ON input is odd otherwise,
it generates 0 or false or OFF output. So, it is also known as an even parity
generator.
a.
Graphical
Symbol of XOR gate
b.
Boolean
Expression of XOR gate
Z=X’.Y+X.Y’ OR Z=XêššY
c.
Truth Table
of XOR gate
|
Inputs |
Output |
|
|
X |
Y |
Z=XêššY |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
d.
Venn Diagram
of XOR gate
7.
XNOR(Exclusive
NOR) gate:
It is an electronic circuit used to perform logical complement of Exclusive-OR
operation. It also accepts two or more inputs and generates only one output. It
generates 1 or true or ON output if the number of 1 or true or ON input is even
otherwise; it generates 0 or false or OFF output. Therefore, it is also known
as an odd parity generator.
a.
Graphical
Symbol of XNOR gate
b.
Boolean
Expression of XNOR gate
Z=X.Y+X’.Y’ OR Z=(XêššY)’
c.
Truth Table of XNOR gate
|
Inputs |
Output |
|
|
X |
Y |
Z=(XêššY)’ |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
d.
Venn Diagram
of XNOR gate
Universal Gate (NAND & NOR gate)
A universal gate is a gate which can
implement any Boolean function without using any other types of gates. NAND and
NOR gates are known as universal gates. Hence, any Boolean function can be
implemented by using only NAND and NOR gates. We can implement the basic gates
(AND, OR and NOT) using only universal gates as shown below.
Laws of Boolean Algebra:
Duality Principle
According to the Principle of
Duality, dual of a Boolean expression can be obtained by replacing AND(.) with
OR(+) and vice versa, 1 with 0 and vice versa keeping the variables and
complements and variables unchanged.
For example:
Dual of (A+0) is (A.1)
Dual of A.B’+C is A+B’.C
Boolean Postulates
Boolean postulates are the basic
rules of Boolean algebra which are not required to verify.
|
OR
Law |
AND
Law |
NOT
Law |
|
A+0=A |
A.1=A |
0’=1 |
|
A+1=1 |
A.0=0 |
1’=0 |
|
A+A=A |
A.A=A |
A’’=A |
|
A+A’=1 |
A.A’=0 |
Laws of Boolean Algebra
If A,B and C are the Boolean
variables, Plus(+), Dot(.) and Prime(’) are the Boolean operators and 0 and 1
are identities, then , the laws of Boolean algebra are stated as follows:
1.
Identity Law
a.
A+0=A
b.
A.1=A
2.
Complement
Law
a.
A+A’=1
b.
A.A’=0
3.
Idempotent
Law
a.
A+A=A
b.
A.A=A
4.
Boundedness
Law
a.
A+1=1
b.
A.0=0
5.
Absorption
Laws
a.
A+(A.B)=A
b.
A.(A+B)=A
6.
Commutative
Laws
a.
A+B=B+A
b.
A.B=B.A
7.
Associative
Laws
a.
(A+B)+C=A+(B+C)
b.
(A.B).C=A.(B.C)
8.
Distributive
Laws
a.
A.(B+C)=A.B+A.C
b.
A+(B.C)=(A+B).(A+C)
9.
Involution
Laws
a.
(A’)’=A
10.
De Morgan’s
Laws
a.
(A+B)’=A’.B’
b.
(A.B)’=A’+B’
Statement and Verification of Laws
of Boolean Algebra using Truth Table
1.
Identity Law
This
law states that a variable ORed with 0 and ANDed with 1 is always equal to the
variable.
·
A+0=A
·
A.1=A
Truth Table for A+0=A
|
A |
0 |
A+0=A |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
Hence,
A+0=A Proved
Truth Table for A+1=A
|
A |
1 |
A.0=A |
|
0 |
1 |
0 |
|
1 |
1 |
1 |
Hence,
A.1=A Proved
2.
Complement
Law
A
variable ORed with its complement is always equal to 1 and ANDed with its
complement is always equal to 0.
·
A+A’=1
·
A.A’=0
Truth Table for A+A’=1
|
A |
A’ |
A+A’=1 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
Hence,
A+A’=1 Proved
Truth Table for A.A’=0
|
A |
A’ |
A.A’=0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
Hence,
A.A’=0 Proved
3.
Commutative
Law
This
law states that the order in which the variables are ORed or ANDed make no
difference.
·
A+B=B+A
·
A.B=B.A
Truth Table of A+B=B+A
|
A |
B |
A+B |
B+A |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
Hence,
A+B=B+A Proved.
Truth Table of A.B=B.A
|
A |
B |
A.B |
B.A |
|
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
Hence,
A.B=B.A Proved
4.
Associative
Law
This
law states that When ORing or ANDing is more than two variables, the result is
the same regardless of the grouping of the variables.
·
A+(B+C)=(A+B)+C
·
A.(B.C)=(A.B).C
Truth Table of A+(B+C)=(A+B)+C
|
A |
B |
C |
A+B |
B+C |
A+(B+C) |
(A+B)+C |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Hence,
A+(B+C)=(A+B)+C Proved.
Truth Table of A.(B.C)=(A.B).C
|
A |
B |
C |
A.B |
B.C |
A.(B.C) |
(A.B).C |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Hence,
A.(B.C)=(A.B).C Proved
5.
Distributive
Law
This
law states that ORing/ANDing two or more variables and then ANDing/ORing the
result with a single variable is equivalent to ANDing/ORing the single variable
with each of the two or more variables and then ORing/ANDing the products/sums.
·
A.(B+C)=A.B+A.C
·
A+(B.C)=(A+B).(A+C)
Truth Table of A.(B+C)=A.B+A.C
|
A |
B |
C |
B+C |
A.B |
A.C |
A.(B+C) |
A.B+A.C |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Hence,
A.(B+C)=A.B+A.C Proved.
Truth Table of A+(B.C)=(A+B).(A+C)
|
A |
B |
C |
B.C |
A+B |
A+C |
A+(B.C) |
(A+B).(A+C) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Hence,
A+(B.C)=(A+B).(A+C) Proved.
6.
De-Morgan’s Theorem
a.
Theorem-I
De-Morgan's First Theorem states that “The complement of a
product of variables is equal to the sum of the complement of each variable”. i.e. (A.B)’=A’+B’
Logic Diagram for (A.B)’=A’+B’:
Truth Table for (A.B)’=A’+B’
|
Inputs |
Output-1 |
Output-2 |
||||
|
A |
B |
A.B |
(A.B)’ |
A’ |
B’ |
A’+B’ |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Conclusion:
Comparing the values of (A.B)’=A’+B’ from the truth table,
both are equal. Hence, Proved.
b.
Theorem-II
De-Morgan's Second Theorem states that “The complement of a
sum of variables is equal to the product of the complement of each variable”. i.e. (A+B)’=A’.B’
Logic Diagram for (A+B)’=A’.B’:
Truth Table for (A+B)’=A’.B’
|
Inputs |
Output-1 |
Output-2 |
||||
|
A |
B |
A+B |
(A+B)’ |
A’ |
B’ |
A’.B’ |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Conclusion:
Comparing the values of (A+B)’=A’.B’ from the truth table,
both are equal. Hence, Proved.
1's
and 2's complement method
1's
Complement:
A 1’s complement of a given number
is obtained by subtracting each bit of the given number from 1. In another
words, it is obtained simply by inverting 0 to 1 and 1 to 0. For example:
1’s complement of 101 is 010.
2’s Complement:
A 2’s complement of a given number
is obtained by adding 1 to the 1’s complement of the given binary number.
For example: 2’s complement of 101
is 010+1=011.
Steps for Binary
subtraction using 1’s Complement
1. Make the number of bits equal in both subtrahend and
minuend.
2. Calculate 1’s complement of
subtrahend.
3. Calculate sum of minuend and 1’s
complement of subtrahend.
4. Check the overflow bit (carry).
a. If there is overflow bit, discard it and add it to the
remaining part of the sum and the final sum would be the answer.
b. If there is no overflow bit then the result must be
negative. So, again calculate 1’s complement of the sum and that would be the
final answer.
Example 1:
Perform 1010-101 using 1’s
complement method.
- Make the number of bits equal as 1010
and 0101.
- 1’s Complement of 0101 is 1010.
- Adding 1’s complement of subtrahend
with minuend
1010
+1010
10100
- Here, we got overflow bit so, discard
it and add to the remaining part. 0100+1=0101, which is the final
answer.
Example 2:
Perform 101-1010 using 1’s
complement method.
- Make the number of bits equal as 0101
and 1010.
- 1’s Complement of 1010 is 0101.
- Adding 1’s complement of subtrahend
with minuend
0101
+0101
1010
- Here, we didn’t get overflow bit so,
again calculate 1’s complement of 1010 that is 0101 and put minus sign.
Hence, -0101 is the final answer.
Steps for Binary
subtraction using 2’s Complement
1.
Make the number of bits equal in
both subtrahend and minuend.
2. Calculate 2’s complement of subtrahend.
3. Calculate sum of minuend and 2’s complement of subtrahend.
4. Check the overflow bit (carry).
a. If there is overflow bit, discard it and the remaining bits
would be the final answer.
b. If there is no overflow bit then the result must be
negative. So, again calculate 2’s complement of the sum and that would be the
final answer.
Example 3:
Perform 1010-101 using 2’s
complement method.
- Make the number of bits equal as 1010
and 0101.
- 2’s Complement of 0101 is 1010+1=1011.
- Adding 2’s complement of subtrahend
with minuend
1010
+1011
10101
- Here, we got overflow bit which is
discarded and 0101 is the final answer.
Example 4:
Perform 101-1010 using 2’s
complement method.
- Make
the number of bits equal as 0101 and 1010.
- 2’s Complement of 1010 is 0101+1=0110.
- Adding 2’s complement of subtrahend
with minuend
0101
+0110
1011 - Here, we didn’t get overflow bit so,
again calculate 2‘s complement of 1011 that is 0100+1=0101 and put minus
sign. Hence, -0101 is the final answer.
Simplification of Boolean Expression
Large and complex Boolean
Expressions can be simplified by using different laws of Boolean algebra which
simplifies the logic circuit design and reduces the cost. Example: Given the
Boolean Functions F=AB'C+A'B'C+ABC
- List the truth table of the given functions.
- Draw the logic diagram using the given expression
- Simplify the given expression using Boolean algebra
- List the truth table of the functions from simplified
expression
- Draw the logic diagram from the simplified expression
and compare the total number of gates with the diagram of the given
expressions.
Solutions:
(a) Truth table of the given function is as follows:
|
A |
B |
C |
A' |
B' |
AB'C |
A'B'C |
ABC |
F=AB'C+A'B'C+ABC |
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
(b) The logic diagram of the given expression is as follows:
(c) Simplification of the given Boolean Expression:
AB'C+A'B'C+ABC =B'C(A+A')+ABC
[Distributive Law : A.(B+C)=AB+AC] =B'C.1+ABC [Complement Law : A+A'=1]
=B'C+ABC [Identity Law : A.1=A] =C(B'+AB) [Distributive Law : A.(B+C)=AB+AC]
=C(B'+A)(B'+B) [Distributive Law : A+(B.C)=(A+B).(A+C)] =C(B'+A).1 [Complement
Law: A+A'=1] =C(B'+A) [Identity Law: A.1=A] =C(A+B') [Commutative Law: A+B=B+A]
(d) The simplified Boolean Expression is C(A+B') and the
truth table of the functions from simplified expression [F=C(A+B')] is as
follows:
|
A |
B |
C |
B' |
A+B' |
C.(A+B') |
|
0 |
0 |
0 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
1 |
(e)The logic diagram from the simplified expression C(A+B') is as follows:
.png)
Here, the total number of gates used
in the logic circuit for the given Boolean Expression is 6(2 NOT gates+ 3 AND
gates + 1 OR gates ) where as the total number of gates used in the logic
circuit for the simplified Boolean Expression is 3 (1 NOT gate + 1 AND gate + 1
OR gate ). So, the logic circuit for the simplified Boolean Expression is quite
simple and consumes less time to process and low cost to design.
No comments:
Post a Comment