Computing and Data Science

Logic and Circuits

The foundations of mathematics are built with logic. The bit of logic we will see here is Boolean logic, which is the basis for digital circuits and computing.

A useful online simulator for digital logic is: https://logic.ly/demo/

Boolean Logic

A logical expression is one that evaluates to either TRUE or FALSE. A single binary bit can represent TRUE (\(1\)) or FALSE (\(0\)), and we can operate on bits with logical operations. Three fundamental logical operations are NOT, AND, and OR.

NOT

The simplest operation is NOT. Given a Boolean variable \(A\), where \(A\) is either 0 or 1, the NOT operation negates \(A\):

If \(A\) is \(0\), then NOT \(A\) is \(1\).
If \(A\) is \(1\), then NOT \(A\) is \(0\).

The digital circuit diagram for NOT looks like this:

where \(Q\) is the output. A nice way to represent this is with a truth table. The left-hand side is the input value and the right-hand side is the output value.

\[ \begin{array}{|c|c|} \hline A & \neg A \\ \hline 0 & 1 \\ 1 & 0 \\ \hline \end{array} \]

AND

Given two input bits A and B, the AND operation evaluates to TRUE when A and B are both true. The digital circuit diagram for AND looks like this:

The truth table for AND is: \[ \begin{array}{|c c|c|} \hline \rule{0pt}{2.5ex} A & B & A \land B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \hline \end{array} \]

OR

Given input bits A and B, the OR operation evaluates to TRUE when either A or B is true. The digital circuit diagram for OR looks like this:

The truth table for OR is: \[ \begin{array}{|c c|c|} \hline \rule{0pt}{2.5ex} A & B & A \lor B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \\ \hline \end{array} \]

Evaluating Expressions

Consider the expression \[\neg A \lor B \land C\] which reads "NOT A OR B AND C". This expression uses three Boolean values, and is TRUE either if A is FALSE, OR if B AND C are both TRUE. The order of operations here is that AND takes precedence over OR.

\[ \begin{array}{|c c c | c |} \hline \rule{0pt}{2.5ex} A & B & C & \neg A \lor B \land C \\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \hline \end{array} \]

A Bit More Logic

Logic is much bigger than what we have seen above (see the introduction in Chapter 1 of Levin), but Boolean logic is the foundation of digital electronics, upon which computing is built, which is directly related to the programming languages that run through digital electronics, which is where we do science with data.

Recommended Reading