Unit - 3-Boolean Algebra & Computer Logic
Uploaded by
mansi deshmukhUnit - 3-Boolean Algebra & Computer Logic
Uploaded by
mansi deshmukhUnit 3
Boolean Algebra & Computer Logic
Boolean algebra is a type of algebra that is created by operating the
binary system. In the year 1854, George Boole, an English mathematician,
proposed this algebra. This is a variant of Aristotle’s propositional logic
that uses the symbols 0 and 1, or True and False. Boolean algebra is
concerned with binary variables and logic operations.
Boolean Algebra is fundamental in the development of digital electronics
systems as they all use the concept of Boolean Algebra to execute
commands. Apart from digital electronics this algebra also finds its
application in Set Theory, Statistics, and other branches of mathematics.
In this article, we will learn about basic Boolean operations, Boolean
expressions, Truth Tables, Boolean laws, and others in detail.
What is Boolean Algebra?
Boolean Algebra is a branch of algebra that deals with boolean
values—true and false. It is fundamental to digital logic design and
computer science, providing a mathematical framework for describing
logical operations and expressions
Boolean Algebra Operations
Various operations are used in Boolean algebra but the basic operations
that form the base of Boolean Algebra are.
● Negation or NOT Operation
● Conjunction or AND Operation
● Disjunction or OR Operation
Boolean Algebra Expression
These operations have their own symbols and precedence and the table
added below shows the symbol and the precedence of these operators.
Operator Symbol Precedence
NOT ‘ (or) ⇁ First
AND . (or) ∧ Second
OR + (or) ∨ Third
We can easily define these operations using two boolean variables.
Let’s take two boolean variables A and B that can have any of the two
values 0 or 1, i.e. they can be either OFF or ON. Then these operations are
explained as,
Negation or NOT Operation
Using the NOT operation, reverse the value of the Boolean variable from 0
to 1 or vice-versa. This can be understood as:
● If A = 1, then using NOT operation we have (A)’ = 0
● If A = 0, then using the NOT operation we have (A)’ = 1
● We also represent the negation operation as ~A, i.e if A = 1, ~A =
Conjunction or AND Operation
Using the AND operation satisfies the condition that if both the value of
the individual variables are true and if any of the values is false then this
operation gives the negative result. This can be understood as,
● If A = True, B = True, then A . B = True
● If A = True, B = False, Or A = false, B = True, then A . B = False
● If A = False, B = False, then A . B = False
Disjunction (OR) Operation
Using the OR operation satisfies the condition that if any value of the
individual variables is true, it only gives a negative result if both the
values are false. This can be understood as,
● If A = True, B = True, then A + B = True
● If A = True, B = False, Or A = false, B = True, then A + B = True
● If A = False, B = False, then A + B = Falses
Boolean Algebra Table
Given Below is the Expression for the Boolean Algebra
Symb
Operation Definition
ol
Returns true only if both inputs are
AND Operation ⋅ or ∧
true.
Returns true if at least one input is
OR Operation + or ∨
true.
NOT Operation ¬ or ∼ Reverses the input.
Returns true if exactly one input is
XOR Operation ⊕
true.
NAND Returns false only if both inputs are
↓
Operation true.
Returns false if at least one input is
NOR Operation ↑
true.
XNOR
↔ Returns true if both inputs are equal.
Operation
Boolean Expression and Variables
Boolean expression is an expression that produces a Boolean value when
evaluated, i.e. it produces either a true value or a false value. Whereas
boolean variables are variables that store Boolean numbers.
P + Q = R is a Boolean phrase in which P, Q, and R are Boolean variables
that can only store two values: 0 and 1. The 0 and 1 are the synonyms for
false and True and are used in Boolean Algebra, sometimes we also use
“Yes” in place of True and “No” in place of False.
Thus, we can say that statements using Boolean variables and operating
on Boolean operations are Boolean Expressions. Some examples of
Boolean expressions are,
● A + B = True
● A.B = True
● (A)’ = False
Boolean Algebra Terminologies
There are various terminologies related to Boolean Algebra, which are
used to explain various parameters of Boolean Algebra. That includes,
● Boolean Variables
● Boolean Function
● Literal
● Complement
● Truth Table
Now, we will discuss the important terminologies of Boolean algebra in
the article below,
Boolean Variables
Variables used in Boolean algebra that store the logical value of 0 and 1
are called the boolean variables. They are used to store either true or false
values. Boolean variables are fundamental in representing logical states
or propositions in Boolean expressions and functions.
Boolean Function
A function of the Boolean Algebra that is formed by the use of Boolean
variables and Boolean operators is called the Boolean function. It is
formed by combining Boolean variables and logical expressions such as
AND, OR, and NOT. It is used to model logical relationships, conditions, or
operations.
Literal
A variable or the complement of the variable in Boolean Algebra is called
the Literal. Literals are the basic building blocks of the boolean
expressions and functions. They represent the operands in logical
operations.
Complement
The inverse of the Boolean variable is called the complement of the
variable. The complement of 0 is 1 and the complement of 1 is 0. It is
represented by ‘ or (¬) over the variable. Complements are used to
represent logical negations in Boolean expressions and functions.
Truth Table
Table containing all the possible values of the logical variables and the
combination of the variable along with the given operation is called the
truth table. The number of rows in the truth table depends on the total
Boolean variables used in that function. It is given by using the formula,
Number of Rows in Truth Table = 2n
where “n” is the number of Boolean variables used.
Truth Tables in Boolean Algebra
A truth table represents all the combinations of input values and outputs
in a tabular manner. All the possibilities of the input and output are
shown in it and hence the name truth table. In logic problems, truth tables
are commonly used to represent various cases. T or 1 denotes ‘True’ & F or
0 denotes ‘False’ in the truth table.
Example: Draw the truth table of the conditions A + B and A.B where A
and b are boolean variables.
Solution:
The required Truth Table is,
X=A+ Y=
A B B A.B
T T T T
T F T F
F T T F
F F F F
Boolean Algebra Rules
In Boolean Algebra there are different fundamental rules for logical
expression.
● Binary Representation: In Boolean Algebra the variables can have
only two values either 0 or 1 where 0 represents Low and 1
represents high. These variables represent logical states of the
system.
● Complement Representation: The complement of the variables is
represented by (¬) or (‘) over the variable. This indicates logical
negation or inversion of the variable’s value. So Complement of
variable A can be represented by
● A‾
● A
● ,if the value of A=0 then its complement is 1.
● OR Operation: The OR operation is represented by (+) between
the Variables. OR operation returns true if at least one of the
operands is true. For Examples let us take three variables A,B,C
the OR operation can be represented as A + B + C.
● AND Operation: The AND Operation is denoted by (.) between
the Variables. AND operation returns true only if all the operands
are true. For Examples let us take three variables A,B,C the AND
operation can be represented A.B.C or ABC.
Laws for Boolean Algebra
The basic laws of the Boolean Algebra are added in the table added
below,
Law OR form AND form
Identity Law P+0=P P.1 = P
Idempotent Law P+P=P P.P = P
Commutative
P+Q=Q+P P.Q = Q.P
Law
P + (Q + R) = (P + Q) +
Associative Law P.(Q.R) = (P.Q).R
R
P + QR = (P + Q).(P + P.(Q + R) = P.Q +
Distributive Law
R) P.R
Inversion Law (A’)’ = A (A’)’ = A
De Morgan’s Law (P + Q)’ = (P)’.(Q)’ (P.Q)’ = (P)’ + (Q)’
Let’s learn about these laws in detail.
Identity Law
In the Boolean Algebra, we have identity elements for both AND(.) and
OR(+) operations. The identity law state that in boolean algebra we have
such variables that on operating with AND and OR operation we get the
same result, i.e.
● A + 0 = A
● A.1 = A
Commutative Law
Binary variables in Boolean Algebra follow the commutative law. This law
states that operating boolean variables A and B is similar to operating
boolean variables B and A. That is,
● A. B = B. A
● A + B = B + A
Associative Law
Associative law states that the order of performing Boolean operator is
illogical as their result is always the same. This can be understood as,
● ( A . B ) . C = A . ( B . C )
● ( A + B ) + C = A + ( B + C)
Distributive Law
Boolean Variables also follow the distributive law and the expression for
Distributive law is given as:
● A . ( B + C) = (A . B) + (A . C)
Inversion Law
Inversion law is the unique law of Boolean algebra this law states that,
the complement of the complement of any number is the number itself.
● (A’)’ = A
Apart from these other laws are mentioned below:
AND Law
AND law of the Boolean algebra uses AND operator and the AND law is,
● A . 0 = 0
● A . 1 = A
● A . A = A
OR Law
OR law of the Boolean algebra uses OR operator and the OR law is,
● A + 0 = A
● A + 1 = 1
● A + A = A
De Morgan’s Laws are also called De morgan’s Theorem. They are the
most important laws in Boolean Algebra and these are added below
under the heading Boolean Algebra Theorem
Boolean Algebra Theorems
There are two basic theorems of great importance in Boolean Algebra,
which are De Morgan’s First Laws, and De Morgan’s Second Laws. These
are also called De Morgan’s Theorems. Now let’s learn about both in
detail.
De Morgan’s First laws
De Morgan’s Law states that the complement of the product (AND) of two
Boolean variables (or expressions) is equal to the sum (OR) of the
complement of each Boolean variable (or expression).
(P.Q)’ = (P)’ + (Q)’
The truth table for the same is given below:
P Q (P)’ (Q)’ (P.Q)’ (P)’ + (Q)’
T T F F F F
T F F T T T
F T T F T T
F F T T T T
We can clearly see that truth values for (P.Q)’ are equal to truth values for
(P)’ + (Q)’, corresponding to the same input. Thus, De Morgan’s First Law
is true.
De Morgan’s Second laws
Statement: The Complement of the sum (OR) of two Boolean variables (or
expressions) is equal to the product(AND) of the complement of each
Boolean variable (or expression).
(P + Q)’ = (P)’.(Q)’
Proof:
The truth table for the same is given below:
(P +
P Q (P)’ (Q)’ (P)’.(Q)’
Q)’
T T F F F F
T F F T F F
F T T F F F
F F T T T T
We can clearly see that truth values for (P + Q)’ are equal to truth values
for (P)’.(Q)’, corresponding to the same input. Thus, De Morgan’s Second
Law is true.
Articles related to Boolean Algebra:
● Properties of Boolean Algebra
● Principle of Mathematical Induction
● Logic Gates
Solved Examples on Boolean Algebra
Draw Truth Table for P + P.Q = P
Solution:The truth table for P + P.Q = P
P Q P.Q P + P.Q
T T T T
T F F T
F T F F
F F F F
In the truth table, we can see that the truth values for P + P.Q is exactly
the same as P.
Draw Truth Table for P.Q + P + Q
Solution:
The truth table for P.Q + P + Q
P Q P.Q P.Q + P + Q
T T T T
T F F T
F T F T
F F F F
Solve
A‾+B⋅C
A+B⋅C
Solution:
Using De Morgan’s Law
A‾+B.C=A‾.(B+C)
A+B.C=A.(B+C)
Using Distributive Law
A.(B+C)=A.B+A.C
So, the simplified expression for the given equation
A.(B+C)=A.B+A.C
Where is Boolean Algebra Used?
Boolean Algebra finds applications in many other fields of science related
to digital logic design, computer science, telecommunications, etc. It will
equip you with the basics of designing and analyzing digital circuits;
therefore, this is an introduction to the backbone of modern digital
electronics. Boolean Algebra also forms a framework of logical
expressions essential in simplification and optimization while
programming and designing algorithms.
Digital Logic Design:
Boolean Algebra acts as the backbone of digital logic design, being the
most important element in the creation and analysis of digital circuits
used in computers, smartphones, and all other electronic devices. It helps
simplify the logic gates and circuits so that in the design of digital
systems, they can be effectively designed and optimized.
Computer Science:
In computer science, Boolean Algebra is utilized in the design and study of
algorithms, particularly in fields that require decision-making processes.
It’s vital in database query optimization, where Boolean logic is utilized to
filter and obtain specific data based on circumstances.
Telecommunications:
Boolean Algebra finds application in the design and analysis of
communication systems in telecommunication. More specifically, it is used
in error detection and correction mechanisms. It is also used in the
modulation and encoding of signals so that data is efficiently and
accurately transmitted over networks.
Artificial Intelligence (AI):
Boolean Algebra is vital in AI, notably in the construction of
decision-making algorithms and neural networks. It’s used to model
logical thinking and decision trees, which are crucial in machine learning
and expert systems.
Electrical Engineering:
In electrical engineering, Boolean Algebra is employed to analyze and
design switching circuits, which are important in the operation of electrical
networks and systems.It aids in the optimization of these circuits, ensuring
minimal energy loss and effective functioning.
Advantages, Disadvantages, and Applications
Advantages
● Simplifies the design and analysis of digital circuits.
● Reduces the complexity of logical expressions and functions.
● Enhances efficiency in digital logic design and computer
programming.
Disadvantages
● Limited to binary values, which may not always represent
real-world complexities.
● Requires a strong understanding of logical operators and rules.
Applications
● Digital electronics and circuit design.
● Computer programming and algorithm optimization.
● Telecommunications for logical signal processing.
● Set theory and mathematical logic.
Introduction of K-Map (Karnaugh Map)
In many digital circuits and practical problems, we need to find
expressions with minimum variables. We can minimize Boolean
expressions of 3, 4 variables very easily using K-map without using any
Boolean algebra theorems.
K-map can take two forms:
1. Sum of product (SOP)
2. Product of Sum (POS)
According to the need of the problem. K-map is a table-like
representation, but it gives more information than the TABLE. We fill a
grid of the K-map with 0’s and 1’s then solve it by making groups.
Steps to Solve Expression using K-map
1. Select the K-map according to the number of variables.
2. Identify minterms or maxterms as given in the problem.
3. For SOP put 1’s in blocks of K-map respective to the minterms
(0’s elsewhere).
4. For POS put 0’s in blocks of K-map respective to the max terms
(1’s elsewhere).
5. Make rectangular groups containing total terms in power of two
like 2,4,8 ..(except 1) and try to cover as many elements as you
can in one group.
6. From the groups made in step 5 find the product terms and sum
them up for SOP form.
SOP FORM
1. K-map of 3 variables
K-map SOP form for 3 variables
Z= ?A,B,C(1,3,6,7)
From red group we get product term—
A’C
From green group we get product term—
AB
Summing these product terms we get- Final expression (A’C+AB)
2. K-map for 4 variables
K-map 4 variable SOP form
F(P,Q,R,S)=?(0,2,5,7,8,10,13,15)
From red group we get product term—
QS
From green group we get product term—
Q’S’
Summing these product terms we get- Final expression (QS+Q’S’).
POS FORM
1. K-map of 3 variables
K-map 3 variable POS form
F(A,B,C)=?(0,3,6,7)
From red group we find terms
A B
Taking complement of these two
A' B'
Now sum up them
(A' + B')
From brown group we find terms
B C
Taking complement of these two terms
B’ C’
Now sum up them
(B’+C’)
From yellow group we find terms
A' B' C’
Taking complement of these two
A B C
Now sum up them
(A + B + C)
We will take product of these three terms : Final expression –
(A' + B’) (B’ + C’) (A + B + C)
2. K-map of 4 variables
K-map 4 variable POS form
F(A,B,C,D)=?(3,5,7,8,10,11,12,13)
From green group we find terms
C’ D B
Taking their complement and summing them
(C+D’+B’)
From red group we find terms
C D A’
Taking their complement and summing them
(C’+D’+A)
From blue group we find terms
A C’ D’
Taking their complement and summing them
(A’+C+D)
From brown group we find terms
A B’ C
Taking their complement and summing them
(A’+B+C’)
Finally we express these as product –
(C+D’+B’).(C’+D’+A).(A’+C+D).(A’+B+C’)
What are Normal Forms?
Normal Forms are structured representations of logical expressions where
the formula is broken down into a combination of literals (variables or
their negations) connected by logical operators such as AND, OR, and
NOT. These forms help in the simplification and standardization of logical
statements.
Key Concepts:
● Literal: A variable or its negation (e.g., 𝐴 or ¬𝐴).
● Clause: A disjunction of literals (e.g., 𝐴∨¬𝐵).
● Normal Form: A logical formula that follows a specific structure,
such as CNF or DNF.
Types of Normal Forms
Disjunctive Normal Forms (DNF)
A formula which is equivalent to a given formula and which consists of a
sum of elementary products is called a disjunctive normal form of given
formula.
Example : (P ∧ ~ Q) ∨ (Q ∧ R) ∨ (~ P ∧ Q ∧~ R)
The DNF of the formula is not unique.
Conjunctive Normal Form (CNF)
A formula which is equivalent to a given formula and which consists of a
product of elementary sums is called a conjunctive normal form of given
formula.
Example : (P~ ∨ Q) ∧ (Q ∨ R) ∧ (~ P ∨ Q ∨ ~ R)
The CNF of formula is not unique.
If every elementary sum in CNF is tautology, then the given formula is also
tautology.
Properties of Normal and Principal Forms
1. Logical Equivalence:
● Definition: Normal forms are logically equivalent to the original
expression, meaning they produce the same truth values under all
possible interpretations.
● Importance: Ensures that the logical meaning is preserved during
the transformation.
2. Minimality:
● Definition: Principal normal forms aim to use the minimal number
of literals and clauses necessary to represent the logical
expression.
● Importance: Reduces complexity and improves efficiency in
computational processes.
3. Canonical Representation:
● Definition: Principal forms provide a unique representation for a
logical expression, which is especially useful in automated
reasoning and digital logic design.
● Importance: Ensures consistency in logical analysis and
processing.
4. Simplification:
● Definition: Normal forms simplify complex logical expressions,
making them easier to manipulate and analyze.
● Importance: Facilitates logical reasoning, problem-solving, and
optimization.
Conversion to Normal Forms
1. Conversion to CNF:
Steps:
1. Eliminate Bi-conditional and Implication: Convert any bi-conditional (↔)
and implication (→) into their logical equivalents.
● Example: A→B becomes ¬A∨B.
2. Move Negations Inward: Apply De Morgan’s laws to push negations
inside and eliminate double negations.
● Example: ¬(A∧B) becomes ¬A∨¬B.
3. Distribute OR over AND: Apply distributive laws to achieve a
conjunction of disjunctions.
● Example: (A∨(B∧C)) becomes (A∨B)∧(A∨C).
Example: Convert (A→B)∧¬C to CNF: (¬A∨B)∧¬C
2. Conversion to DNF:
Steps:
1. Eliminate Bi-conditional and Implication: Similar to CNF conversion,
start by eliminating any bi-conditional and implication.
● Example: A→B becomes ¬A∨B.
2. Move Negations Inward: Apply De Morgan’s laws to push negations
inside.
● Example: ¬(A∧B) becomes ¬A∨¬B.
3. Distribute AND over OR: Apply distributive laws to achieve a
disjunction of conjunctions.
● Example: (A∧(B∨C)) becomes (A∧B)∨(A∧C).
Example: Convert (A∧¬B)∨(C∧D) to DNF: (A∧¬B)∨(C∧D)
3. Conversion to Principal Forms:
Steps:
1. Simplify the Formula: Reduce the expression by combining like
terms and eliminating redundancies.
2. Apply CNF or DNF Conversion: Convert the simplified formula to
CNF or DNF.
3. Ensure Minimality: Check that the resulting form is minimal in
terms of the number of literals and clauses.
Example:
For the expression A∧(A∨B), the Principal Conjunctive Normal Form is A.
Solved Examples on Normal Forms
Example 1: Convert the expression(A ∨ B) ∧ (¬A ∨ C) to Disjunctive
Normal Form (DNF)
Solution:
Distribute the AND over OR:
(A∨B)∧(¬A∨C)=(A∧¬A)∨(A∧C)∨(B∧¬A)∨(B∧C)
Simplify:
(A∧C)∨(B∧¬A)∨(B∧C)
Final DNF:
(A∧C)∨(B∧¬A)∨(B∧C)
Example 2: Convert the expression (A∧B)∨(¬A∧C) to Conjunctive
Normal Form (CNF).
Solution:
Apply distributive laws to distribute OR over AND:
(A∧B)∨(¬A∧C)=(A∨¬A)∧(A∨C)∧(B∨¬A)∧(B∨C)
Simplify using the tautology
(A∨C)∧(B∨¬A)∧(B∨C)
Final CNF:
(A∨C)∧(B∨¬A)∧(B∨C)
Example 3: Simplify the Boolean function
f(x,y,z)=x∧y∨¬x∧z using the Shannon Expansion Theorem.
Solution:
Apply the theorem to break down the expression:
f(x,y,z)=x∧(y∨z)
Final simplified form: f(x,y,z)=x∧(y∨z)
Well-Formed Formula(WFF) is an expression consisting of
variables(capital letters), parentheses, and connective symbols. An
expression is basically a combination of operands & operators and here
operands and operators are the connective symbols.
Below are the possible Connective Symbols:
1. ¬ (Negation)
2. ∧ (Conjunction)
3. ∨ (Disjunction)
4. ⇒ (Rightwards Arrow)
5. ⇔ (Left-Right Arrow)
Statement Formulas
1. Statements that do not contain any connectives are called Atomic or
Simple statements and these statements in themselves are WFFs.
For example,
P, Q, R, etc.
2. Statements that contain one or more primary statements are called
Molecular or Composite statements.
For example,
If P and Q are two simple statements, then some of the Composite
statements which follow WFF standards can be formed are:
-> ¬P
-> ¬Q
-> (P ∨ Q)
-> (P ∧ Q)
-> (¬P ∨ Q)
-> ((P ∨ Q) ∧ Q)
-> (P ⇒ Q)
-> (P ⇔ Q)
-> ¬(P ∨ Q)
-> ¬(¬P ∨ ¬Q)
Rules of the Well-Formed Formulas
1. A Statement variable standing alone is a Well-Formed
Formula(WFF).
For example– Statements like P, ∼P, Q, ∼Q are themselves Well
Formed Formulas.
2. If ‘P’ is a WFF then ∼P is a formula as well.
3. If P & Q are WFFs, then (P∨Q), (P∧Q), (P⇒Q), (P⇔Q), etc. are
also WFFs.
Example Of Well Formed Formulas:
WFF Explanation
By Rule 1 each Statement by itself is a WFF, ¬P is a
¬¬P
WFF, and let ¬P = Q. So ¬Q will also be a WFF.
By Rule 3 joining ‘(P⇒Q)’ and ‘Q’ with connective
((P⇒Q)⇒Q)
symbol ‘⇒’.
By Rule 3 joining ‘¬Q’ and ‘P’ with connective
(¬Q ∧ P)
symbol ‘∧’.
((¬P∨Q) ∧ By Rule 3 joining ‘(¬P∨Q)’ and ‘¬¬Q’ with
¬¬Q) connective symbol ‘∧’.
¬((¬P∨Q) ∧ By Rule 3 joining ‘(¬P∨Q)’ and ‘¬¬Q’ with
¬¬Q) connective symbol ‘∧’ and then using Rule 2.
Below are the Examples which may seem like a WFF but they are not considered as
Well-Formed Formulas:
1. (P), ‘P’ itself alone is considered as a WFF by Rule 1 but placing
that inside parenthesis is not considered as a WFF by any rule.
2. ¬P ∧ Q, this can be either (¬P∧Q) or ¬(P∧Q) so we have
ambiguity in this statement and hence it will not be considered as
a WFF. Parentheses are mandatory to be included in Composite
Statements.
3. ((P ⇒ Q)), We can say (P⇒Q) is a WFF and let (P⇒Q) = A, now
