Class 12 Exam  >  Class 12 Notes  >  COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum  >  Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum PDF Download

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science

Boolean algebra is an algebra that deals with Boolean values((TRUE and FALSE) . Everyday
we have to make logic decisions: “Should I carry the book or not?” , “Should I watch TV or not?” etc. Each question will have two answers yes or no, true or false. In Boolean Algebra we use 1 for true and 0 for false which are known as truth values.

Truth table:
A truth table is composed of one column for each input variable (for example, A and B), and one final column for all of the possible results of the logical operation that the table is meant to represent (for example, A XOR B). Each row of the truth table therefore contains one possible configuration of the input variables (for instance, A = true B = false), and the result of the operation for those values.

Logical Operators:
In Algebraic function e use +,-,*,/ operator but in case of Logical Function or Compound statement we use AND,OR & NOT operator. Example: He prefers Computer Science NOT IP.
There are three Basic Logical Operator:
1. NOT
2. OR
3. AND

 NOT Operator—Operates on single variable. It gives the complement value of variable.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 OR Operator -It is a binary operator and denotes logical Addition operation and is represented by ”+” symbol

 

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 AND Operator – AND Operator performs logical multiplications and symbol is (.) dot.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Truth table:

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Question for Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science
Try yourself:
Which algebra deals with Boolean values?
View Solution

Basic Logic Gates
A logic gate is an physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Gates also called logic circuits.

Or

A gate is simply an electronic circuit which operates on one or more signals to produce an output signal. NOT gate (inverter):The output Q is true when the input A is NOT true, the output is the inverse of the input:

Q = NOT A
A NOT gate can only have one input. A NOT gate is also called an inverter.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

AND gate
The output Q is true if input A AND input B are both true: Q = A AND B An AND gate can have two or more inputs, its output is true if all inputs are true.

 

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

OR gate
The output Q is true if input A OR input B is true (or both of them are true): Q = A OR B An OR gate can have two or more inputs, its output is true if at least one input is true.

 

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Basic postulates of Boolean Algebra:
Boolean algebra consists of fundamental laws that are based on theorem of Boolean algebra. These fundamental laws are known as basic postulates of Boolean algebra. These postulates states basic relations in boolean algebra, that follow:
I If X != 0 then x=1 and If X!=1 then x=0
II OR relations(logical addition)

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 

Question for Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science
Try yourself:
Which type of logic gate produces an output that is the inverse of the input?
View Solution

Principal of Duality
This principal states that we can derive a Boolean relation from another Boolean relation by performing simple steps. The steps are:-
1. Change each AND(.) with an OR(+) sign
2. Change each OR(+) with an AND(.) sign
3. Replace each 0 with 1 and each 1 with 0
e.g
0+0=0 then dual is 1.1=1
1+0=1 then dual is 0.1=0

 

Basic theorem of Boolean algebra
Basic postulates of Boolean algebra are used to define basic theorems of Boolean algebra that provides all the tools necessary for manipulating Boolean expression.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Some other rules of Boolean algebra
Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Question for Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science
Try yourself:
Which principal of Boolean algebra states that we can derive a Boolean relation from another Boolean relation by performing simple steps?
View Solution

Derivation of Boolean expression:-
 

Minterm :
minterm is a Product of all the literals within the logic System.
Step involved in minterm expansion of Expression
1. First convert the given expression in sum of product form.
2. In each term is any variable is missing(e.g. in the following example Y is missing in first term and X is missing in second term), multiply that term with (missing term +complement( missing term) )factor e.g. if Y is missing multiply with Y+Y” )
3. Expand the expression .
4. Remove all duplicate terms and we will have minterm form of an expression.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Other procedure for expansion could be
1. Write down all the terms
2. Put X‟s where letters much be inserted to convert the term to a product term
3. Use all combination of X‟s in each term to generate minterms
4. Drop out duplicate terms
 

Shorthand Minterm notation:
Since all the letters must appear in every product, a shorthand notation has been developed that saves actually writing down the letters themselves. To form this notation, following steps are to be followed:
1. First of all, Copy original terms
2. Substitute 0s for barred letters and 1s for nonbarred letters
3. Express the decimal equivalent of binary word as a subscript of m.
Rule1. Find Binary equivalent of decimal subscript e.g.,for m6 subscript is 6, binary equivalent of 6 is 110.
Rule 2. For every 1s write the variable as it is and for 0s write variables complemented form i.e., for 110 t is XYZ. XYZ is the required minterm for m6.
 

maxterm:
A maxterm is a sum of all the literals (with or without the bar) within the logic system. Boolean Expression composed entirely either of Minterms or Maxterms is referred to as Canonical Expression.
 

Question for Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science
Try yourself:
Which step is involved in the minterm expansion of a Boolean expression?
View Solution

Canonical Form:
Canonical expression can be represented is derived from
(i) Sum-of-Products(SOP) form
(ii) Product-of-sums(POS) form

Sum of Product (SOP)
1. Various possible input values
2. The desired output values for each of the input combinations

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Product of Sum (POS)
When a Boolean expression is represented purely as product of Maxterms, it is said to be in Canonical Product-of-Sum from of expression.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Minimization of Boolean expressions:-
After obtaining SOP and POS expressions, the next step is to simplify the Boolean expression.
There are two methods of simplification of Boolean expressions.
1. Algebraic Method
2. Karnaugh Map :

1.Algebraic method:This method makes use of Boolean postulates, rules and theorems to simplify the
expression.
Example No. 1: Reduce the expression

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

2. Using Karnaugh Map :
Karnaugh Maps:
Karnaugh map or K Map is a graphical display of the fundamental product in a truth table.
For example:

  •  Put a 1 in the box for any minterm that appears in the SOP expansion.
  •  Basic idea is to cover the largest adjacent blocks you can whose side length is some power of 2.
  •  Blocks can “wrap around” the edges.

      Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Remember, group together adjacent cells of 1s, to form largest possible rectangles of sizes that are  powers of 2. Notice that you can overlap the blocks if necessary.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Question for Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science
Try yourself:
What are the two forms of canonical expressions?
View Solution

For reducing the expression first mark Octet, Quad, Pair then single.
• Pair: Two adjacent 1’s makes a pair.
• Quad: Four adjacent 1’s makes a quad.
• Octet: Eight adjacent 1’s makes an Octet.
• Pair removes one variable.
• Quad removes two variables.
• Octet removes three variables.
Reduction of expression: When moving vertically or horizontally in pair or a quad or an octet it can be observed that only one variable gets changed that can be eliminated directly in the expression. For Example

In the above Ex

Step 1 : In K Map while moving from m7 to m15 the variable A is changing its state Hence it can be removed directly, the solution becomes B.CD = BCD. This can be continued for all the pairs, Quads, and Octets.

Step 2 : In K map while moving from m0 to m8 and m2 to m10 the variable A is changing its state. Hence B’ can be taken similarly while moving from m0 to m2 and m8 to m10 the variable C is changing its state. Hence D’ can be taken; the solution becomes B’.D’ The solution for above expression using K map is BCD + B’D’.

Example1: Reduce the following Boolean expression using K-Map:
F(P,Q,R,S)=Σ(0,3,5,6,7,11,12,15)

Soln:
This is 1 quad, 2pairs & 2 lock
Quad(m3+m7+m15+m11) reduces to RS
Pair(m5+m7) reduces to P‟QS
Pair (m7+m6) reduces to P‟QR
Block m0=P‟Q‟R‟S‟
M12=PQR‟S‟
hence the final expressions is F=RS + P‟QS + P‟QR + PQR‟S‟ + P‟Q‟R‟S‟

 

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Example2: Reduce the following Boolean expression using K-Map:
F(A,B,C,D)=Π(0,1,3,5,6,7,10,14,15)

Soln:
Reduced expressions are as follows:
For pair 1, (A+B+C)
For pair 2, (A‟+C‟+D)
For Quad 1, (A+D‟)
For Quad 2, (B‟+C‟)
Hence final POS expression will be

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

More about Gates:
NAND gate (NAND = Not AND)
This is an AND gate with the output inverted, as shown by the 'o' on the output. The output is true if input A AND input B are NOT both true: Q = NOT (A AND B) A NAND gate can have two or more inputs, its output is true if NOT all inputs are true.
NOR gate (NOR = Not OR)
This is an OR gate with the output inverted, as shown by the 'o' on the output. The output Q is true if NOT inputs A OR B are true: Q = NOT (A OR B) A NOR gate can have two or more inputs, its output is true if no inputs are true.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 

EX-OR (EXclusive-OR) gate
The output Q is true if either input A is true OR input B is true, but not when both of them are true: Q = (A AND NOT B) OR (B AND NOT A) This is like an OR gate but excluding both inputs being true. The output is true if inputs A and B are DIFFERENT. EX-OR gates can only have 2 inputs.
EX-NOR (EXclusive-NOR) gate
This is an EX-OR gate with the output inverted, as shown by the 'o' on the output. The output Q is true if inputs A and B are the SAME (both true or both false):

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 

 

Q = (A AND B) OR (NOT A AND NOT B) EX-NOR gates can only have 2 inputs.
Summary truth tables
The summary truth tables below show the output states for all types of 2-input and 3-input gates.

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Question for Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science
Try yourself:
Which gate has an output that is true if both inputs are the same?
View Solution

NAND gate equivalents
The table below shows the NAND gate equivalents of NOT, AND, OR and NOR gates:

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Low Order Thinking Questions: (Boolean Algebra)
a) State and verify absorption law in Boolean algebra.
Ans. Absorption Law states that :
a) X+XY=X b) X(X+Y)=X
b) Verify X’.Y+X.Y’=(X’+Y’).(X+Y) algebraically.
Ans. LHS= X’Y + XY’
= (X’+X) (X’+Y’) (Y+X) (Y+Y’)
= 1.(X’+Y’) (X+Y).1
= (X’+Y’) (X+Y)
= RHS, hence proved
c) Write the equivalent Boolean Expression F for the following circuit diagram :

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

 

Ans.: A’B+AB+B’C
d) If F(P,Q,R,S) = Π (3,4,5,6,7,13,15) , obtain the simplified form using K-Map.
Ans.:

Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

Reduction of groups following the reduction rule :
Quad1 = M4.M5.M6.M7
= P+Q’
Quad2 = M5.M7.M13.M15
= Q’+S’
Pair = M3.M7
= P+R’+S’
Therefore POS of F(P,Q,R,S) = (P+Q’)(Q’+S’)(P+R’+S’)
e) F(a,b,c,d)=Σ(0,2,4,5,7,8,10,12,13,15)
F(a,b,c,d)=B1+B2+B3
B1=m0+m4+m12+m8==c’d’
B2=m5+m7+m13+m15=bd
B3=m0+m2+m8+m10=b’d’
F(a,b,c,d)=c’d’+bd+b’d’
f) Write the equivalent Boolean expression for the following logic circuit:
Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

The document Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum is a part of the Class 12 Course COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum.
All you need of Class 12 at this link: Class 12
9 docs

FAQs on Chapter 7 - Boolean Algebra, Chapter Notes, Class 12, Computer Science - COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

1. What is Boolean Algebra?
Ans. Boolean algebra is a branch of algebra that deals with binary variables and logical operations. It is used in digital electronics, computer programming, and other areas where logic gates and logical operations are used. In Boolean algebra, the variables can take only two values, i.e., 0 and 1, and logical operations include AND, OR, NOT, XOR, etc.
2. What are the basic laws of Boolean algebra?
Ans. The basic laws of Boolean algebra are as follows: 1. Commutative law: A + B = B + A and AB = BA 2. Associative law: (A + B) + C = A + (B + C) and (AB)C = A(BC) 3. Distributive law: A(B + C) = AB + AC and (A + B)(C + D) = AC + AD + BC + BD 4. Identity law: A + 0 = A and A1 = A 5. Inverse law: A + A' = 1 and AA' = 0 These laws are used to simplify Boolean expressions and to design logic circuits.
3. What is the truth table of the AND operation?
Ans. The truth table of the AND operation is as follows: A B A AND B 0 0 0 0 1 0 1 0 0 1 1 1 The AND operation returns 1 only when both inputs are 1, otherwise, it returns 0.
4. What is the difference between AND and OR operators in Boolean algebra?
Ans. The AND and OR operators are two basic logical operations in Boolean algebra. The main difference between them is that the AND operator returns 1 only when both inputs are 1, whereas the OR operator returns 1 when at least one input is 1. For example, A AND B returns 1 only when both A and B are 1, otherwise, it returns 0. On the other hand, A OR B returns 1 if either A or B or both are 1.
5. How do you simplify Boolean expressions using Boolean algebra?
Ans. Boolean algebra provides various laws and rules to simplify Boolean expressions. The simplification process involves applying these laws and rules to the given expression to reduce it to its simplest form. The steps to simplify a Boolean expression are as follows: 1. Use the commutative and associative laws to rearrange the expression. 2. Use the distributive law to expand the expression. 3. Use the identity law to simplify the expression. 4. Use the inverse law to simplify the expression. 5. Use the De Morgan's law to simplify the expression. 6. Use the double negation law to simplify the expression. By applying these steps, we can simplify any Boolean expression and reduce it to its simplest form.
9 docs
Download as PDF
Explore Courses for Class 12 exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Chapter 7 - Boolean Algebra

,

Exam

,

Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

,

shortcuts and tricks

,

Important questions

,

Objective type Questions

,

Semester Notes

,

ppt

,

past year papers

,

Chapter Notes

,

Chapter Notes

,

Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

,

Previous Year Questions with Solutions

,

Extra Questions

,

video lectures

,

practice quizzes

,

Chapter 7 - Boolean Algebra

,

Summary

,

mock tests for examination

,

Computer Science | COMPUTER SCIENCE for Class 12(XII) - CBSE & NCERT Curriculum

,

Sample Paper

,

pdf

,

study material

,

Class 12

,

MCQs

,

Class 12

,

Viva Questions

,

Chapter Notes

,

Free

,

Class 12

,

Chapter 7 - Boolean Algebra

;