Amity School of Engineering & Technology (CSE)

Module#3
Boolean
Algebra

1
 Amity School of Engineering & Technology (CSE)
Boolean Algebra
Boolean algebra as Lattice:
A lattice is said to be a BA if it is both Distributed and
complemented lattice.
Note: In distributed lattice every element has at most one complement
(means either not exist or only one complement).
And In complemented lattice every element has at least one
complement.

A lattice L is said to be a BA if it has exactly one complement for

each element in L.
Ex:

2
 Amity School of Engineering & Technology (CSE)
Boolean Algebra
Let B is a nonempty set with
 Two binary operator (+) and (*)
 One unary operator ‘ (complement), and
 Two distinct element 0 and 1, then Boolean algebra can be represented
as a 6 tuple 𝑩, +,∗, ’, 𝟎, 𝟏 , where 0 is a least element and 1 is
called a greatest element.
 If the set B satisfy the following properties, then B is called
Boolean algebra:
1.Closure property: 4. Complement law
∀𝒂, 𝒃 ∈ 𝑩 𝒂 + 𝒃 ∈ 𝑩 𝒂 + 𝒂’ = 𝟏
𝒂∗𝒃∈𝑩 𝒂 ∗ 𝒂’ = 𝟎

2. Associative Law: 5. Commutative Law

𝒂 + (𝒃 + 𝒄) = (𝒂 + 𝒃) + 𝒄 a+b=b+a
𝒂∗ 𝒃∗𝒄 = 𝒂∗𝒃 ∗c a∗b=b∗
a
3. Identity Law: Distributive law:
𝒂+𝟎=𝒂 a + (b ∗ c) = (a + b) ∗ (a + c)
𝒂∗𝟏=𝒂 (a ∗ (b + c) = (a ∗ b) + (a ∗ c)
3
 Amity School of Engineering & Technology (CSE)

Point to be remember

1. Boolean algebra is a distributed and

complemented lattice means each element of a
lattice have a unique complement.
2.The representation 𝑩, +,∗, ’, 𝟎, 𝟏 of a set B,
which satisfy the properties (1 to 6) is called a
Boolean algebra.
3.Lattice and Boolean algebra are interconnected
to each other.

4
 Amity School of Engineering & Technology (CSE)

Boolean Algebra
 Boolean algebra is the theoretical foundation for digital system.
 Boolean algebra can have only two values, 0 and 1. The Boolean
0 and 1 do not represent actual numbers, instead a state of a
voltage which is known as the logic level.
 Boolean algebra is used as a tool for the analysis and design of
logic circuit.
 Boolean algebra provides the operations and the rules
for working with the set {0,1}.
 In Boolean algebra, 3 operations are mostly used:
 Boolean Complementation (‘)
 Boolean Sum (+) and
 Boolean Product (.)

5
 Amity School of Engineering & Technology (CSE)

Boolean Algebra
• Both sets and propositions satisfy similar laws, These laws
are used to define an abstract mathematical structure called
a Boolean algebra, which is named after the mathematician
George Boole (1815–1864).
• Let B be a nonempty set with two binary operations + and ∗, a
unary operation ‘ , and two distinct elements 0 and 1. Then B is
called a Boolean algebra if the following axioms hold where a,
b, c are any elements in B:
• We will sometimes designate a Boolean algebra by 6 tuples as
(B,+, ∗,’ ,0, 1), which satisfy the following Properties:

6
 Amity School of Engineering & Technology (CSE)

Boolean Algebra
(B,+, ∗,’ ,0, 1) is a BA, if the following axioms hold where a, b, c are any elements in B.

[B ] Commutative laws:
1 We say
(1a) a + b = b + a  0 is the zero element,
 1, is the unit element, and
(1b) a ∗ b = b ∗ a  a’ is the complement of a.
[B ] Distributive laws:
2

 ‘ has precedence over ∗, and ∗

(2a) a + (b ∗ c) = (a + b) has precedence over +.
∗ (a + c) For example,
(2b)] Identity
a ∗ (b + laws:
c) = (a ∗ b) + (a ∗  a + b ∗ c means
3
a + (b ∗ c) and not (a + b) ∗ c;
c) [B  a ∗ b’ means a ∗ (b’) and not (a ∗ b)’
(3a) a + 0 = a  Of course when a + b ∗ c is written a + bc
then the meaning is clear.
(3b) a ∗ 1 = a
[B ] Complement
4

laws: (4a) a + a =1
7
(4b) a ∗ a= 0
 Amity School of Engineering & Technology (CSE)

Boolean Algebra

Example1: Let B = {0, 1}, the set of bits (binary digits), with the binary
operations of + and ∗ and the unary operation defined by Fig.1. Then B is
a Boolean algebra. (Note simply changes the bit, i.e., 1= 0 and 0= 1.).

8
 Amity School of Engineering & Technology (CSE)
Boolean Algebra- Example

9
 Amity School of Engineering & Technology (CSE)

Example3:
Let 𝐷70 = {1, 2, 5, 7, 10, 14, 35, 70}, the divisors of 70. Define +, ∗,
and on 𝐷70 by a + b = lcm(a, b), a ∗ b = gcd(a, b), a’=70/a
Show that 𝐷70 is a Boolean algebra with 1 as a ‘zero element’ and
70 as a Unit (Greatest) element.

It is clear from these two tables a,b,c ∈ 𝐷70

10
 Amity School of Engineering & Technology (CSE)

Example3:

11
 Amity School of Engineering & Technology (CSE)
Boolean Algebra

12
 Amity School of Engineering & Technology (CSE)
Boolean Algebra

13
 Amity School of Engineering & Technology (CSE)
Boolean Algebra

14
Amity School of Engineering & Technology (CSE)
Note Point

15
 Amity School of Engineering & Technology (CSE)

Proving Theorems of Boolean Algebra

(B,+, ∗,’ ,0, 1) is a BA, if the following axioms hold where a, b, c are any elements in B.
Theorem1: Idempotent law
∀𝒂 ∈ 𝑩
(1) 𝑎 + 𝑎 = 𝑎
(2) 𝑎. 𝑎 = 𝑎
Proof:
(1) LHS

16
 Amity School of Engineering & Technology (CSE)

Properties of Boolean
Algebra

17
 Amity School of Engineering & Technology (CSE)

Properties of Boolean
Algebra
Let 11 and 12 be two multiplicative identity in B, then

18
 Amity School of Engineering & Technology (CSE)

Properties of Boolean
Algebra

19
 Amity School of Engineering & Technology (CSE)

Proving Theorems of Boolean Algebra

Theorem2: Prove that the element 0 (additive identity) and
1(multiplicative identity) are Unique.
Proof:

20
 Amity School of Engineering & Technology (CSE)

Properties of Boolean
Algebra

21
 Amity School of Engineering & Technology (CSE)

Properties of Boolean Algebra

Theorem3:

22
 Amity School of Engineering & Technology (CSE)
Properties of Boolean
Algebra

23
 Amity School of Engineering & Technology (CSE)

Theorem5: De Morgan’s Law

∀a, b ∈ 𝑩
1 𝑎 + 𝑏 ′ = 𝑎 ′ . 𝑏′
2 𝑎. 𝑏 ′ = 𝑎 ′ + 𝑏′
Proof: To prove this, we use the concept A+A’=1 and A.A’=0
For (1) we have show that:
(𝑎 + 𝑏) + 𝑎 ′ . 𝑏′ = 1
LHS (𝑎 + 𝑏 + 𝑎’). (𝑎 + 𝑏 + 𝑏’) = (1 + 𝑏). (1 + 𝑎) = 1.1 = 1=RHS
Also consider
(𝑎 + 𝑏). (𝑎’. 𝑏’) = (𝑎’. 𝑏’). (𝑎 + 𝑏) = (𝑎’. 𝑏’. 𝑎) + (𝑎’. 𝑏’. 𝑏)
= (0. 𝑏’) + (𝑎’. 0) = 0 + 0 = 0

24
 Amity School of Engineering & Technology (CSE)

Theorem6:
0’=1 and 1’=0
Proof: 0’=(a.a’)’=a’+(a’)’=a’+a=1
And
1’=(a+a’)’=a’.(a’)’=a’.a=0

25
 Amity School of Engineering & Technology (CSE)

Atom and Anti-atom

Atom: Immediate successor of least element
Anti-atom: Immediate predecessor of Greatest element.

In fig2,
Atom: 𝑐
Anti-
atom:
𝑎, 𝑏, 𝑔 26
 Amity School of Engineering & Technology (CSE)

Example2:
Consider 𝐷110 . Draw its Hasse diagram and find atoms and anti-
atom.

Atom: 2,5,11
Anti-atom: 10,22,55

27
 Amity School of Engineering & Technology (CSE)

Example3:
Consider 𝐷210 . Draw its Hasse diagram and find atoms and anti-atom.
𝐷210 = {1, 2, 3, 5, 6, 7, 10,14, 15, 21, 30, 35, 42, 70, 105,
210}

Atom: 2,3,5,7
Anti-atom: 30,42,70,105

28
 Amity School of Engineering & Technology (CSE)

Subalgebra:
A Boolean subalgebra, or more simply, a subalgebra, of a Boolean
algebra (B, ≼) is a subset A (i.e 𝐴 ⊆ 𝐵), that contains the Greatest (1)
and Least elements (0) of B , and with any elements 𝑎, 𝑏 ∈ 𝐴 , it
𝑎 ∨ 𝑏, 𝑎 ∧ 𝑏 and 𝑎′ as well.
contains
Note: 1) A itself be a BA, and contains 0 and 1
element Let's consider a subset with
 2 element:
{c,a}, {c,b}….., {c,d}; only {c,d} is a Boolean SA.
 3 element (i.e. odd number of element)
{c,a,d},{c,b,d},{a,d,b},{a,c,b}; odd number of
Element in a subset never will be a Boolean SA in any case, because it itself not
a BA that is one extra element (say in {c,a,d}, a is not having any compliment),
so need not to check 2nd condition, least and greatest element in subset A.
 4 element: {a,b,c,d} is a Boolean subalgebra.
29
 Amity School of Engineering & Technology (CSE)

Subalgebra:
 Any subset A (of B) having odd number of elements, will not be a BSA.
Because there will be at least one element for which complement is not
exist.
Any set having even number of elements may or may not be a BSA.
Example: Find all the Boolean subalgebra of D30.

{1,30}
{ _, _, _ } not a BSA (odd number of element)
{1, _, _, 30} implies {1, 2,15, 30}
{1, 5, 6, 30}
{1, 3, 10, 30}

Total 4 Boolean SA.

30
 Amity School of Engineering & Technology (CSE)

Subalgebra:
Example: Find all the Boolean subalgebra of D30, which are not a Boolean
subalgebra of having at least 4 element.

31
 Amity School of Engineering & Technology (CSE)

Subalgebra

32
 Amity School of Engineering & Technology (CSE)

Subalgebra

33
 Amity School of Engineering & Technology (CSE)

Boolean Subalgebra

34
 Amity School of Engineering & Technology (CSE)

QUIZ time (11.45-12.10 pm)

35