proofs-derivations-ch2-ch3

Chapter 2 & 3 Mathematical Proofs & Derivations

Overview

This note compiles the core algebraic proofs and mathematical derivations of Chapters 2 and 3. These proofs form the baseline theoretical and logical foundations of digital logic, demonstrating “why” the algebraic rules work before hardware layout.

---

1. The Self-Complementing Weight Theorem

A weighted 4-bit binary code is self-complementing if the 1’s complement of any decimal digit’s codeword yields the exact codeword of its 9’s complement ($9-d$).

The Theorem

For a weighted 4-bit binary code with weights $(w_3,w_2,w_1,w_0)$ to be self-complementing, the sum of its weights must equal exactly 9: ${\sum }_{i=0}^3{w}_i=w_3+w_2+w_1+w_0=9$

The Algebraic Proof

1. Let a decimal digit $d$ be represented by the binary bits $B=b_3{b}_2{b}_1{b}_0$. The decimal value is: $d=w_3{b}_3+w_2{b}_2+w_1{b}_1+w_0{b}_0$
2. For the code to be self-complementing, the 9’s complement ($9-d$) must be represented by the bitwise inverted bits $B^{\prime }=b_3^{\prime }{b}_2^{\prime }{b}_1^{\prime }{b}_0^{\prime }$: $9-d=w_3{b}_3^{\prime }+w_2{b}_2^{\prime }+w_1{b}_1^{\prime }+w_0{b}_0^{\prime }$
3. Add these two equations together: $d+(9-d)=w_3(b_3+b_3^{\prime })+w_2(b_2+b_2^{\prime })+w_1(b_1+b_1^{\prime })+w_0(b_0+b_0^{\prime })$
4. Since $b_i$ is a binary bit ($0$ or $1$), the sum of a bit and its complement is always exactly $1$ ($b_i+b_i^{\prime }=1$): $9=w_3(1)+w_2(1)+w_1(1)+w_0(1)$ $\therefore w_3+w_2+w_1+w_0=9■$

---

2. Excess-3 Self-Complementing Code Proof

Excess-3 is a non-weighted code, but it is self-complementing. Here is the formal proof.

The Theorem

$\text{XS-3}(9-N)=\overline{\text{XS-3}(N)}$

The Algebraic Proof

1. Define the XS-3 representation: The Excess-3 codeword for any decimal digit $N$ ($0\le N\le 9$) is defined as: $\text{XS-3}(N)=N+3$
2. XS-3 of the 9’s complement: The representation of the 9’s complement of $N$ ($9-N$) is: $\text{XS-3}(9-N)=(9-N)+3=12-N$
3. The 1’s complement of XS-3: Taking the bitwise 1’s complement of a 4-bit number is mathematically equivalent to subtracting that number from $15_{10}$ ($1111_2$): $\overline{\text{XS-3}(N)}=15-\text{XS-3}(N)$ $\overline{\text{XS-3}(N)}=15-(N+3)=12-N$
4. Compare: $\text{XS-3}(9-N)=12-N$ $\overline{\text{XS-3}(N)}=12-N$ $\therefore \text{XS-3}(9-N)=\overline{\text{XS-3}(N)}■$

---

3. Dual of XOR Equals Its Complement (XNOR)

This is a highly repeated 10-12 mark exam question.

The Theorem

$\text{Dual}(A\oplus B)=(A\oplus B{)}^{\prime }=A\odot B$

The Algebraic Proof

Let the XOR function be $F=A\oplus B=A^{\prime }B+A{B}^{\prime }$.

Step 1: Find the Dual ($Dual(F)$)

Duality rules state we swap AND ($\cdot$) with OR ($+$), and identity elements $0\leftrightarrow 1$, leaving the literals and their complements completely unchanged. $F=(A^{\prime }\cdot B)+(A\cdot B^{\prime })$ $\text{Dual}(F)=(A^{\prime }+B)\cdot (A+B^{\prime })$ Expand by algebraic distribution: $\text{Dual}(F)=A^{\prime }A+A^{\prime }{B}^{\prime }+BA+B{B}^{\prime }$ Since $A^{\prime }A=0$ and $B{B}^{\prime }=0$ (Huntington Postulate 5b): $\text{Dual}(\mathbf{F})=\mathbf{AB}+{\mathbf{A}}^{\prime }{\mathbf{B}}^{\prime }\text{— (Eq. 1)}$

Step 2: Find the Complement ($F^{\prime }$)

Apply De Morgan’s Law to $F=A^{\prime }B+A{B}^{\prime }$: $F^{\prime }=(A^{\prime }B+A{B}^{\prime }{)}^{\prime }=(A^{\prime }B{)}^{\prime }\cdot (A{B}^{\prime }{)}^{\prime }$ $F^{\prime }=(A+B^{\prime })\cdot (A^{\prime }+B)$ Expand by algebraic distribution: $F^{\prime }=A{A}^{\prime }+AB+B^{\prime }{A}^{\prime }+B^{\prime }B$ Since $A{A}^{\prime }=0$ and $B^{\prime }B=0$: ${\mathbf{F}}^{\prime }=\mathbf{AB}+{\mathbf{A}}^{\prime }{\mathbf{B}}^{\prime }\text{— (Eq. 2)}$

Conclusion:

Comparing Eq. 1 and Eq. 2: $\text{Dual}(\text{XOR})=(\text{XOR}{)}^{\prime }=\text{XNOR}■$

---

4. The Consensus Theorem

Used to eliminate redundant product or sum terms in Boolean simplification.

Original Form (SOP)

$\mathbf{AB}+{\mathbf{A}}^{\prime }\mathbf{C}+\mathbf{BC}=\mathbf{AB}+{\mathbf{A}}^{\prime }\mathbf{C}$

Proof:

1. Multiply the redundant term $BC$ by $(A+A^{\prime })=1$: $\text{L.H.S}=AB+A^{\prime }C+BC(A+A^{\prime })$
2. Distribute: $\text{L.H.S}=AB+A^{\prime }C+ABC+A^{\prime }BC$
3. Group and factor terms: $\text{L.H.S}=AB(1+C)+A^{\prime }C(1+B)$
4. Since $1+X=1$ (Null Element Theorem): $\text{L.H.S}=AB(1)+A^{\prime }C(1)=AB+A^{\prime }C=\text{R.H.S}■$

Dual Form (POS)

$(\mathbf{A}+\mathbf{B})({\mathbf{A}}^{\prime }+\mathbf{C})(\mathbf{B}+\mathbf{C})=(\mathbf{A}+\mathbf{B})({\mathbf{A}}^{\prime }+\mathbf{C})$

Proof:

1. Add $A{A}^{\prime }=0$ to the redundant term $(B+C)$: $\text{L.H.S}=(A+B)(A^{\prime }+C)(B+C+A{A}^{\prime })$
2. Distribute the third term: $\text{L.H.S}=(A+B)(A^{\prime }+C)(B+C+A)(B+C+A^{\prime })$
3. Rearrange terms: $\text{L.H.S}=\underset{\text{Absorption: }X(X+Y)=X}{\underbrace{(A+B)(A+B+C)}}\cdot \underset{\text{Absorption: }X(X+Y)=X}{\underbrace{(A^{\prime }+C)(A^{\prime }+C+B)}}$
4. Simplify: $\text{L.H.S}=(A+B)(A^{\prime }+C)=\text{R.H.S}■$

---

5. The Absorption Laws

Original Form: $A+AB=A$

Proof:

$\text{L.H.S}=A+AB=A(1+B)=A(1)=A=\text{R.H.S}■$

Dual Form: $A(A+B)=A$

Proof:

$\text{L.H.S}=A(A+B)=AA+AB=A+AB=A(1+B)=A=\text{R.H.S}■$

---

6. 4-Variable XNOR Expansion Proof

The Theorem

$A\odot B\odot C\odot D=\sum m(0,3,5,6,9,10,12,15)$

Proof:

Let $X=A\odot B=AB+A^{\prime }{B}^{\prime }$ and $Y=C\odot D=CD+C^{\prime }{D}^{\prime }$. $F=X\odot Y=XY+X^{\prime }{Y}^{\prime }$

• Recall that $X^{\prime }=(A\odot B{)}^{\prime }=A\oplus B=A^{\prime }B+A{B}^{\prime }$
• Recall that $Y^{\prime }=(C\odot D{)}^{\prime }=C\oplus D=C^{\prime }D+C{D}^{\prime }$

Substitute these into the equation for $F$: $F=(AB+A^{\prime }{B}^{\prime })(CD+C^{\prime }{D}^{\prime })+(A^{\prime }B+A{B}^{\prime })(C^{\prime }D+C{D}^{\prime })$ $F=ABCD+AB{C}^{\prime }{D}^{\prime }+A^{\prime }{B}^{\prime }CD+A^{\prime }{B}^{\prime }{C}^{\prime }{D}^{\prime }+A^{\prime }B{C}^{\prime }D+A^{\prime }BC{D}^{\prime }+A{B}^{\prime }{C}^{\prime }D+A{B}^{\prime }C{D}^{\prime }$ Evaluating these 8 canonical product terms into decimal minterms:

• $ABCD\to 1111_2=m_{15}$
• $AB{C}^{\prime }{D}^{\prime }\to 1100_2=m_{12}$
• $A^{\prime }{B}^{\prime }CD\to 0011_2=m_3$
• $A^{\prime }{B}^{\prime }{C}^{\prime }{D}^{\prime }\to 0000_2=m_0$
• $A^{\prime }B{C}^{\prime }D\to 0101_2=m_5$
• $A^{\prime }BC{D}^{\prime }\to 0110_2=m_6$
• $A{B}^{\prime }{C}^{\prime }D\to 1001_2=m_9$
• $A{B}^{\prime }C{D}^{\prime }\to 1010_2=m_{10}$

Gathering terms: $\therefore F=\sum m(0,3,5,6,9,10,12,15)■$

---

7. Algebraic Literal Factoring (Under 8 Literals Limit)

Reducing Boolean terms algebraically using the absorption identity $X^{\prime }+XY=X^{\prime }+Y$.

Problem

Express $F=B^{\prime }{C}^{\prime }{D}^{\prime }+A{B}^{\prime }C{D}^{\prime }+B{C}^{\prime }D+A^{\prime }BCD$ in three different ways using 8 or fewer literals.

Way 1: Group by $B^{\prime }{D}^{\prime }$ and $BD$

$F=B^{\prime }{D}^{\prime }(C^{\prime }+AC)+BD(C^{\prime }+A^{\prime }C)$ Apply absorption identity $X^{\prime }+XY=X^{\prime }+Y$: $\mathbf{F}={\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }({\mathbf{C}}^{\prime }+\mathbf{A})+\mathbf{BD}({\mathbf{C}}^{\prime }+{\mathbf{A}}^{\prime })\text{(8 literals)}$

Way 2: Group by $C^{\prime }$ and $C$

Expand Way 1: $F=A{B}^{\prime }{D}^{\prime }+B^{\prime }{C}^{\prime }{D}^{\prime }+A^{\prime }BD+B{C}^{\prime }D$ $\mathbf{F}={\mathbf{C}}^{\prime }({\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }+\mathbf{BD})+\mathbf{C}(\mathbf{A}{\mathbf{B}}^{\prime }{\mathbf{D}}^{\prime }+{\mathbf{A}}^{\prime }\mathbf{BD})\text{(8 literals)}$

Way 3: Group by $D^{\prime }$ and $D$

Grouping from unsimplified $F$: $\mathbf{F}={\mathbf{D}}^{\prime }(\mathbf{A}{\mathbf{B}}^{\prime }\mathbf{C}+{\mathbf{B}}^{\prime }{\mathbf{C}}^{\prime })+\mathbf{D}({\mathbf{A}}^{\prime }\mathbf{BC}+\mathbf{B}{\mathbf{C}}^{\prime })\text{— (Eq. A)}$ Apply absorption: $B^{\prime }{C}^{\prime }+A{B}^{\prime }C=B^{\prime }(C^{\prime }+AC)=B^{\prime }(C^{\prime }+A)=B^{\prime }{C}^{\prime }+A{B}^{\prime }$ Likewise: $B{C}^{\prime }+A^{\prime }BC=B(C^{\prime }+A^{\prime }C)=B(C^{\prime }+A^{\prime })=B{C}^{\prime }+A^{\prime }B$ Substitute back into Eq. A: $\mathbf{F}={\mathbf{D}}^{\prime }(\mathbf{A}{\mathbf{B}}^{\prime }+{\mathbf{B}}^{\prime }{\mathbf{C}}^{\prime })+\mathbf{D}({\mathbf{A}}^{\prime }\mathbf{B}+\mathbf{B}{\mathbf{C}}^{\prime })\text{(8 literals)}■$