Boolean Algebras And Switching Circuits

Boolean Algebra Dr Amber Habib Mathematical Sciences Foundation St. Stephen’s College Delhi 110007

Algebra of Sets 1 Fix a set X and consider the behaviour of its subsets relative to the operations of union (∪), intersection (∩). For every A, B, C ⊂ X, we have:

• Idempotent Law: A ∪ A = A ∩ A = A.

• Commutative Law: A ∪ B = B ∪ A,

A ∩ B = B ∩ A.

• Associative Law: A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C

• Distributive Law: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 1

Algebra of Sets 2 Moreover, there are two special subsets: ∅ and X. Relative to these, the operations obey:

• A ∪ ∅ = A, A ∩ ∅ = ∅.

• A ∪ X = X, A ∩ X = A.

In particular ∅ serves as identity for ∪, while X does the same for ∩. Finally, we have the operation of complementation: Every A ⊂ X has a unique complement A0 (with respect to X), and • A ∪ A0 = X, A ∩ A0 = ∅.

2

Algebra of Logic 1 Now we consider propositional calculus. We let ∨ stand for ‘or’ and ∧ stand for ‘and’. Then for all statements A, B, C, we have:

• Idempotent Law: A ∨ A = A ∧ A = A.

• Commutative Law: A ∨ B = B ∨ A,

A ∧ B = B ∧ A.

• Associative Law: A ∨ (B ∨ C) = (A ∨ B) ∨ C A ∧ (B ∧ C) = (A ∧ B) ∧ C

• Distributive Law: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) 3

Algebra of Logic 2 We write T for the statement which is necessarily true and F for the one which is necessarily false. Relative to these, the operations obey:

• A ∨ F = A, A ∧ F = F .

• A ∨ T = T , A ∧ T = A.

In particular F serves as identity for ∨, while T does the same for X. Finally, we have the operation of negation: Every statement A has a unique negation ¬A, and

• A ∨ ¬A = T , A ∧ ¬A = F . 4

Boolean Algebras An abstract Boolean Algebra is a set B with

• Two binary operations ∨ (“join”)and ∧ (“meet”),

• Two special elements denoted 0 (“zero”) and 1 (“unity”),

• An operation 0 (“complement”),

such that for all a, b, c ∈ B we have:

5

Laws of Boolean Algebra • Idempotent Law: a ∨ a = a ∧ a = a. • Commutative Law: a ∨ b = b ∨ a,

a ∧ b = b ∧ a.

• Associative Law: a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c • Distributive Law: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) • a ∨ 0 = a, a ∧ 0 = 0. • a ∨ 1 = 1, a ∧ 1 = a. • a ∨ a0 = 1, a ∧ a0 = 0. 6

The Simplest Example Let B = {0, 1}. Define

• 0∧0=0∨0= 1∧1=1∨1=

• 0∧1= 0∨1= • 00 = 10 =

7

The Simplest Example Let B = {0, 1}. Define

• 0 ∧ 0 = 0 ∨ 0 = 0, 1 ∧ 1 = 1 ∨ 1 = 1.

• 0∧1= 0∨1= • 00 = 10 =

8

The Simplest Example Let B = {0, 1}. Define

• 0 ∧ 0 = 0 ∨ 0 = 0, 1 ∧ 1 = 1 ∨ 1 = 1.

• 0 ∧ 1 = 0, 0 ∨ 1 = 1. • 00 = 10 =

9

The Simplest Example Let B = {0, 1}. Define

• 0 ∧ 0 = 0 ∨ 0 = 0, 1 ∧ 1 = 1 ∨ 1 = 1.

• 0 ∧ 1 = 0, 0 ∨ 1 = 1. • 00 = 1, 10 = 0.

10

The Simplest Example 2 The previous example could also be obtained as follows: Let B consist of the subsets of a singleton set X = {x}. Let ∨ = ∪, ∧ = ∩, and 0 stand for complement. Define

• 0=∅

• 1=X

Then the rules for combining 0, 1 are exactly as on the previous slide.

11

Absorption Law Let B be a Boolean algebra. If a, b ∈ B, then a ∧ (a ∨ b) = a ∨ (a ∧ b) = a.

12

Absorption Law Let B be a Boolean algebra. If a, b ∈ B, then a ∧ (a ∨ b) = a ∨ (a ∧ b) = a. Proof. First, by Distributive Law, a ∧ (a ∨ b) = (a ∧ a) ∨ (a ∧ b) = a ∨ (a ∧ b).

13

Absorption Law Let B be a Boolean algebra. If a, b ∈ B, then a ∧ (a ∨ b) = a ∨ (a ∧ b) = a. Proof. First, by Distributive Law, a ∧ (a ∨ b) = (a ∧ a) ∨ (a ∧ b) = a ∨ (a ∧ b). Then, a ∧ (a ∨ b) = [a ∧ (a ∨ b)] ∨ [b ∧ b0]

14

Absorption Law Let B be a Boolean algebra. If a, b ∈ B, then a ∧ (a ∨ b) = a ∨ (a ∧ b) = a. Proof. First, by Distributive Law, a ∧ (a ∨ b) = (a ∧ a) ∨ (a ∧ b) = a ∨ (a ∧ b). Then, a ∧ (a ∨ b) = [a ∧ (a ∨ b)] ∨ [b ∧ b0] = (a ∨ b) ∧ (a ∨ b0) ∧ (a ∨ b ∨ b) ∧(a ∨ b ∨ b0)

15

Absorption Law Let B be a Boolean algebra. If a, b ∈ B, then a ∧ (a ∨ b) = a ∨ (a ∧ b) = a. Proof. First, by Distributive Law, a ∧ (a ∨ b) = (a ∧ a) ∨ (a ∧ b) = a ∨ (a ∧ b). Then, a ∧ (a ∨ b) = [a ∧ (a ∨ b)] ∨ [b ∧ b0] = (a ∨ b) ∧ (a ∨ b0) ∧ (a ∨ b ∨ b) ∧(a ∨ b ∨ b0) = (a ∨ b) ∧ (a ∨ b0) ∧ 1 = (a ∨ b) ∧ (a ∨ b0) = a ∨ (b ∧ b0) = a ∨ 1 = a.

16

Cancellation Law Let B be a Boolean algebra. Suppose there are a, b, c ∈ B such that a∨b = a∨c a ∧ b = a ∧ c. Then b = c.

17

Cancellation Law Let B be a Boolean algebra. Suppose there are a, b, c ∈ B such that a∨b = a∨c a ∧ b = a ∧ c. Then b = c. Proof. Law:

We repeatedly use the Absorption

b = b ∧ (a ∨ b)

18

Cancellation Law Let B be a Boolean algebra. Suppose there are a, b, c ∈ B such that a∨b = a∨c a ∧ b = a ∧ c. Then b = c. Proof. Law:

We repeatedly use the Absorption

b = b ∧ (a ∨ b) = b ∧ (a ∨ c) = (a ∧ b) ∨ (b ∧ c) = (a ∧ c) ∨ (b ∧ c) = c ∧ (a ∨ b) = c ∧ (a ∨ c) = c.

19

Uniqueness of Complement Let B be a Boolean algebra. Suppose a, b ∈ B such that a∨b = 1 a ∧ b = 0. Then b = a0.

20

Uniqueness of Complement Let B be a Boolean algebra. Suppose a, b ∈ B such that a∨b = 1 a ∧ b = 0. Then b = a0. Proof. We have a ∨ b = a ∨ a0 = 1 a ∧ b = a ∧ a0 = 0. Hence, by the Cancellation Law, b = a0. Corollary: a00 = a. Corollary: 00 = 1, 10 = 0.

21

De Morgan’s Laws Let B be a Boolean algebra and a, b ∈ B. Then

• (a ∨ b)0 = a0 ∧ b0. • (a ∧ b)0 = a0 ∨ b0.

22

De Morgan’s Laws Let B be a Boolean algebra and a, b ∈ B. Then

• (a ∨ b)0 = a0 ∧ b0. • (a ∧ b)0 = a0 ∨ b0. Proof. Let c = (a ∨ b)0. Then (a ∨ b) ∧ (a0 ∧ b0) = (a ∧ a0 ∧ b0) ∨ (b ∧ a0 ∧ b0) = 0 ∨ 0 = 0, (a ∨ b) ∨ (a0 ∧ b0) = (a ∨ b ∨ a0) ∧ (a ∨ b ∨ b0) = 1 ∧ 1 = 1.

23

Switching Circuits 1 Our aim is to study circuits such as the following: a b | | b0 | a | a • Each mark, such as represents a | switch (in this case, named a). • Each switch has two states, “on” and “off” (or 1 and 0). • If two switches always have the same state, we consider them to be the same. In particular, they have the same name. • If two switches always have opposite states, we call one the complement of the other, and denote it by a 0 (e.g. b and b0). 24

Switching Circuits 2 a |

b | b0 | a |

The specific question is: How do the states of the individual switches affect the state of the entire circuit? Or, which combinations of states of individual switches lead to the entire circuit being “on” (current can pass from one end to the other) or “off” (current cannot pass). In the above example, the circuit is on exactly when a is on, and b is off. Hence we could just as well use the simpler circuit a |

b0 | 25

Series Connection a |

b |

a∧b

Parallel Connection a | a∨b b |

26

Series Connection a |

b |

a∧b

Parallel Connection a | a∨b b | A Series-Parallel Circuit a |

b | b0 | a |

27

Series Connection a |

b |

a∧b

Parallel Connection a | a∨b b | A Series-Parallel Circuit a |

b | b0 | a |

((a ∧ b) ∨ a) ∧ b0 28

Series-Parallel Circuits Not only switches, but circuits can be placed in series or parallel connections. Suppose we have circuits A and B, which we denote by:

A

B

We can connect them in series:

A

B

A∧B

Or in parallel:

A A∨B B 29

The Algebra of Switching Circuits 1 Consider two circuits A and B made from switches a, b, c, . . . . We consider them equal if for any choice of states of a, b, c, . . . , A and B have the same state. We have defined two operations ∧ and ∨ on the set of switching circuits. We have the following identities for these operations: • Idempotent Law: A ∨ A = A ∧ A = A. A A

A

=

=

A

A • Commutative Law: A ∨ B = B ∨ A,

A ∧ B = B ∧ A.

• Associative Law: A ∨ (B ∨ C) = (A ∨ B) ∨ C A ∧ (B ∧ C) = (A ∧ B) ∧ C 30

The Algebra of Switching Circuits 2 Distributive Law

• A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) B |

A |

C |

=

A |

B |

A |

C |

• A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) A | B |

C |

=

A |

A |

B |

C |

31

The Algebra of Switching Circuits 3 Zero, Unity, Complements We introduce two special switches: • The switch named 1 is always on. • The switch named 0 is always off. It is easy to see that for any circuit A, • A ∨ 0 = A, A ∧ 0 = 0. • A ∨ 1 = 1, A ∧ 1 = A. Two circuits are termed complementary if they are always in opposite states, and we then name them A and A0. We have • A ∨ A0 = 1 • A ∧ A0 = 0 32

The Boolean Algebra of Switching Circuits The previous few slides show that switching circuits follow the rules of Boolean algebra. This enables us to develop systematic methods for analyzing them, especially for replacing circuits by smaller ones with the same behaviour. For instance, consider the equality a |

b | b0 |

=

a |

b0 |

a | This can be derived by algebra: ((a ∧ b) ∨ a) ∧ b0 = a ∧ b0, by the Absorption Law.

33

Switching Circuits and Truth-Tables Recall that truth-tables are a useful way of exploring the structure of logic. Since switching circuits have the same algebraic structure, we can expect a similar role for truthtables in this context. For instance, the circuit given by the expression a ∧ b0 has the table:

ab 0 1

0 0 1

1 0 0

or

a 0 0 1 1

b 0 1 1 0

a ∧ b0 0 0 0 1

Similarly, the circuit (a ∧ b) ∨ (a0 ∧ b0) has the table:

ab 0 1

0 1 0

1 0 1

or

a 0 0 1 1

b 0 1 1 0

a ∧ b0 1 0 1 0 34

Karnaugh Maps Given a switching circuit, we can generate its table in a mechanical way. Conversely, given its table, we can generate the Boolean expression corresponding to the circuit. Karnaugh maps are a way of using the table to generate a simple or efficient expression for the circuit.

35

Karnaugh Maps For Two Switches We start by looking at some possibilities for a circuit involving two switches a and b: a0 ∧ b0 ab 0 1 0 1 0 1 0 0

a ∧ b0 ab 0 1 0 0 0 1 1 0

a

b0

ab 0 1

0 0 1

1 0 1

(a0 ∧ b0) ∨ (a ∧ b) ab 0 1 0 1 0 1 0 1

ab 0 1

1 0 0

a0 ∨ b0 ab 0 1 0 1 1 1 1 0 0

1 ab 0 1

0 1 1

0 1 1

1 1 1

ab 0 1

0 0 0

1 0 0 36

Karnaugh Maps For Two Switches 2 From the tables on the last slide, we can conclude the following: • Whenever 1’s occur in vertical or horizontal pairs, the pair of boxes represents a single switch (or its complement – so one switch drops out). • Whenever 1’s occur in a 2 × 2, square, the square represents the constant 1 (two switches drop out).

We illustrate the use of these observations by an example: ab 0 1

0 1 1

1 1 0

1

1 ⇒ a0 1 ⇒ b0 1

Hence the circuit is represented by a0 ∨ b0. 37

Karnaugh Maps For Three Switches We use tables of the following format: abc 0 1

00

01

11

10

00 1 1

01 1

11 1

10

Example 1: abc 0 1

1

1 ⇒ a0 ∧ c

1 ⇒ b0 ∧ c0 1

So the circuit is represented by (a0 ∧ c) ∨ (b0 ∧ c0).

38