2. Circuits and Truth Tables¶

2.1. Gates and Truth Tables¶

Here are the four basic gates:

In the above drawings, the input wires are labelled with the names P and Q. The output that is computed is emitted from the rightmost wire which exits the gate. For these simple gates, it is possible to exhaustively test every permutation of potential inputs and summarize results in a table, called a truth table.

Let’s examine the AND gate. The AND gate emits a high voltage (1) exactly when high voltages are sensed at input wires P and Q; otherwise low voltage (0) is emitted. The gate’s physical behavior is summarized by in the following table.:

AND: P Q |
------------
     1 1 | 1
     1 0 | 0
     0 1 | 0
     0 0 | 0

For the remainder of this course, we will use T (read “true”) for 1 and F (read “false”) for 0. This is because we will examine applications that go far beyond circuit theory and base-two arithmetic. Here are the truth tables for the AND, OR, NOT and IMPLY gates:

OR is sometimes called “inclusive or”, because as long as one of its inputs is true, then its output is true. This differs from common United States English usage. Generally in spoken and written English, “or” carries the exclusive connotation. If offered a choice of “coffee or tea,” it is understood that you may select one but not both. The logical “or” is admits the possibility of both. It is more accurately translated into the English language as “and/or”.

The meaning of the IMPLY gate will be covered latter in this chapter. It is included here so all the gate information is consolidated.

It is standard to write each gate in a linear notation, that is, instead of drawing , we write P ∧ Q. (The tradition of writing linear notations to represent two-dimensional structures goes back centuries in physics and math.) The notations are as follows (the traditional math notations are provided for your reference.)

These notes will typically use the UNICODE notations.

We can also compose the gates to define new operations.

For example, this circuit, written ¬ (P ∧ Q), defines this computation of outputs:

P Q | ¬ (P ∧ Q)
--------------
T T | F
T F | T
F T | T
F F | T

which we can work out in stages, like this:

We begin by writing the value of each set of inputs on the left, under their corresponding symbol on the right. Next we apply the operator (gate) with the highest precedence (covered in Logical Operator Precedence below). In our case the “()” make the AND (∧) symbol the highest.

A truth assignment is a unique permutation of the possible inputs for a system. For the ∧-gate, it is a 2-variable sequence. Considering the first row we see we have ” T ∧ T”–looking that up in the ∧-gate truth table we see the result is also “T”, and we record that under the “∧” symbol. We do the same thing all the other truth assignments.

After the initial transcribing of the truth values under their respective variables, we look up the truth-values in the gate tables, not the variables. Also observe that while ∧ is symmetric, i.e. “T F” == “F T” == “F” the IMPLY gate is not.

Now we look up the value under the “∧” symbol in the ¬ gate table. In the first row we see that the truth assignment for the first row, “T”, is “F” and record it under the “¬” symbol. Do this for every row and we are done.

1      *
2------------
3p | p ∨ ¬ p
4------------
5T | T T F T
6F | F T T F
7------------
8Tautology

1      *
2------------
3p | p ∧ ¬ p
4------------
5T | T F F T
6F | F F T F
7------------
8Contradictory

2.1.2. Truth Tables as Proofs¶

This is a class about logic. As such, much the class will involve formally proving some claim is always true, never true, or true only under certain conditions. Many types of “computing” problems can be expressed as truth tables.

Consider the simple 2-bit integer adder.

While it has a lot of parts (three “answer” tables, each with 2^2 truth assignments), it is certainly feasible (although irritating) to calculate these tables by hand. But recall, that most integers are represented by 32-bits, leading to 33 tables (don’t forget the Carry-Over or Overflow bit), each with 2^32 entries. This will take a bit (pun intended) over a 1,100-years to write out by hand if you can average one truth assignment per second.

Considering you will probably never be asked to write a real-world application as simple as integer addition, it is easy to conclude that it is infeasible to prove the correctness of programs by truth tables. The inability to test a program by exhaustively testing every input or state is known as the combinatorial explosion problem.

OKay … then why are we making you learn truth tables? Well, even when more advanced techniques are applied to prove logical statements, underling the techniques’ soundness are these primitive rules which are easily expressed and learned via truth tables.

2.2. Logika Truth Tables¶

From this point forward, the course will expect you to use Logika formatted truth tables. The Logika truth table for the formula ¬ (P ∧ Q) is:

1      *
2------------
3p | p ∨ ¬ p
4------------
5T | T T F T
6F | F T T F
7------------
8Tautology

Logika truth tables have standard format (syntax) and semantic meanings. All elements of the truth table must be included to be considered correct.

The first line will always contain a single asterisk (*) over the last operator evaluated in the formula. This may also be referred to as the “top level” or “lowest precedent” operator. Why it is called the “top level” operator will be covered towards the end of this chapter.

Next is a line of - (minus sign) characters, these lines must be at least as long as the third line to avoid getting errors.

The third line contains “variables | formula”. As Logika uses some capital letters as reserved words, lower case letters are used as variable names. Additionally, variables should be listed alphabetically.

The fourth line is another row of -.

Next come the truth assignments. Convention is to start with all True and progress linearly to all False. Capital T and F must be used. In a truth assignment each variable is mapped to either true or false.

After the Truth assignments is another row of -.

Lastly comes the table. When all truth assignment cause the formula to be true, the word Tautology is used without an accompanying table. Similarly, when all truth assignments are false, Contradictory is used. All other results are Contingent, see the example in the figure above.

The order of precedence for logical operators from highest to lowest are:

Parentheses alter the order of operations as they do in normal algebra. Parenthetical expressions are evaluated from most-deeply nested to least-deeply nested (inside-to-outside).

2.3. The Strange Case of the Imply-gate¶

The astute reader will notice that → truth tables work very different from ∧ and ∨. To begin with, ∧ and ∨ truth assignments are symmetric; if [T F] == F then [F T] == F. This is not true of implication because, p → q is a composite claim that asserts that p holds knowledge sufficient to deduce q.

Lets use a concrete example from K-State. If I know you are majoring in computer science (fact p), then I know you are majoring in engineering (fact q).

majoring in computer science  →  majoring in engineering
           p                  →           q

However the converse, majoring in Engineering  → majoring in Computer Science is not necessarily true.

Some students tend to conflate “p holds knowledge sufficient to deduce q” to mean “p == q”, and are surprised and indignant that the truth assignment [F T] in the IMPLY gate is True. p → q does not mean p == q or q == p

In the truth table for p → q, the result reflects the existence of a serial link between p and q. First p must be true, then q must also be true in order for the implication to be true.

If both are true, the link is true, and the implication (the relationship) between p and q is true.

If p is true and q is false, clearly p does not hold knowledge sufficient to deduce q, so the relationship is not true (false).

Finally, if p is not true, there is no way to know whether the relationship holds. In this case, the implication is said to be true, or vacuously true. There is certainly no evidence to prove that it is false.

Implication in logic was formalized by William of Ockham, in his book Summa Logicae in the 14th century. These somewhat convoluted rules add tremendous expressive power to logic and computation. Without them there would be no branching in programs (no IFs, no FORs, no WHILEs).

2.4. Common Logical Formula (circuit) Equivalences¶

 1         *
 2--------------
 3p q | (p ∧ q)
 4--------------
 5T T |  T T T
 6T F |  T F F
 7F T |  F F T
 8F F |  F F F
 9---------------
10Contingent
11- T : [T T]
12- F : [F F] [F T] [T F]

 1         *
 2-------------------
 3p q |  p ∧ (q ∧ p)
 4-------------------
 5T T |  T T  T T T
 6T F |  T F  F F T
 7F T |  F F  T F F
 8F F |  F F  F F F
 9--------------------
10Contingent
11- T : [T T]
12- F : [F F] [F T] [T F]

(p ∧ ¬ q) ∨ (¬p ∧ q)
(p ∨ q) ∧ ¬ (p ∧ q)

2.5. Why it is called the “Top Level” operator¶

Let us return to the 2-bit adder, and consider only the circuitry for Q1. In a circuit, knowledge can be said to flow along the wires, where it is transformed by gates and the new knowledge propagates to the next point.

In the circuit annotated above, it is clear what knowledge (facts and deduced facts) flow in each wire segment. A common mathematical, hence computer science technique is to represent this type of knowledge flow in specialized type of graph called a tree. A tree is represented by a collection of nodes and edges, one node is selected as the “root” and all nodes have a unique path (a collection of edges) leading to the root node. By convention, the tree is drawn inverted, with its root at the top and its leaves hanging from the bottom.

In computer science, the root is selected to be the node which provides the “final answer” to the problem. As you can see, edges carry facts and nodes are operators which deduce new facts.

The tree representation of a computer program is a fundamental abstraction for computer scientist. Modern compilers and interpreters take a program written in a high level programing language and convert it into an abstract syntax tree (AST), which is then converted to machine-code. For languages in the functional paradigm (C# and Java are in the imperative and/or object paradigms ), there is a strong correlation between the high-level program’s structure and that of the AST.

When we compare the tree with the logical statement, we see the lowest priority operator is the root of the tree; hence the term “Top Level” operator.

             *
(¬(A1 ∧ B1)) ∧ (A1 ∧ B1)

2.6. Knowledge Travels Along the Wires of A Circuit¶

So far, we pretended that low- and high-voltage levels travel along the wiring of a circuit. But it is really knowledge that travels the circuit. This is understood with some pictures. Here is a circuit:

and here is its coding in equations:

R = P ∧ Q
S = R ∨ Q
T = ¬ S

Let’s redraw the circuit vertically and lay it side by side with the assignment equations:

Each wire in the circuit is named. These are just variable names. Indeed, the first (electronic) computer programs, in the 1940s, were descriptions of wiring diagrams like this one. The modern stored-program computer, developed by John von Neumann in the 1950s, used storage registers to hold the values of the variable names and used a processor to compute the values of the equations. In this way, a processor-plus-registers can simulate a circuit, and all computer programs are merely descriptions of circuits in which information flows through the wires (the variables).

This is the origin of variable-based, assignment-based computer programming. Now, at each of the program points, marked by stars in the above diagram, what information travels in the wires? We might use the circuit with some inputs to see “what happens”. Say that we supply true for P and false for Q:

The diagram shows the values on the wires labelled P, Q, R and S as they travel through the circuit. But this is just tracking the values of the variables in the assignment program we wrote! The “output variable”/write, named T, has value true.

Just as interesting is that we can analyze the program/circuit before it is completely tested. For example, say that the circuit will be inserted into a board where its P wire will always receive a t as input, but we don’t know what Q will receive. What can we predict about the circuit’s behavior once it is embedded in the board? It’s this:

In the diagram, we see that R = Q is stated after the AND gate. How do we know this? First, we do know that R = P ∧ Q. But P = true. We substitute true for P and obtain R = true ∧ Q. Next, we do a cases analysis and consider the cases of Q’s possible value: If Q is true, then true ∧ Q is true ∧ true, which simplifies to true, that is, to Q’s value. Similarly, when Q is false, then t ∧ Q is false as well. Hence, in both cases, true ∧ Q equals Q.

The above reasoning is a deduction – we deduced from the facts P = true and R = P ∧ Q that R = Q. The whole point of this course is to learn how to make such deductions.

The other deductions in the example are calculated with similar uses of substitution, simplification, and cases analysis.

The point of the previous example is that we can deduce (predict) properties of the circuit in advance of using it. These deductions complement testing.

Next, say that we don’t know anything about P and Q as inputs. What can be stated about the circuit’s output? Well, it’s this:

T = ¬((P ∧ Q) ∨ Q)

stating the obvious! But by a careful examination of the truth tables, we can also state that T = ¬Q. Later in the course, we learn deduction rules that calculate this result, not relying on truth tables.

Finally, we can make circuits that take three or more inputs, e.g., (¬(P ∧ Q)) ∨ R computes:

Here, the column underneath OR defines the output. We see this circuit emits false only when P and Q are both true and R is false. This is a hint that the circuit, ¬(P ∧ Q ∧ ~R), behaves the same way (has the same truth table) as the one above. Yet another equivalent circuit is (¬P) ∨ (¬Q) ∨ R. (Why?)

In circuit design, finding equivalent circuits with fewer gates and variables saves power, time and material.

This note was adapted from David Schmidt's CIS 301, 2008, Chapter 0 course note.

It was updated in 2018 by Dr John Hatcliff and George Lavezzi
to conform with Logika syntax and more closely match
KSU's CIS 301 course as taught in Spring 2018.