Recently, I’ve started exploring Mathematical Logic, guided by Elliott Mendelson’s “Introduction to Mathematical Logic, 6th Edition”. One fascinating fact I found in the textbook is that “Every truth function is generated by a statement form involving the logical connectives in a functional complete set“. This idea sparked my interest, leading me to connect it with experiences from my past.
Before diving deeper, please let me introduce some prerequisite concepts to you.
Formally, in Mathematical Logic:
- A truth function is defined as $f: \{0, 1\}^n \to \{0, 1\} $, where $0$ represents False (F) and $1$ represents True (T).
- A propositional variable is the variable $\in \{0, 1\}$, equivalently, it is the variable that can either have the True or False value.
- Well-formed formulas (WFFs) are expressions defined as follows:
- A propositional variable is a WFF.
- If $A$ and $B$ are WFFs, then $A \wedge B, \neg B, \neg A$ are also WFFs.
Then we proceed to introduce the following theorems:
$\textbf{Theorem 1}$
Every truth function is generated by a WFF involving the logical connectives $\neg$ (NOT), $\wedge$ (AND) and $\vee$ (OR). Equivalently, the set $\{\neg, \wedge, \vee\}$ constitutes a functionally complete set of logical connectives.
$\textbf{Proof}$
For any truth function $f(x_1,x_2,\cdots,x_n)$ where $x_1,x_2,\cdots,x_n \in \{0, 1\}$, we can represent $f(x_1,x_2,\cdots,x_n)$ in a truth table with $2^n$ rows, since the total number of combinations of $x_1,x_2,\cdots,x_n$ is $2^n$ and each combination produces a corresponding output of $f(x_1,x_2,\cdots,x_n)$.
For each row in the truth table where the function $f(x_1,x_2,\cdots,x_n)$ outputs $1$, we can construct a conjunction $\wedge$ (AND) that corresponds to that particular combination of inputs.
More generally, for a given row $i \in \{1,2,\cdots, 2^n\}$, we define a conjunction $C_i$ as follows: $C_i = U_{i,1} \wedge U_{i,2} \wedge \cdots \wedge U_{i,n}$, where $U_{i,j} = x_{i,j}$ if $x_{i,j} = 1$, else $U_{i,j} = \neg x_{i,j}$ if $x_{i,j} = 0$, where $j \in \{1,2,\cdots,n\}$.
After setting up $C_{1}, C_{2},\cdots, C_{n}$, we take the disjunction $\vee$ (OR) of all such conjunctions corresponding to the truth rows where the function $f$ outputs $1$, assume there are $m \in \{1,2,\cdots,n-1\}$ such rows (The situations of $m=0$ and $m=n$ are discussed below.). This forms a statement in disjunctive normal form (DNF) representing our original truth function $f$. This DNF statement, denoted as $D$, is defined as $D = C_1 \vee C_2 \vee \cdots \vee C_m$, where each $C_k$ (where $k \in \{1,2,\cdots,m\}$) corresponds to one of the rows where $f$ outputs $1$, and $m$ is the number of such rows.
If $m=0$, in other words, if $f$ always outputs $0$, then $D$ can be defined as a contradiction (for example: $D = x_1 \wedge \neg x_1$). If $m=n$, in other words, if $f$ always outputs $1$, then $D$ can be defined as a tautology (for example: $D = x_1 \vee \neg x_1$).
Accordingly and obviously, we have $f(x_1,x_2,\cdots,x_n) \iff D$. Then since $D$ is a corresponding wff involving the logical connectives $\neg$ (NOT), $\wedge$ (AND) and $\vee$ (OR), therefore “Every truth function is generated by a WFF involving the logical connectives $\neg$ (NOT), $\wedge$ (AND) and $\vee$ (OR).”
$\Box$
$\textbf{Example 1}$
$$\begin{array}{c}
x_1 & x_2 & x_3 & f\left(x_1, x_2, x_3\right) \\
\mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{T} \\
\mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T} \\
\mathrm{F} & \mathrm{T} & \mathrm{F} & \mathrm{F} \\
\mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{F} \\
\mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{F} \\
\mathrm{T} & \mathrm{T} & \mathrm{F} & \mathrm{F} \\
\mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{F} \\
\mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{F}
\end{array}$$
Then $$f(x_1, x_2, x_3) \iff D = (\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge \neg x_2 \wedge x_3)$$
$\Box$
Here is the Python program I wrote. This program uses AND, OR and NOT gate, based on $\textbf{Theorem 1}$, to construct the equivalent DNF of any logic gate.
# python3
def convert_to_dnf(truth_table):
D = []
for row in truth_table:
if row[-1] == 1:
terms = []
for i, val in enumerate(row[:-1]):
if val == 1:
terms.append(f"x_{i+1}")
else:
terms.append(f"¬x_{i+1}")
if terms:
C_i = " ∧ ".join(terms)
D.append(C_i)
if D:
dnf_structure = f'({") ∨ (".join(D)})'
else:
dnf_structure = "(x_1 ∧ ¬x_1)"
return dnf_structure
# Here we use the truth table from Example 1
truth_table = [
[0, 0, 0, 1],
[0, 0, 1, 1],
[0, 1, 0, 0],
[1, 0, 0, 0],
[0, 1, 1, 0],
[1, 1, 0, 0],
[1, 0, 1, 0],
[1, 1, 1, 0],
]
dnf_gate_structure = convert_to_dnf(truth_table)
print("DNF:", dnf_gate_structure)$\textbf{Theorem 2}$
The set $\{\downarrow \text{(NOR)} \}$ constitutes a functionally complete set of logical connectives.
$\textbf{Proof}$
According to the definition, $x_1 \downarrow x_2 \iff \neg (x_1 \vee x_2)$. By constructing and analyzing the corresponding truth table, we deduce that $\neg x_1 \iff (x_1 \downarrow x_1)$, $x_1 \wedge x_2 \iff (x_1 \downarrow x_1) \downarrow(x_2 \downarrow x_2)$ and $x_1 \vee x_2 \iff (x_1 \downarrow x_2) \downarrow(x_1 \downarrow x_2)$. Then apply $\textbf{Theorem 1}$ and the substitutions, clearly “The set $\{\downarrow \}$ constitutes a functionally complete set of logical connectives.”
$\Box$
$\textbf{Example 2}$
Set
$$\begin{align}
A & = \bigg( \Big( \big( (x_1 \downarrow x_1) \downarrow (x_1 \downarrow x_1) \big) \downarrow \big( (x_2 \downarrow x_2) \downarrow (x_2 \downarrow x_2) \big) \Big) \downarrow \Big( \big( (x_1 \downarrow x_1) \downarrow (x_1 \downarrow x_1) \big) \downarrow \big( (x_2 \downarrow x_2) \downarrow (x_2 \downarrow x_2) \big) \Big) \bigg)\\
B & = \bigg( (x_3 \downarrow x_3) \downarrow (x_3 \downarrow x_3) \bigg) \\
C & = \bigg( x_3 \downarrow x_3 \bigg)
\end{align}$$
Then the function $f(x_1, x_2, x_3)$ in $\textbf{Example 1}$ can be rewritten as
$$\begin{align}
&f(x_1, x_2, x_3) \\
\iff & D = (\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge \neg x_2 \wedge x_3) \\
\iff & D = \big( (x_1 \downarrow x_1) \wedge (x_2 \downarrow x_2) \wedge (x_3 \downarrow x_3) \big) \vee \big( (x_1 \downarrow x_1) \wedge (x_2 \downarrow x_2) \wedge x_3 \big) \\
\iff & D = \bigg( \Big( \big( (x_1 \downarrow x_1) \downarrow (x_1 \downarrow x_1) \big) \downarrow \big( (x_2 \downarrow x_2) \downarrow (x_2 \downarrow x_2) \big) \Big) \wedge (x_3 \downarrow x_3) \bigg) \\
& \vee \bigg( \Big( \big( (x_1 \downarrow x_1) \downarrow (x_1 \downarrow x_1) \big) \downarrow \big( (x_2 \downarrow x_2) \downarrow (x_2 \downarrow x_2) \big) \Big) \wedge x_3 \bigg) \\
\iff & D = \bigg( A \downarrow B \bigg) \vee \bigg( A \downarrow C \bigg) \\
\iff & D = \Bigg( \bigg( A \downarrow B \bigg) \downarrow \bigg( A \downarrow C \bigg) \Bigg) \downarrow \Bigg( \bigg( A \downarrow B \bigg) \downarrow \bigg( A \downarrow C \bigg) \Bigg)
\end{align}$$
$\Box$
Applying $\textbf{Theorem 2}$ fully unlocks the potential to design any logic gate we desire! This concept took me back to October 2021, when I discovered “Turing Complete”, which is an amazing game on Steam dedicated to constructing fundamental stuffs in Computer Science (such as logic gates and circuits). Then I shared my excitement about this game on Zhihu.com, recommending it as an excellent introduction for those new to logic circuits.
Below are some related screenshots.
At that time, I actually found some of the construction problems in that game quite challenging (to me), so I was thinking that whether it is possible to build up an algorithm that can automatically construct new logic gates through a pattern of systematic combinations? And later on I was working on other academic stuffs (I checked my timeline and found myself was preparing for the IB and AP exams during that time, though those exams were later all canceled in Shanghai due to the quarantine unfortunately…) and completely forgot about this.
This old idea resurfaced recently as I delved into Mathematical Logic, so I wrote this post…
Leave a Reply