Number Systems and Boolean Algebra

Abstract

Number Systems and Boolean Algebra form the mathematical foundation of digital system design. Positional number representations (Binary, Octal, Hexadecimal) allow compact abstractions for binary physical signals. Boolean Algebra defines operations over two-valued logic ($B=\{0,1\}$) using primary operators ($\text{AND},\text{OR},\text{NOT}$) and derived logic gates ($\text{NAND},\text{NOR},\text{XOR},\text{XNOR}$). Circuit analysis and simplification rely on core Boolean axioms, the Principle of Duality, algebraic theorems, and formal proof techniques.

---

Positional Number Encoding

In positional number systems, each digit’s position represents a specific power of the base (radix). A symbol in a given position indicates the quantity of that power:

$$\text{Value}=\sum _i{d}_i\times b^i$$

• Base 10 (Decimal): Uses symbols $\{0,1,2,3,4,5,6,7,8,9\}$. Positions represent powers of 10.
• Base 2 (Binary): Uses symbols $\{0,1\}$. Positions represent powers of 2. This matches physical two-state digital hardware (high/low voltage levels).
• Base 16 (Hexadecimal): Uses symbols $\{0\dots 9,A\dots F\}$ (where $A=10\dots F=15$). Functions as a compact human-readable shorthand for binary (each hex digit corresponds to exactly 4 binary bits / 1 nibble).
• Base 8 (Octal): Uses symbols $\{0\dots 7\}$. Positions represent powers of 8 (each octal digit corresponds to 3 binary bits).

---

Primary Logic Gates & Operations

Boolean algebra operates on a two-element set $B=\{0,1\}$. Variables evaluate strictly to $0$ or $1$, and operators return results in $B$.

Primary Operators

1. Logical AND (Intersection): Denoted by $\cdot$ or concatenation ($a\cdot b$ or $ab$). Returns $1$ if and only if all inputs are $1$.
2. Logical OR (Union): Denoted by $+$ ($a+b$). Returns $1$ if at least one input is $1$.
3. Logical NOT (Complement): Denoted by $a^{\prime }$ or $\overline{a}$. Inverts the binary input value.
4. Buffer: Returns the input value unchanged ($f(a)=a$). Used in physical circuits for signal amplification and propagation delay.

Inputs ($a,b$)	AND ($a\cdot b$)	OR ($a+b$)	NOT ($\overline{a}$)	Buffer ($a$)
$0,0$	$0$	$0$	$1$	$0$
$0,1$	$0$	$1$	$1$	$0$
$1,0$	$0$	$1$	$0$	$1$
$1,1$	$1$	$1$	$0$	$1$

AND Gate Symbol

OR Gate Symbol

NOT Gate (Inverter) Symbol

Derived Logic Gates

Derived gates combine primary operators to perform specialized logic functions:

• NAND: Inverted AND, expressed as $(a\cdot b{)}^{\prime }$. Universal gate.
• NOR: Inverted OR, expressed as $(a+b{)}^{\prime }$. Universal gate.
• XOR (Exclusive-OR): Returns $1$ when inputs differ ($a\oplus b=a^{\prime }b+a{b}^{\prime }$).
• XNOR (Equivalence): Inverted XOR, returns $1$ when inputs are identical ($(a\oplus b{)}^{\prime }=ab+a^{\prime }{b}^{\prime }$).

NAND Gate Symbol

NOR Gate Symbol

XOR Gate Symbol

XNOR Gate Symbol

Truth Table for Derived Gates

$a$	$b$	NAND ($(ab{)}^{\prime }$)	NOR ($(a+b{)}^{\prime }$)	XOR ($a\oplus b$)	XNOR ($(a\oplus b{)}^{\prime }$)
$0$	$0$	$1$	$1$	$0$	$1$
$0$	$1$	$1$	$0$	$1$	$0$
$1$	$0$	$1$	$0$	$1$	$0$
$1$	$1$	$0$	$0$	$0$	$1$

---

Boolean Axioms and Theorems

Fundamental Axioms

Axiom Name	Primary Form	Dual Form
Binary Field	$B=0\text{ if }B\ne 1$	$B=1\text{ if }B\ne 0$
NOT Operation	$\overline{0}=1$	$\overline{1}=0$
Identity Axiom	$0\cdot 0=0$	$1+1=1$
Unit Axiom	$1\cdot 1=1$	$0+0=0$
Null Axiom	$0\cdot 1=1\cdot 0=0$	$1+0=0+1=1$

Single-Variable Theorems

Theorem Name	Theorem	Dual Form
Identity	$B\cdot 1=B$	$B+0=B$
Null Element	$B\cdot 0=0$	$B+1=1$
Idempotency	$B\cdot B=B$	$B+B=B$
Involution	$\overline{\overline{B}}=B$	—
Complements	$B\cdot \overline{B}=0$	$B+\overline{B}=1$

Multi-Variable Theorems

Theorem Name	Primary Form	Dual Form
Commutativity	$B\cdot C=C\cdot B$	$B+C=C+B$
Associativity	$(B\cdot C)\cdot D=B\cdot (C\cdot D)$	$(B+C)+D=B+(C+D)$
Distributivity	$B+(C\cdot D)=(B+C)\cdot (B+D)$	$B\cdot (C+D)=(B\cdot C)+(B\cdot D)$
Covering	$B\cdot (B+C)=B$	$B+(B\cdot C)=B$
Combining	$(B\cdot C)+(B\cdot \overline{C})=B$	$(B+C)\cdot (B+\overline{C})=B$
Consensus	$(B\cdot C)+(\overline{B}\cdot D)+(C\cdot D)=B\cdot C+\overline{B}\cdot D$	$(B+C)\cdot (\overline{B}+D)\cdot (C+D)=(B+C)\cdot (\overline{B}+D)$
De Morgan’s Law	$\overline{B_0\cdot B_1\cdot B_2\dots }=\overline{B_0}+\overline{B_1}+\overline{B_2}\dots$	$\overline{B_0+B_1+B_2\dots }=\overline{B_0}\cdot \overline{B_1}\cdot \overline{B_2}\dots$

---

Principle of Boolean Duality

The dual of a Boolean expression is obtained by swapping $\cdot$ with $+$, $0$ with $1$, and vice versa, while leaving all variables unchanged.

$$\text{General Duality: }f(X_1,X_2,\dots ,X_n,0,1,+,\cdot )⟺f(X_1,X_2,\dots ,X_n,1,0,\cdot ,+)$$

Property of Duality

If an algebraic theorem or equality is proven true, its dual form is guaranteed to be true without requiring a separate proof. Note that Duality is distinct from De Morgan’s Theorem (Duality does not negate variables).

---

Proof Techniques for Boolean Expressions

1. Proof by Perfect Induction (Truth Tables)

Exhaustively verifies that both sides of a Boolean expression evaluate to identical truth values across all possible input variable combinations.

Example: Prove De Morgan’s Law $(X+Y{)}^{\prime }=X^{\prime }\cdot Y^{\prime }$

$X$	$Y$	$X^{\prime }$	$Y^{\prime }$	$(X+Y)$	$(X+Y{)}^{\prime }$	$X^{\prime }\cdot Y^{\prime }$
$0$	$0$	$1$	$1$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$0$	$0$
$1$	$0$	$0$	$1$	$1$	$0$	$0$
$1$	$1$	$0$	$0$	$1$	** $0$**	$0$

Result: Columns $(X+Y{)}^{\prime }$ and $X^{\prime }\cdot Y^{\prime }$ are identical for all inputs, proving the identity.

2. Algebraic Proof

Applies axiomatic identities step-by-step to transform one side of an equation into the target expression.

Example: Prove the Combining Theorem $X\cdot Y+X\cdot Y^{\prime }=X$

$$\begin{array}{rlrl}X\cdot Y+X\cdot Y^{\prime }& =X\cdot (Y+Y^{\prime })& & \text{(Distributivity)}\\ & =X\cdot (1)& & \text{(Complementarity: }Y+Y^{\prime }=1\text{)}\\ & =X& & \text{(Identity: }X\cdot 1=X\text{)}\end{array}$$

---

Related Notes

• Transistors & Gates
• Combinational Logic Design
• SOP, POS, K-Maps & Logic Simplification
• Digital Systems