(XI) Ch-2 Number System and Boolean Algebra

Number System and Conversion	Binary Calculations
1's and 2's Complement method for Binary	Introduction to Boolean algebra
Logic Gates	Laws of Boolean Algebra

1. What is number system? Answer: The system concerned with the number and represented by a sequence of digits is called number system. It plays a vital role in computing and electronics. Number system also refers to the digits, its arrangement, positional value, and base of number system. 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:

Number System Conversion:
We mainly focused on twelve(12) types of conversion for four types of number systems which can be grouped as follows based on the common method to be used for conversion.
(i) Decimal to other systems(Binary / Octal / Hexadecimal) conversion
(ii) Other systems to Decimal conversion
(iii) Binary to Octal and Hexadecimal Conversion
(iv) Octal and Hexadecimal to Binary Conversion
(v) Octal to Hexadecimal Conversion
(vi) Hexadecimal to Octal Conversion

Decimal to Binary, Octal, and Hexadecimal Conversion

A decimal number is converted into other number systems by using successive division by to be converted number base(e.g. if binary then by 2) where remainders noted during successive divisions are written in a bottom-up approach to get the required number system.

The fraction part of any decimal number is converted into other numbers by successive multiplication to the given number with a respective base of to be converted number (e.g. if binary then by 2). The process is terminated when we get zero(0) in the fraction part of the product. When we fail to get zero(0), then we may terminate the process after 5th round. The integer values that come from each successive multiplication are written in the top-down approach.
Conversion 1: (42)₁₀=(?)₂

2	42	Remainder
2	21	0
2	10	1
2	5	0
2	2	1
2	1	0
	0	1

∴(42)₁₀=(101010)₂

---

Conversion 2: (42.54)₁₀=(?)₂ 

2	42	Remainder
2	21	0
2	10	1
2	5	0
2	2	1
2	1	0
	0	1

∴(42)₁₀=(101010)₂
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)₁₀=(101010.10001)₂

---

Conversion 3: (123)₁₀=(?)₈

8	123	Remainder
8	15	3
8	1	7
	0	1

∴(123)₁₀=(173)₈

---

Conversion 4: (123.54)₁₀=(?)₈ 

8	123	Remainder
8	15	3
8	1	7
	0	1

∴(123)₁₀=(173)₈
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)₁₀=(173.42436)₈

---

Conversion 5: (123)₁₀=(?)₁₆

16	123	Remainder
16	7	11 (B)
	0	7

∴(123)₁₀=(7B)₁₆

---

Conversion 6: (123.54)₁₀=(?)₁₆ 

16	123	Remainder
16	7	11 (B)
	0	7

∴(123)₁₀=(7B)₁₆
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)₁₀=(7B.8A3D7)₁₆

---

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)₂=(?)₁₀
Answer:

Face Value	1	0	1	0	1	0
Place Value	25	24	23	22	21	20

=1x2⁵+0x2⁴+1x2³+0x2²+1x2¹+0x2⁰
=1×32+0×16+1×8+0×4+1×2+0×1
=32+0+8+0+2+0 
=(42)₁₀
∴(101010)₂=(42)₁₀

---

Conversion 8: (101.101)₂=(?)₁₀
Answer:

Face Value	1	0	1	.1	0	1
Place Value	22	21	20	2-1	2-2	2-3

=1x2²+0x2¹+1x2⁰+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)₁₀
∴(101.101)₂=(5.625)₁₀

---

Conversion 9: (345)₈=(?)₁₀
Answer:

Face Value	3	4	5
Place Value	82	81	80

=3x8²+4x8¹+5x8⁰
=3×64+4×8+5×1
=192+32+5
=(229)₁₀
∴(345)₈=(229)₁₀

---

Conversion 10: (31.76)₈=(?)₁₀
Answer:

Face Value	3	1	.7	6
Place Value	81	80	8-1	8-2

=3x8¹+1x8⁰+7x8^-1+6x8^-2
=3x8+1x1+7x0.125+6x0.015625
=24+1+0.875+0.09375
=(25.96875)₁₀
∴(31.76)₈=(25.96875)₁₀

---

Conversion 11: (ABC)₁₆=(?)₁₀
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

=Ax16²+Bx16¹+Cx16⁰
=10×256+11×176+12×1
=2560+176+12 
=(2748)₁₀
∴(ABC)₁₆=(2748)₁₀

---

Conversion 12: (3F.7A)₁₆=(?)₁₀
Answer:

Face Value	3	F	.7	A
Place Value	161	160	16-1	16-2

=3x16¹+Fx16⁰+7x16^-1+Ax16^-2
=3x16+15x1+7x0.0625+10x0.00390625
=48+15+0.4375+0.0390625
=(63.4765625)₁₀
∴(3F.7A)₁₆=(63.4765625)₁₀

---

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)₂=(?)₈
Answer:

3 BITS Group	001	011	101
Octal Value	1	3	5

∴(1011101)₂=(135)₈

---

Conversion 14: (1011101.1011001)₂=(?)₈
Answer:

3 BITS Group	001	011	101	.101	100	100
Octal Value	1	3	5	.5	4	4

∴(1011101.1011001)₂=(135.544)₈

---

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)₂=(?)₁₆
Answer:

4 BITS Group	0101	1101
Hexadecimal	5	13(D)

∴(1011101)₂=(5D)₁₆

---

Conversion 16: (1011101.101111)₂=(?)₁₆
Answer:

4 BITS Group	0101	1101	.1011	1100
Hexadecimal	5	13(D)	.11(B)	12(C)

∴(1011101.101111)₂=(5D.BC)₁₆

---

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)₈=(?)₂
Answer:

Octal Digits	5	6	7
Equivalent BITS	101	110	111

∴(567)₈=(101110111) ₂

---

Conversion 18: (567.123)₈=(?)₂
Answer:

Octal Digits	5	6	7	.1	2	3
Equivalent BITS	101	110	111	.001	010	011

∴(567.123)₈=(101110111.001010011)₂

---

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)₁₆=(?)₂
Answer:

Hexadecimal Digits	A	4	3
Equivalent BITS	1010	0100	0011

∴(A43)₁₆=(101001000011) ₂

---

Conversion 20: (4A3.EF)₁₆=(?)₂
Answer:

Hexadecimal Digits	4	A	3	.E	F
Equivalent BITS	0100	1010	0011	.1110	1111

∴(4A3.EF)₁₆=(010010100011.11101111)₂

---

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)₈=(?)₁₆
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)₈=(101110111)₂
Now, obtained binary number is converted into hexadecimal number as:

4 BITS Group	0001	0111	0111
Hexadecimal Digits	1	7	7

So, (101110111)₂=(177)₁₆
∴(567)₈=(177)₁₆ Method - II

---

Here, given octal number is first converted into equivalent decimal number.

Face Value	5	6	7
Place Value	82	81	80

=5x8²+6x8¹+7x8⁰
=5×64+6×8+7×1
=320+48+7
=(375)₁₀
Now, the obtained decimal number is converted into hexadecimal number as:

16	375	Remainder
16	23	7
16	1	7
	0	1

So, (375)₁₀=(177)₁₆
∴(567)₈=(177)₁₆

---

Conversion 22: (123.456)₈=(?)₁₆
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)₈=(1010011.100101110)₂
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)₂=(53.970)₁₆
∴(123.456)₈=(53.97)₁₆

---

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)₁₆=(?)₈
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)₁₆=(10111100111)₂
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)₂=(2747)₈
∴(5E7)₁₆=(2747)₈ Method - II

---

Here, given hexadecimal number is first converted into equivalent decimal number.

Face Value	5	E	7
Place Value	162	161	160

=5x16²+Ex16¹+7x16⁰
=5×256+14×16+7×1
=1280+224+7
=(1511)₁₀
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)₁₀=(2747)₈
∴(5E7)₁₆=(2747)₈

---

Conversion 24: (5E7.3D)₁₆=(?)₈
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)₁₆=(10111100111.00111101)₂
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)₂=(2747.175)₁₆
∴(5E7.3D)₁₆=(2747.175)₁₆

---

Binary Addition

---

Binary Subtraction

 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:

1. A+A’B

2. 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

It is also known as logical multiplication. It is carried out by dot(.) operator or simply by AND. It generates true output if all the inputs are true otherwise it generates false output. The logical equation of AND operation is written as C=A.B or C= A AND B. The truth table of AND operation is given below:

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.

1. Graphical Symbol of AND gate
   

2. Boolean Expression of AND gate:

Z=X.Y

3. Truth table of AND gate

Inputs		Output
X	Y	Z=X.Y
0	0	0
0	1	0
1	0	0
1	1	1

4. 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.

1. Graphical Symbol of OR gate:
   

2. Boolean Expression of OR gate:
   Z=X+Y

3. Truth Table of OR gate:

Inputs		Output
X	Y	Z=X+Y
0	0	0
0	1	1
1	0	1
1	1	1

4. 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.

1. Graphical Symbol of NOT gate:
   

2. Boolean Expression of NOT gate:
   Z=X’

3. Truth Table of NOT gate:

Input	Output
X	Z=X’
0	1
1	0

4. 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.

1. Graphical Symbol of NAND gate
   

2. Boolean Expression of NAND gate
   Z=(X.Y)’

3. Truth Table of NAND gate
   
   

Inputs		Output
X	Y	Z=(X.Y)’
0	0	1
0	1	1
1	0	1
1	1	0

4. 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.

1. Graphical Symbol of NOR gate
   

2. Boolean Expression of NOR gate
   Z=(X+Y)’

3. Truth Table of NOR gate
   
   

Inputs		Output
X	Y	Z=(X+Y)’
0	0	1
0	1	0
1	0	0
1	1	0

4. 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.

1. Graphical Symbol of XOR gate
   

2. Boolean Expression of XOR gate
   Z=X’.Y+X.Y’   OR  Z=XꚚY

3. Truth Table of XOR gate
   
   

Inputs		Output
X	Y	Z=XꚚY
0	0	0
0	1	1
1	0	1
1	1	0

4. 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.

1. Graphical Symbol of XNOR gate
   

2. Boolean Expression of XNOR gate
   Z=X.Y+X’.Y’   OR  Z=(XꚚY)’

3. Truth Table of XNOR gate
   
   

Inputs		Output
X	Y	Z=(XꚚY)’
0	0	1
0	1	0
1	0	0
1	1	1

4. 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

1. A+0=A

2. A.1=A

2. Complement Law

1. A+A’=1

2. A.A’=0

3. Idempotent Law

1. A+A=A

2. A.A=A

4. Boundedness Law

1. A+1=1

2. A.0=0

5. Absorption Laws

1. A+(A.B)=A

2. A.(A+B)=A

6. Commutative Laws

1. A+B=B+A

2. A.B=B.A

7. Associative Laws

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

2. (A.B).C=A.(B.C)

8. Distributive Laws

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

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

9. Involution Laws

1. (A’)’=A

10. De Morgan’s Laws

1. (A+B)’=A’.B’

2. (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

1. 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.

2. 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

1. List the truth table of the given functions.
2. Draw the logic diagram using the given expression
3. Simplify the given expression using Boolean algebra
4. List the truth table of the functions from simplified expression
5. 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:

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.

End of Chapter-2