Boolean algebra is the
branch of mathematics that includes methods for manipulating logical variables
and logical expressions. Gorge Boole an English mathematician and philosopher
invented the concept of Boolean algebra in 1854. The two distinct logical
values T(True) and F(False) are also represented 1(ON) and 0(OFF). Basic
operations used in Boolean algebra are: AND(.) OR (+) and NOT(-). In Boolean
abgebra no coefficient and power are used A+A=A and A.A=A. It holds both
distributive laws A+(B.C) =(A+B).(A+C) and A.(B+C)=(A.B)+(A.C)
Logic gate: The logic gate is an electronic circuit to
receive more than one input and deliver single output. Gates are often logic
circuits because they can be analyzed with Boolean algebra. The computer system
is a set of gates. The gates are applied in the main memory, ALU, resisters,
etc. Logic gates can be constructed from relays, diode, fluidics and optical
elements.
In digital computer, there are three basic gates, they
are
1. AND
gate
2. OR
gate
3. NOT
gate
There are also other gates made with
basic gates, which are
4. NAND
gate
5. NOR
gate
6. Exclusive
OR( XOR) gate
7. Exclusive
NOR( XNOR) gate
Different types of gates are
AND
gates: - AND gates take two or more inputs and generates single
value as output. It produces true (1) or high output only when all inputs are
true (1) or high otherwise it produces false (0) or off. It is denoted by
dot(.) symbol. It is sometimes called intersection operation.
Algebraic
expression X=A.B
Input
|
output
|
|
A
|
B
|
X=A.B
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
OR gate: - OR
gates take two or more inputs and generates single value as output. It produces
true (1) or high output when any one of the input is true (1) or high otherwise
it produces false (0) or off. It is denoted by plus (+) symbol. It is sometimes
called Union operation.
Algebraic
expression X=A+B
Inputs
|
Outputs
|
|
A
|
B
|
X=A+B
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
NOT gate: -
This is the type of logic gate in which the output will be complement or just
reverse of input. If the input is low
(0) or false, then the output will be high (1) or true and vice versa. It is
denoted by prime (') operator or bar (-) or single quote ('). It is sometimes
called Inverter.
Algebraic expression
X=A'=A
Input
|
output
|
0
|
1
|
1
|
0
|
NAND
gate:-It is the combination of AND and NOT gate i.e. it is
the complement of AND gate. This gate produces low (0) output when all the
inputs are high (1) otherwise the output will be high (1). It uses dot operator (.) and single quote operator(').
Algebraic expression X=(A.B)'
Inputs
|
Output
|
||
A
|
B
|
X=A.B
|
X=(A.B)'
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
NOR
gate: - It is the combination of OR and NOT gate i.e. it is the complement of OR gate. This gate produces high (1)
output when all inputs are low(0) otherwise the output will be low(0). It uses plus operator(+) and single quote operator(').
Algebraic expression X=(A+B)'
Inputs
|
Outputs
|
||
A
|
B
|
X=A+B
|
X=(A+B)'
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
XOR
gate: The exclusive OR gate which produces low (0) or false
output when all the inputs are same otherwise the output will be high (1) or
true. It is also known as even parity generator.
Algebraic expression
X=A'.B+A.B' or X=A ⊕B
Inputs
|
Outputs
|
|||||
A
|
B
|
A'
|
B'
|
A'B
|
AB'
|
X=A'.B+A.B'
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
XNOR
gate: - This exclusive NOR gate produces high (1) or true
output when all the inputs are either low(0) or high(1). It is also known as
odd parity generator.
Algebraic expression
X=A.B+A'.B' or X=(A ⊕B)'
Inputs
|
Outputs
|
|||||
A
|
B
|
A'
|
B'
|
A'B'
|
AB
|
X=A.B+A'.B'
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
De Morgan's Theorem
There are two De Morgan's Theorem for
applying logic gates
1. First
theorem: - "The complement of sum equal to the product of the
complement"
Algebraic
form: (x.y)'=x'+y'
proof:
|
Inputs
|
Output1
|
|
Outputs2
|
|||
|
X
|
Y
|
X+Y
|
(X+Y)'
|
X'
|
Y'
|
X'.Y'
|
|
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
|
Hence
( A+B)'=A'.B'
2. Second
Theorem "The complement of a product is equal to the sum of the
complement"
Algebraic
form: (x.y)'=x'+y'
proof:
|
Inputs
|
Output1
|
|
Output2
|
|||
|
X
|
Y
|
X.Y
|
(X.Y)'
|
X'
|
Y'
|
X'+Y'
|
|
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
|
Different laws Boolean algebra: Some
of the law of Boolean algebra are as follows
a. Commutative
law:The communivate law states that changing the sequence of the variable does
noit have any effect on the output of a logic circuit.
A+B=B+A A.B=B.A
Proof: using truth table
|
A
|
B
|
A+B
|
B+A
|
A.B
|
B.A
|
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
0
|
|
1
|
0
|
1
|
1
|
0
|
0
|
|
1
|
1
|
1
|
1
|
1
|
1
|
Comparing the value of A+B and B+A,
A.B and B.A from trith table, both are equal. Hence Proved.
b. Distributive
law: The distributive law of Boolean algebra state that
A.(B+C)=A.B+A.C ( OR distributive
Law)
A+(B.C)=(A+B).(A+C) ( AND
distrivitive Law)
Proof: using truth table
|
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
|
Comparing value of A.(B+C)=A.B+A.C
from truth table, both are equal. Hence proved.
c. Complement
law: The complement law of Boolean algebra state that
i)A+A'=1
ii)A.A'=0
Proof using truth table
|
A
|
A'
|
A+A'
|
A.A'
|
|
0
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
Hence A+A' =1 and A.A'=0. Hence
Proved
No comments:
Post a Comment