MathPhys Archive
The archive of my lecture notes on mathematics, physics and other related subjects.
Front for MathPhys Archive
MathPhys
Logic and Computer
Computers are built on (propositional) logic. The reason ( ) around "propositional" is that propositional logic is not the only choice of logic for computers. There are ternary computers based on 3-valued logic. (In 3-valued logic a statement can be either true, false, or neither.) In principle, you can build computers out of any $n$-valued logic. There are also computers based upon infinite-valued logic. Examples of such computers include fuzzy computers (based upon fuzzy logic) and quantum computers (based upon the laws of the quantum world!). There are so many interesting things to talk about these uncoventional computers but our discussion here is about conventional computers that are based upon propositional logic.
Computers carry out logical calculations. Arithmetic operations such as adding two numbers are in fact logical calculations as we will see later. Computers (conventional binary computers to be clear) can understand only the bits 0 (switch on-current) and 1 (switch off-no current). Hence everything in a computer is represented as patterns of of 0s and 1s. 0 and 1 can be understood as the two truth values, true and false, of propositional logic. For example, 0 could represent true while 1 does false. Using propositional logic one can design physical devices, called logic circuits, that perform intended results by producing bits (output) from bits (input). The design of logic circuits is called computer logic. The smallest units of a circuit are called the logic gates or gates in short, i.e. logic gates are building blocks of a logic circuit. Gates correspond to the operations of propositional logic, such as $\vee$, $\wedge$, $\oplus$, and $\neg$.
Example. The diagram of Or Gate.
Or Gate
Example. The diagram of And Gate.
And Gate
Example. The diagram of Exclusive Or Gate.
Exclusive Or Gate
Example. The diagram of Not Gate
Not Gate
In practice, however, not all these operations are available to a circuit designer. For example, exclusive or can be performed using $\vee$, $\wedge$ and $\neg$ as we have seen here. $$x\oplus y\equiv(x\wedge\neg y)\vee(\neg x\wedge y)$$ The following figure shows a logic circuit that computes $x\oplus y$. The semi circle on a wire represents that the wire is crossing over another i.e. they are not connected.
A circuit to compute Exclusive Or Gate
Not gate often simply represented by a bubble. With this convention, the above circuit can be simplified as in the following figure.
There is a very useful gate called NAND (NOT-AND) Gate. It is defined by nand operator $$p|q\equiv\neg(p\wedge q)$$ What's interesting about nand operator is that any conventional operator can be expressed using only nand operator. For example, \begin{align*}\neg p&\equiv p|p\\p\wedge q&\equiv\neg(p|q)\equiv(p|q)|(p|q)\end{align*}
Example. The diagram of NAND Gate.
NAND Gate
Binary Arithmetic
The basic rules of binary arithmetic: \begin{equation}\begin{aligned}0+0&=0\\0+1&=1\\1+0&=1\\1+1&=0,\ \mbox{carry}\ 1\end{aligned}\label{eq:binadd}\end{equation}As shown, when adding 1 to 1, the result is 0 but a 1 is carried into the next position to the left. For example,adding 1 to 10111 results in 11000 with three carries. $$\begin{array}{cccccc}& & 1 & 1 & 1 & \\& 1 & 0 & 1 & 1 & 1\\+& & & & & 1\\\hline & 1 & 1 & 0 & 0 & 0\end{array}$$ Here is another example $10101+01111$. \begin{equation}\begin{array}{ccccccc}& & 1 & 1 & 1 & 1 & \\& & 1 & 0 & 1 & 0 & 1\\+& & 0 & 1 & 1 & 1 & 1\\\hline & 1 & 0 & 0 & 1 & 0 & 0\end{array}\label{eq:binadd2}\end{equation} The question is how do we design hardware to do binary arithmetic? The simplest operation is the addition of two bits shown in \eqref{eq:binadd}. The equations in \eqref{eq:binadd} actually create two output bits, a sum $s$ and a carry $c$, from two input bits $x$ and $y$. The carry bit was not mentioned for the first three because it is 1 only when both input bits are 1. On the other hand, the sum is 1 only when one of the input bits is 1 and the other is 0. Hence, the device that performs the addition of two bits, called a half adder can be represented by the following diagram.
A Half Adder
However, a half adder is not adequate to compute more complex binary sums such as \eqref{eq:binadd2} because when adding numbers with multiple digits we sometimes need three input bits. A full adder takes three input bits $X$, $Y$, and the carry-in bit $C_{\mathrm{in}}$ and produce two output bits, the sum $S$ and the carry-out bit $C_{\mathrm{out}}$. Th following is the truth table for computing the two output bits $S$ and $C_{\mathrm{out}}$ from the three input bits $X$, $Y$, and $C_{\mathrm{in}}$. $$\begin{array}{|c|c|c|c|c|}\hline X & Y & C_{\mathrm{in}} & S & C_{\mathrm{out}}\\\hline 0 & 0& 0 & 0 & 0\\\hline0 & 0 & 1 & 1 & 0\\\hline0 & 1 & 0 & 1 & 0\\\hline 0 & 1 & 1 & 0 &1\\\hline 1 & 0 & 0 & 1 &0\\\hline 1 & 0 & 1 & 0 & 1\\\hline 1 & 1 &0 & 0 &1\\\hline 1 & 1 & 1 & 1 & 1\\\hline\end{array}$$ The following diagram shows a way to construct a full adder using two half adders (represented by a box called HA). The circuit produces the sum bit by adding $X$ and $Y$ and then adding $C_{\mathrm{in}}$ to the result. The $C_{\mathrm{out}}$ is 1 if there is a carry from either the first or the second of these additions.
A Full Adder
[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019
This entry was posted in Discrete Mathematics on October 15, 2019 by Sung Lee.
← Normal Forms Quantificational Logic →
Support MathPhys Archive
If you like what you read here and think it is helpful for you, please kindly consider a donation to support maintaining this site and its server, and to support improving the quality of its blog content.
Follow @geomphys
Modular Arithmetic
Equivalence Relations
Directed Graphs
Quantificational Logic
Sung Lee on The Chain Rule
Sung Lee on Implicit Differentiation
roberta on Implicit Differentiation
Classical Differential Geometry
Fourier Analysis
Functions of a Complex Variable
General Topology
Lie Groups and Lie Algebras
Math on Twitter
Quantum Algebra
Representation Theory
Stochastic Calculus