Boolean Algebra

What is Boolean Algebra?

• Boolean algebra is a mathematical system used to manipulate and simplify Boolean values (True/False or 1/0)
• It is essential in Computer Science for optimising logic circuits
• Complex expressions can be reduced to simpler forms, meaning fewer logic gates are required in the physical hardware
• It offers a more powerful simplification method than Karnaugh maps, as it can handle expressions with more variables and algebraic relationships
• By combining specific laws and rules, complex logic can often be reduced to a single term

---

General Rules

These fundamental rules deal with how variables interact with constants (0 and 1) and themselves.

General AND Rules

Null Law

• $X\wedge 0=0$
• Any value AND 0 is always 0

Identity Law

• $X\wedge 1=X$
• Any value AND 1 remains unchanged

Idempotent Law

• $X\wedge X=X$
• Connecting two inputs to the same variable results in that variable

Inverse Law

• $X\wedge \neg X=0$
• A variable cannot be True AND False simultaneously

General OR Rules

Identity Law

• $X\vee 0=X$
• Any value OR 0 remains unchanged

Null Law

• $X\vee 1=1$
• If one input is 1, the output is always 1

Idempotent Law

• $X\vee X=X$
• Connecting two inputs to the same variable results in that variable

Inverse Law

• $X\vee \neg X=1$
• Either the variable or its opposite must be true

---

De Morgan’s Laws

De Morgan’s Laws provide a strategy for simplifying expressions that involve the negation of a conjunction (AND) or a disjunction (OR).

A common mnemonic for this process is: “Break the bar and change the sign”

Law 1: Negation of AND

The negation of a conjunction is the disjunction of the negations.

$\neg (A\wedge B)\equiv (\neg A)\vee (\neg B)$

Truth Table Proof:

A	B	$A\wedge B$	$\neg (A\wedge B)$	$\equiv$	$\neg A$	$\neg B$	$\neg A\vee \neg B$
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

Law 2: Negation of OR

The negation of a disjunction is the conjunction of the negations.

$\neg (A\vee B)\equiv (\neg A)\wedge (\neg B)$

Truth Table Proof:

A	B	$A\vee B$	$\neg (A\vee B)$	$\equiv$	$\neg A$	$\neg B$	$\neg A\wedge \neg B$
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

Applying De Morgan’s Law (Step-by-Step)

Example 1: $\neg (A\vee B)$

1. Identify the operator inside the brackets ($\vee$): $\neg (A\vee B)$
2. Invert the operator ($\vee \to \wedge$): $\neg (A\wedge B)$
3. Negate each term: $(\neg A\wedge \neg B)$
4. Remove the outer negation: $(\neg A\wedge \neg B)$

Example 2: $\neg (X\wedge Y)$

1. Identify the operator inside the brackets ($\wedge$): $\neg (X\wedge Y)$
2. Invert the operator ($\wedge \to \vee$): $\neg (X\vee Y)$
3. Negate each term: $(\neg X\vee \neg Y)$
4. Remove the outer negation: $(\neg X\vee \neg Y)$

Example 3: $\neg (\neg A\vee B)$

1. Identify the operator inside the brackets ($\vee$): $\neg (\neg A\vee B)$
2. Invert the operator ($\vee \to \wedge$): $\neg (\neg A\wedge B)$
3. Negate each term: $(A\wedge \neg B)$
4. Remove the outer negation: $(A\wedge \neg B)$

Example 4: $\neg ((A\vee B)\wedge C)$

1. Identify the main operator ($\wedge$): $\neg ((A\vee B)\wedge C)$
2. Invert the operator ($\wedge \to \vee$): $\neg (A\vee B)\vee \neg C$
3. Apply De Morgan’s law to the inner brackets: $(\neg A\wedge \neg B)\vee \neg C$
4. Remove the outer negation: $(\neg A\wedge \neg B)\vee \neg C$

Example 5: $\neg (P\vee (Q\wedge R))$

1. Identify the main operator ($\vee$): $\neg (P\vee (Q\wedge R))$
2. Invert the operator ($\vee \to \wedge$): $\neg P\wedge \neg (Q\wedge R)$
3. Apply De Morgan’s law to the inner brackets: $\neg P\wedge (\neg Q\vee \neg R)$
4. Remove the outer negation: $\neg P\wedge (\neg Q\vee \neg R)$

• Simplifying using this law allows the use of only NAND or NOR gates which makes building microprocessors much easier (i.e. Flash drives)

---

Double Negation

Double negation cancels itself out.

$\neg (\neg A)=A$

Real-life example:

• “It is not true that I am not hungry” is the same as saying “I am hungry”

---

Distribution

The Distributive Law explains how AND and OR interact, similar to expanding brackets in standard maths. This allows you to multiply out or factorise expressions.

AND over OR $A\wedge (B\vee C)=(A\wedge B)\vee (A\wedge C)$

OR over AND (Unique to Boolean Algebra) $A\vee (B\wedge C)=(A\vee B)\wedge (A\vee C)$

Real-life example for “OR over AND”:

• Ordering a meal deal: “You must choose a Sandwich OR (Chips AND Drink)”
• This is logically equivalent to: “(Sandwich OR Chips) AND (Sandwich OR Drink)”
• You must satisfy both conditions

---

Association

The Associative Law allows the regrouping of variables when the operators are the same. Brackets can be moved or removed without changing the logic.

$(A\wedge B)\wedge C=A\wedge (B\wedge C)=A\wedge B\wedge C$

$(A\vee B)\vee C=A\vee (B\vee C)=A\vee B\vee C$

---

Commutation

The Commutative Law states that the order of variables does not matter.

$A\wedge B=B\wedge A$

$A\vee B=B\vee A$

---

Absorption

Absorption rules are powerful tools for eliminating redundant terms quickly. If a term outside the bracket is repeated inside the bracket with the opposite operator, the outside term “absorbs” the rest.

$A\vee (A\wedge B)=A$

$A\wedge (A\vee B)=A$

Why does this work? Looking at $A\vee (A\wedge B)$:

• If $A=1$: The result is $1\vee (\dots )$, which is always 1 ($A$)
• If $A=0$: The result is $0\vee (0\wedge B)\to 0\vee 0$, which is 0 ($A$)
• Therefore, $B$ is irrelevant

Worked Example

Question: Simplify the expression $Q=\neg (A\vee B)\vee (A\wedge \neg B)$

Step 1: Apply De Morgan’s Law First, look at the term $\neg (A\vee B)$. Apply the “break the bar, change the sign” rule. $(\neg A\wedge \neg B)\vee (A\wedge \neg B)$

Step 2: Factorise (Distribution) Notice that both parts of the expression share a common term: $\wedge \neg B$. We can factor this out, just like factorising $xy+zy$ to $y(x+z)$ in maths. $\neg B\wedge (\neg A\vee A)$

Step 3: Apply Inverse Rule Look at the bracket $(\neg A\vee A)$. The Inverse Law states that $X\vee \neg X=1$. $\neg B\wedge (1)$

Step 4: Apply Identity Rule The Identity Law states that $X\wedge 1=X$. $\neg B$

Final Answer: $Q=\neg B$