Logic Function and Booleans Algebra

Boolean algebra is algebra of logic. It deals with variables that can have two
discrete values, 0 (False) and 1 (True); and operations that have logical
significance. The earliest method of manipulating symbolic logic was invented by
George Boole and subsequently came to be known as Boolean Algebra.
Rules in Boolean Algebra
Following are the important rules used in Boolean algebra.
 Variable used can have only two values. Binary 1 for HIGH and Binary 0 for
LOW.
 Complement of a variable is represented by an overbar (-). Thus, complement
– . Thus if B = 0 then B
of variable B is represented as B – = 1 and B = 1 then B
–
= 0.
 ORing of the variables is represented by a plus (+) sign between them.
Example: ORing of A, B, C is represented as A + B + C.
 Logical ANDing of the two or more variable is represented by writing a dot
between them such as A.B.C. Sometime the dot may be omitted like ABC.
Difference between Boolean Algebra and Ordinary Algebra:
SN Boolean algebra Ordinary Algebra
1 It is algebra of logic based on binary It is general purpose algebra based on
number system. decimal number system.
2 It is used in the field of digital It is used in the field of mathematics.
Electronics.
3 Basic Operation used in Boolean Basic operation used in ordinary
algebra are: AND, OR and NOT algebra are addition, subtraction,
Operations. multiplication and division.
4 In Boolean algebra there are no Coefficient and power are used in
coefficients or exponents involved. ordinary algebra.
i.e. x + x= x i.e. A + A = 2A
5 It holds both distributive laws: It holds only one distributive law.
SN Boolean algebra Ordinary Algebra
A. (B+C)=(A.B)+(A.C) and A.(B+C)=(A.B)+(A.C)
A+(B.C)=(A+B).(A+C)

Truth Table
A truth table is a tabular representation of all the combinations of values for
inputs and their corresponding outputs. It is a mathematical table that shows all
possible outcomes that would occur from all possible scenarios that are considered
factual, hence the name. Truth tables are usually used for logic problems as in
Boolean algebra and electronic circuits. A truth table shows how a logic circuit's
output responds to various combinations of the inputs, using logic 1 for true and
logic 0 for false. A truth table for two inputs is shown, but it can be extended to
any number of inputs.
Input 1 Input 2 Output
A B A.B
0 0 0
0 1 0
1 0 0
1 1 1

Boolean Expression/Boolean Function/Logic Function

A logic function or Boolean function is an expression formed by binary
variables, binary operators OR, AND, unary operator NOT, parenthesis, and equal
sign. For a given value of the variables, the function can be either 0 or 1.

Basic Operation/Boolean Operation

a) NOT Operation (Complement)
The NOT operation changes one logic level to the opposite logic level. When
input is HIGH (1), the output is LOW (0). When input is LOW (0), the output
is HIGH (1). In either sense, the output is not same as the input. The NOT
 operation is implemented by a logic circuit known as inverter. It is denoted by
symbol prime ('), or bar (-) or tilde (~). The logic operation for NOT operation
is written as Z=A'.

Input Output
A Z=A'
0 1
1 0

Table: Truth table of logical NOT Operation

b) OR Operation
This operation is also called logical addition. The OR operation produces a
HIGH output when any of the input is high or both inputs are HIGH, the
output is LOW when both inputs are LOW. The OR operation is implemented
by a logic circuit known as OR gate. The logical equation for OR operation is
denoted by Z=A+B

Input 1 Input 2 Output

A B Z=A+B
0 0 0
0 1 1
1 0 1
1 1 1

Table: Truth table of logical OR Operation AUB

c) AND Operation
This operation is also called logical Multiplication and is denoted by dot (.).
The AND operation produces a HIGH output when both inputs are HIGH,
the output is LOW when any one or both inputs are LOW. The AND
operation is implemented by a logic circuit known as AND gate.
The logical equation for AND operation is denoted by Z=A.B
 Input 1 Input 2 Output
A B Z=A.B
0 0 0
0 1 0
1 0 0
1 1 1

Table: Truth table of logical AND Operation

Logic Gates
The term gate is used to describe a circuit that performs a basic operation.
Logic gates are basic building block of a computer or any digital electronic system.
Electronic component such as microprocessor is made up millions of logic gates. A
logic gate is an elementary building block of a digital circuit. Most logic gates have
two inputs and one output. At any given moment, every terminal is in one of the two
binary conditions low (0) or high (1), represented by different voltage levels. The
logic state of a terminal can, and generally does, change often, as the circuit
processes data.
Types of logical gates
Basic Gates
a) AND gate b) OR Gate c) NOT Gate
Derived Gate
a) NAND Gate b) NOR Gate
c) Exclusive-OR Gate d) Exclusive-NOR Gate
a) AND Gate
Statement
The AND gate is one of the basic gates that can be combined to form any
basic function. It is an electronic device and can have two or more inputs and
performs what is known as logical multiplication. The AND is composed of
two or more inputs and gives single output, as indicated by the standard
symbols shown in figure below. Inputs are on the left and the output is on the
right in each symbol. Gates with two inputs are shown; however, an AND
gate can have any number of inputs greater than one.
Standard Logic Symbol for the AND gate:

A AND
Z=A.B
B

Logic Expression for an AND Gate

The logical AND function of two variables is represented mathematically
either by placing a dot between the two variables, as A.B or by simply writing
the adjacent letters without the dot, as AB. We will normally use the letter
notation because it is easier to write. If one input variable is A, the other input
variable is B, and the output variable is Z, then the Boolean expression is
Z=A.B OR AB

Truth Table
The logical operation of gate can be expressed with a truth table that lists all
input combinations with the corresponding outputs. The truth table can be
expanded to any number of inputs. The AND gate produces output 1 when all
inputs are 1, and 0 when any input is 0.

Input 1 Input 2 Output

A B Z=A.B
0 0 0
0 1 0
1 0 0
1 1 1

b) OR gate
Statement
The OR gate is another of the basic gates that can be combined to form any
basic function. It is an electronic device and can have two or more inputs and
 performs what is known as logical addition. The OR is composed of two or
more inputs and single output, as indicated by the standard symbols shown in
figure below. Inputs are on the left and the output is on the right in each
symbol. Gates with two inputs are shown; however, an OR gate can have any
number of inputs greater than one.
Standard Logic symbol for the OR gate:

Logic Expression for an OR Gate

The logical OR function of two variables is represented mathematically by
placing + between the two variables. If one input variable is A, the other input
variable is B, and the output variable is Z, then the Boolean expression is
Z=A+B.
Truth Table
The logical operation of gate can be expressed with a truth table that lists all
input combinations with the corresponding outputs. The truth table can be
expanded to any number of inputs. The OR gate produces output 1 when all
inputs are 1 or any one input is 1, and 0 when all inputs are 0.
Input 1 Input 2 Output
A B Z=A+B
0 0 0
0 1 1
1 0 1
1 1 1

c) NOT Gate
Statement
The Not gate is an electronic device with one input and one output. It is also
called an Inverter. The inverter (NOT circuit) performs the operation called
 inversion or complementation. The inverter changes one logic level to the
opposite level. In terms of bits, it changes 1 to 0 and 0 to 1.
Standard Logic symbol for the NOT gate:

inverter
A Z=A'
Logic Expression for an NOT Gate
In Boolean algebra, which is the mathematics of logic circuits a variable is
designated by a letter. The complement of a variable is designated by a bar
over the letter. A variable can take on a value of either 1 or 0. If a given
variable is 1, its complement is 0 and vice versa. If the input variable is called
A and the output variable is called Z, then Z = A'.
This expression states that the output is the complement of the input, so if A=0,
then Z=1, and if A=1, then Z=0. The complemented variable A can be read as
"A bar" or "not A".
Truth Table
Input Output
A Z = A'
1 0
0 1

d) The NAND Gate

Statement
The NAND gate is an electronic circuit and has two or more than two inputs to
produce single output. It is popular logic element because it can be used as a
universal gate; that is, NAND gates can be used in combination to perform the
AND, OR, and inverter operations.
The term NAND gate is contraction of AND-NOT and implies an AND
function with a complemented (inverted) output. i.e. AND + NOT =NAND.
Standard Logic symbol for the NAND Gate:
 A NAND
Z=(A.B)'
B
Logic Expression for a NAND Gate
The Boolean expression for the output of a 2-input NAND gate is Z= AB or
(A.B)'
This expression says that the two input variables, A and B, are first ANDed
and then complemented, as indicated by the bar over the AND expression.
The NAND expression can be extended to more than two input variables by
including additional letters to represent the other variables.
Truth Table
Input 1 Input 2 Output
A B Z= (A.B)'
0 0 1
0 1 1
1 0 1
1 1 0

e) NOR gate
Statement
The NOR gate is an electronic circuit and has two or more than two inputs to
produce single output. It is popular logic element because it can be used as a
universal gate; that is, NAND gates can be used in combination to perform the
AND, OR, and inverter operations.
The term NOR gate is contraction of NOT-OR and implies an OR function with a
complemented (Inverted) output. i.e. NOT+OR=NOR

Standard Logic symbol for the NOR gate:

A NOR
Z=(A+B)'
B
 Logic Expression for a NOR Gate
The Boolean expression for the output of a 2-input NOR gate is Z= (A+B)'
This expression says that the two input variables, A and B, are first ORed
and then complemented, as indicated by the bar over the OR expression.
The NOR expression can be extended to more than two input variables by
including additional letters to represent the other variables.
Truth Table
Input 1 Input 2 Output
A B Z= (A+B)'
0 0 1
0 1 0
1 0 0
1 1 0

Difference between NAND gate and NOR gate:

SN NAND gate NOR gate

1 It is the combination of AND and It is the combination of OR and NOT
NOT gates. Gates.
2 It's output value is just complement of It's output value is just complement of
output value of AND gate. output value of OR gate.
3 The output value of NAND gate is 0 The output value of NOR gate is 1
only when all combination of inputs only when all combination of inputs
are 1 otherwise output value is 1. are 0 otherwise output value is 0.
4 Algebraic expression: If A and B are Algebraic expression: If A and B are
two input signals, then it is two input signals, then it is
represented by Z=(A.B)'. represented by Z=(A+B)'.
5 Graphical Symbol Graphical Symbol
A NAND A NOR
Z=(A.B)' Z=(A+B)'
B B
f) Exclusive – OR Gate (X-OR Gate)
Statement
It is an electronic circuit. Exclusive-OR gate is formed by a combination of
other gates. However, because of their fundamental importance in many
applications, these gates are often treated as basic logic elements with their
own unique symbols.
The XOR (exclusive-OR) gate acts in the same way as the logical "either/or."
The output is "true" if either, but not both, of the inputs are "true." The output
is "false" if both inputs are "false" or if both inputs are "true." Another way of
looking at this circuit is to observe that the output is 1 if the inputs are
different, but 0 if the inputs are the same. It is denoted by . The X-OR gate
has only two inputs.
Standard Logic symbol for the X-OR Gate:

A XOR
Z=(A B)
B
Logic Expression for a X-OR Gate
The Boolean expression for X-OR gate is given by Z=A B OR A'.B + A.B'
Truth Table

Input 1 Input 2 Output

A B Z =A'.B+A.B'
0 0 0
0 1 1
1 0 1
1 1 0

g) Exclusive-NOR Gate (X-NOR Gate)

Statement
It is an electronic circuit. Exclusive-NOR gate is formed by a combination of
other gates. However, because of their fundamental importance in many
 applications, these gates are often treated as basic logic elements with their
own unique symbols.
The X-NOR (exclusive-NOR) gate is a combination XOR gate followed by
an inverter. Its output is "true" if the inputs are the same, and "false" if the
inputs are different.
Standard Logic symbol for the X-NOR Gate
Like the X-OR gate, X-NOR has only two inputs. The bubble on the output of
the X-NOR gate indicates that its output is opposite that of the X-OR gate. It
is denoted by Z=A B or A.B+A'.B'.

A XNOR
Z=(A B)
B
Logic Expression for a X-NOR Gate
The Boolean expression for X-NOR gate is given by Z=A B or A.B + A'.B'.
Truth Table

Input 1 Input 2 Output

A B Z = A.B+A'.B'
0 0 1
0 1 0
1 0 0
1 1 1

Difference between X-OR gate and X-NOR gate

SN X-OR gate X-NOR gate
1 It's denoted by . It's denoted by .
2 It is equivalent to odd parity gate It is equivalent to even parity gate
3 If both inputs are same then output is If both inputs are same then output is
0 otherwise 1 1 otherwise 0
4 Algebraic expression: If a and b are Algebraic expression: If a and b are
two input signals, then it is two input signals, then it is
 represented by Z = A'.B+A.B' represented by Z= A.B+A'.B'
5 Graphical Symbol Graphical Symbol
A XOR A XNOR
Z=(A B) Z=(A B)
B B

Universal Gate
NAND and NOR Gates are called Universal Gates because all the other gates
can be created by using these gates. it's possible to create all other logic gates like
AND, OR, NOT etc. and you can design any logic circuit. They are mostly
applicable in logic circuits. They are easy to implement compare to other gates.
AND, NOT and OR gates are the basic gates; we can create any logic gate or
any Boolean expression by combining them. NOR and NAND gates have the
particular property that any one of them can create any logical Boolean expression
if designed in a proper way. Now we will look at the operation of each gate
separately as universal gates. NAND and NOR gates are known as universal as
gates.
NAND gate as a Universal Logic Gate
The NAND gate is universal gate because it can be used to produce the NOT,
the AND, the OR functions. To prove that any Boolean function can be
implemented using only NAND gates, we will show that the AND, OR, and NOT
operations can be performed using only these gates. An inverter can be made from
a NAND gate by connecting all of the inputs together and creating, in effect, a
single input, in figure below for 2-input gate.
We will consider the truth table of the above NAND gate i.e. a two-input gate.
The two inputs are A and B.
Graphical Symbol of NAND Gate
A
A.B
B

Truth Table

Inputs Outputs
 A B ——
X=A .B
0 0 1
0 1 1
1 0 1
1 1 0

Implementing an Inverter Using only NAND Gate

The figure shows two ways in which a NAND gate can be used as an inverter
(NOT gate).
All NAND input pins connect to the input signal A gives an output A'.

Implementing AND Using only NAND Gates

An AND gate can be replaced by NAND gates as shown in the figure (The
AND is replaced by a NAND gate with its output complemented by a NAND gate
inverter).

Implementing OR Using only NAND Gates

An OR gate can be replaced by NAND gates as shown in the figure (The OR
gate is replaced by a NAND gate with all its inputs complemented by NAND gate
inverter).
 Thus, the NAND gate is a universal gate since it can implement the AND, OR
and NOT functions.
NOR gate as a Universal Logic Gate
To prove that any Boolean function can be implemented using only NOR
gates, we will show that the AND, OR, and NOT operations can be performed
using only these gates.
Implementing an Inverter Using only NOR Gate
The figure shows two ways in which a NOR gate can be used as an inverter
(NOT gate).
All NOR input pins connect to the input signal A gives an output A'.

Implementing OR Using only NOR Gates

An OR gate can be replaced by NOR gates as shown in the figure (The OR is
replaced by a NOR gate with its output complemented by a NOR gate inverter)

Implementing AND Using only NOR Gates

An AND gate can be replaced by NOR gates as shown in the figure (The
AND gate is replaced by a NOR gate with all its inputs complemented by NOR
gate inverters)

Thus, the NOR gate is a universal gate since it can implement the AND, OR
and NOT functions.
4.4 Duality principle
Principle of Duality is based on the Boolean algebra and concepts of boolean
algebra.
In Boolean algebra there is a precise duality between the operators . (AND)
and + (OR) and the digits 0 and 1. One part may be obtained from the other if the
binary operators and the identity elements are interchanged. This important
property Boolean algebra is called the duality principle. If the dual of an algebraic
expression is desired, we simply interchange OR (+) with AND (.) and AND (.)
with OR (+) operators and replace 1's by 0's and 0's by 1's. But variables and
complements are left unchanged.
Rules of Duality Principle
Dual of an algebraic expression is obtained from following concept:
a) Replacing AND(.) operation by OR (+) operation
b) Replacing OR(+) operation with AND(.) operation
c) All 1's are changed to 0 and All 0's are changed to 1
d) All variables and Complements are left Unchanged
Example: For the given expression
B.1 is B+0,
(A'.0).(1+A) is (A'+1)+(0.A) i.e. (A'+1)
xy(y+y'z)+x'z is (x+y)+(y.(y'+z).(x'+z))
Complement of Boolean Expression
Complement of Boolean Expression is obtained from following concept:
a) Replacing AND operation by OR operation
b) Replacing OR operation with AND operation
c) All 1's are changed to 0 and All 0's are changed to 1
d) All variables are complemented
Example: AB'+A'C
= (AB'+A'C)'
= (AB')'.(A'C)'
= (A'+B).(A+C')
4.5 Laws of Boolean algebra – Associative, Commutative, Distributive,
Identity, and Complement Laws
Boolean algebra is a different kind of algebra or rather can be said a new kind
of algebra which was invented by world famous mathematician George Boole in
the year of 1854. In digital electronics there are several methods of simplifying the
design of logic circuits. This algebra is one of these methods. According to George
Boole symbols can be used to represent the structure of logical thoughts. This type
of algebra deals with the rules or laws, which are known as laws of Boolean
algebra by which the logical operations are carried out.
The main aim of any logic design is to simplify the logic as much as possible
so that the final implementation will become easy. In order to simplify the logic,
the Boolean equations and expressions representing that logic must be simplified.
So, to simplify the Boolean equations and expression, there are some laws and
theorems proposed. Using these laws and theorems, it becomes very easy to
simplify or reduce the logical complexities of any Boolean expression or function.
Basic Laws and Proofs
The basic rules and laws of Boolean algebraic system are known as "Laws of
Boolean algebra". The variables used in Boolean Algebra only have one of two
possible values, a logic "0" and a logic "1" but an expression can have an infinite
number of variables all labelled individually to represent inputs to the expression.
Example: Variables A, B, C etc, giving us a logical expression of A + B = C,
but each variable can only be 0 or 1.
Laws (rules) of the Boolean algebra
i. Commutative law ii. Associative Law
iii. Distributive law iv. Identity Law
v. Complement Law
1. Commutative Law
Commutative Law of Addition :
It states that the sum of two variable A and B is equals to the sum of B and
A.
i.e. A + B = B + A
Graphical Symbol:

Truth table

Inputs Output1 Output2

A B A+B B+A
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 1
Conclusion: Comparing the values of output 1 and output 2 from above truth
table both are equal hence proved.

Commutative Law of Multiplication :

It states that the product of two variable A and B is equals to the Product of B
and A. i.e. A . B = B . A
Graphical Symbol:

Truth table
Inputs Output1 Output2
A B AB BA
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
 Conclusion: Comparing the values of output 1 and output 2 from above truth
table both are equal hence proved.
2. Associative Law
Associative Law of Addition:
Associative law of addition states that ORing more than two variables i.e.
mathematical addition operation performed on variables will return the same
value irrespective of the grouping of variables in an equation. It involves in
swapping of variables in groups.
i.e. A + (B + C) = (A + B) + C
Graphical Symbol:

=
(A+B)+C

Truth table
Inputs Output 1 Output 2
A B C B+C A + (B + A+B (A+B)+C
C)
0 0 0 0 0 0 0
0 0 1 1 0 0 0
0 1 0 1 0 1 0
0 1 1 1 0 1 0
1 0 0 0 0 1 0
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
Conclusion: Comparing the values of output 1 and output 2 from above truth
table both are equal hence proved.

Associative Law of Multiplication:

 Associative law of multiplication states that ANDing more than two variables
i.e. mathematical multiplication operation performed on variables will return
the same value irrespective of the grouping of variables in an equation.
i.e. A.(B.C) = (A.B).C
Graphical Symbol

Truth table
Inputs Output1 Output2
A B C BC A(BC) AB (AB)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 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 0 1 0
1 1 1 1 1 1 1
Conclusion: Comparing the values of output 1 and output 2 from above truth
table both are equal hence proved.
3. Distributive law
This is the most used and most important law in Boolean algebra, which
involves in 2 operators: AND and OR.

Distributive law for OR operator:

The multiplication of two variables and adding the result with a variable will
result in same value as multiplication of addition of the variable with
individual variables.
In other words, ANDing two variables and ORing the result with another
variable is equal to AND of ORing of the variable with the two individual
variables.
i.e. A + (B.C) = (A + B).(A + C)
Graphical Symbol

Truth table
Inputs Output1 Output2
A B C B+C A.(B+C) A.B A.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 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
Conclusion: Comparing the values of output 1 and output 2 from above truth
table both are equal hence proved.

Distributive law for AND operator:

The addition of two variables and multiplying the result with a variable will
result in same value as addition of multiplication of the variable with
individual variables.
In other words, ORing two variables and ANDing the result with another
variable is equal to OR of ANDing of the variable with the two individual
variables.
 Distributive law can be written as
A.(B+C) = (A.B) + (A.C)
Graphical Symbol

Truth table
Inputs Output1 Output2
A B C BC A+(BC) A+B A+C (A+B)(A+C)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 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
Conclusion: Comparing the values of output 1 and output 2 from above truth
table both are equal hence proved.
4. Identity law
The first Boolean identity is that the sum of anything and zero is the same as
the original "anything." This identity is no different from its real-number
algebraic equivalent:
 i) A + 0 = A
Graphical Symbol

Truth Table
Inputs Output i.e.
A 0 A+0 A
0 0 0 0
1 0 1 1
The next identity is most definitely different from any seen in normal
algebra. Here we discover that the sum of anything and one is one:
ii) A+1=1
Graphical Symbol

Truth Table

Inputs Output i.e.

A 1 A+1 1
0 1 1 1
1 1 1 1
5. Complement law
i) A+A'=1
Graphical Symbol

Truth Table

Input Output
A A' A+A'
 0 1 1
1 0 1
ii) A. A'=0
Graphical Symbol

Truth Table
Input Output
A A' A.A'
0 1 0
1 0 0
Boolean Expression for a logic Circuit
Boolean algebra provides a concise way to express the operation of a logic
circuit formed by a combination of logic gates so that the output can be determined
for various combinations of input values. A Boolean expression is a logical
statement that is either TRUE or FALSE. A Boolean expression always produces a
Boolean value.
Boolean Expression may be formed by the combinations of Boolean variables,
constants, and logical operators.
To derive the Boolean expression for a given logic circuit, begin at the left-
most inputs and work toward the final output, writing the expression for each gate.
Each Boolean expression represents a Boolean function.
Example: AB′C is a Boolean expression.
Logic Diagram
A logic diagram uses the pictorial description of logic gates in combination to
represent a logic expression. An example below shows a logic diagram with three
inputs (A, B, and C) and one output (Y). The interpretation of this will become
clear in the following sections.
 —
AB

— —
AB B C

—
C
Boolean algebra can be used to write a logic expression in equation form.
Below is an example Boolean expression. In fact, it represents the same logic
as the example logic circuit diagram above. This concept will also become clearer
when we cover converting from and to the Boolean expression below.
— ) B—
Y = (AB C
Example 1:
Construct a Truth Table for the logical functions at points C, D and Q in the
following circuit and identify a single logic gate that can be used to replace the
whole circuit.

First observations tell us that the circuit consists of a 2-input NAND gate, a 2-
inputEX-OR gate and finally a 2-input EX-NOR gate at the output. As there are
only 2 inputs to the circuit labelled A and B, there can only be 4 possible
combinations of the input ( 22 ) and these are: 0-0, 0-1, 1-0 and finally 1-1. Plotting
the logical functions from each gate in tabular form will give us the following truth
table for the whole of the logic circuit below.
Inputs Output
A B C D Q
0 0 1 0 0
0 1 1 1 1
1 0 1 1 1
1 1 0 0 1
Example 2:
Find the Boolean algebra expression for the following system.

The system consists of an AND Gate, a NOR Gate and finally an OR Gate.
The expression for the AND gate is A.B, and the expression for the NOR gate is
A+B . Both these expressions are also separate inputs to the OR gate which is
defined as A+B. Thus the final output expression is given as:

The output of the system is given as Q = (A.B) + (A+B)

Inputs Intermediates Output

B A A.B A+B Q
0 0 0 1 1
0 1 0 0 0
1 0 0 0 0
1 1 1 0 1
Boolean Algebra Example 3:
Find the Boolean algebra expression for the following system.

This system may look more complicated than the other two to analyze but
again, the logic circuit just consists of simple AND, OR and NOT gates connected
together.
As with the previous Boolean examples, we can simplify the circuit by
writing down the Boolean notation for each logic gate function in turn in order to
give us a final expression for the output at Q.

Inputs Intermediates Output

C B A A.B.C B C B+C A.(B+C) Q
0 0 0 0 1 1 1 0 0
0 0 1 0 1 1 1 1 1
0 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 1 1
1 0 0 0 1 0 1 0 0
1 0 1 0 1 0 1 1 1
1 1 0 0 0 0 0 0 0
 1 1 1 1 0 0 0 0 1
Simplify: C + BC:
= C + BC Original Expression
= C (1+B)
= C.1
=C
Simplify: (AB)'(A' + B)(B' + B):
= (AB)'(A' + B) Complement law, Identity law.
= (A' + B')(A' + B) DeMorgan's Law
= A' + B'B Distributive law.
A' Complement, Identity
Simplify: (A+B)(A+C)
= AA + AC + AB + BC
= A + AC +AB + BC
= A(1+C+B) + BC
= A.1 + BC
= A + BC

Simplify: (—
A + B)(A + B)
=— AA + —
A B + AB + BB
=0+—A B +AB + B
=—
A B + AB + B
= B(—
A + A) + B
= B+B
=B

4.6 De-Morgan's Theorem: Statement and logic Expression

De Morgan, a mathematician who knew Boole, proposed two theorems that
are an important part of Boolean algebra. De Morgan's Theorems are two
additional simplification techniques that can be used to simplify Boolean
expressions. Again, the simpler the Boolean expression the simpler the resulting
the Boolean expression, the simpler the resulting logic.
The complement of any Boolean expression can be formed by successively
applying the theorem is known as De Morgan theorem. There are two De Morgan's
theorems for Boolean algebra. They are stated as:
Theorem 1:
The complement of a sum of variables is equal to the product of the
complements of the individual variables.
i.e. (A+B)' = A'.B'
Graphical Symbol

Truth table
A B A' B' A+B (A+B)' A'.B '
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0
Conclusion: Comparing the output of (A+B)' is equals to the output of A'.B'.
Hence, proved.
Theorem 2:
The complement of a product of variables is equal to the sum of the
complement of individual variables.
i.e. (A .B) ' = A'+B'
Graphical Symbol

Truth table
 A B A' B' A.B (A.B)' A'+B'
0 0 1 1 0 1 1
0 1 1 0 0 1 1
1 0 0 1 0 1 1
1 1 0 0 1 0 0
Conclusion: Comparing the output of (A.B)' is equals to the output of A'+B'.
Hence, proved.

4.7 Venn diagram and its representation of logic gates

A Venn diagram is constructed with a collection of simple closed curves as
circle drawn in a plane. Venn diagram normally comprises overlapping circles. It
is a diagram represents a set or sets and logical relationship between them. The sets
are drawn as circle.
The Venn diagram for different gates is given below: