Boolean algebra

Remarkable identities

Exercise: Complete the truth tables for:

1. E ∧ 0 = 0

E	Q
0	0
1	0

2. E ∧ 1 = E

E	Q
0	0
1	1

3. E ∧ E = E

E	Q
0	0
1	1

4. E ∧ ¬E = 0

E	Q
0	0
1	0

5. E ∨ 0 = E

E	Q
0	0
1	1

6. E ∨ 1 = 1

E	Q
0	1
1	1

7. E ∨ E = E

E	Q
0	0
1	1

8. E ∨ ¬E = 1

E	Q
0	1
1	1

9. ¬¬E = E

E	¬E	¬¬E
0	1	0
1	0	1

Commutation, association, and priority rules

In algebraic expressions, there is an order of precedence for the operations. BIDMAS is a mnemonic used to help remember this order - Brackets, Indices, Division/Multiplication, Addition/Subtraction. There is also an order of precedence for Boolean operations used in Boolean algebra - Brackets, Not, Xor, And, Or (not as catchy).

Exercise: Using just the commutativity and associativity laws, simplify the below expressions

1. A ∧ A → A
2. B ∨ B → B
3. (A ∨ B) ∧ (A ∨ B) → A ∨ B
4. A ∨ A -> A
5. (A ∧ B) ∨ (A ∧ B) → A ∧ B
6. X ∨ Y ∨ X → X ∨ Y
7. B ∨ 1 → 1
8. A ∨ B ∨ A ∨ C ∨ 1 → 1
9. A ∨ B ∧ 0 → A
10. A ∨ 0 → A

Distribution

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

Exercise: Expand the brackets in the expressions. Do not simplify the resulting expressions

1. C ∧ (D ∨ B) → C ∧ D ∨ C ∧ B
2. C ∧ D ∧ (B ∨ A ∧ E) → C ∧ D ∧ B ∨ C ∧ D ∧ A ∧ E
3. A ∧ (C ∨ B ∨ D) -> A ∧ C ∨ A ∧ B ∨ A ∧ D
4. D ∧ (F ∨ E ∧ (A ∨ B)) → D ∧ F ∨ D ∧ E ∧ A ∨ D ∧ E ∧ B

Exercise: Factorise the expressions

1. C ∧ D ∨ C ∧ A → C ∧ (D ∨ A)
2. C ∧ D ∧ B ∨ B ∧ A ∧ E → B ∧ (C ∧ D ∨ A ∧ E)
3. A ∧ C ∨ C ∧ E ∨ B ∧ C → C ∧ (A ∨ B ∨ E)
4. E ∧ F ∨ E ∧ ¬F → E ∧ (F ∨ ¬F) → E

Absorption

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

Exercise: Simplify the expressions below

1. C ∨ C ∧ D → C
2. D ∨ C ∧ D ∧ B → D
3. (C ∨ A) ∧ A → A
4. D ∧ 1 ∨ D ∧ F → D
5. E ∧ F ∨ (E ∧ F ∨ D) → E ∧ F ∨ D
6. A ∧ B ∧ (0 ∨ ¬A) ∨ 1 → 1
7. ¬D ∧ (¬E ∨ ¬D) → ¬D

De Morgan's law

When using the negation of an expression, replace booleans and operators using this correspondence table:

Original	Negation
A	¬A
∧	∨
∨	∧

Exercise: Use De Moran's laws, and any other rules that will help, to simplify the expressions below

1. ¬(¬A ∧ ¬B) → A ∨ B
2. ¬(¬B ∨ ¬C) ∧ A → A ∧ B ∧ C
3. ¬(¬A ∨ ¬B) → A ∧ B
4. ¬(¬A ∧ ¬E) ∨ (A ∧ F) → A ∨ E

Final exercises

Simplify each Boolean expression using the basic rules, De Morgan's Laws

1. B ∨ (A ∧ ¬A) → B
2. A ∧ B ∨ A ∧ ¬B → A
3. ¬(1 ∧ B) → ¬B
4. ¬(¬A ∧ ¬B) ∨ A ∨ ¬B → 1
5. (¬A ∨ B) ∧ (A ∧ ¬B) → 0
6. ¬A ∨ ¬(B ∨ A) → ¬A
7. D ∨ F ∧ D ∨ F ∧ G → D ∨ F ∧ G
8. ¬B ∧ ¬(¬A ∨ ¬B) → 0
9. ¬(¬A ∧ B) ∨ A ∧ (A ∨ ¬B) → A ∨ ¬B
10. A ∧ B ∧ ¬C ∨ A ∧ ¬C → A ∧ ¬C
11. X ∧ (¬X ∨ Y) → X ∧ Y
12. D ∨ E ∧ C ∨ ¬B ∧ D ∨ E → D ∨ E
13. A ∧ A ∨ A ∧ 1 ∨ B ∧ ¬B → A
14. (A ∧ A ∨ B) ∨ 0 → A ∨ B
15. ¬(¬D ∧ ¬E) ∧ ¬(¬D ∨ ¬E) → D ∧ E
16. ¬(D ∧ ¬E) ∧ D ∨ ¬E → E ∧ D ∨ ¬E
17. (A ∨ A ∧ B) ∨ B → A ∨ B
18. ¬(A ∨ B ∨ ¬A) → 0
19. A ∨ ¬(B ∨ ¬A) → A
20. A ∧ B ∧ B ∧ C ∨ A ∧ 0 ∧ B ∨ A ∧ C ∧ B ∧ D → A ∧ B ∧ C