2. Circuits and Truth Tables — Sireum Logika (2024)

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 andQ.The output that is computed is emitted from the rightmost wire which exits thegate. For these simple gates, it is possible to exhaustively test every permutationof 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) exactlywhen high voltages are sensed at input wires P and Q; otherwiselow voltage (0) is emitted. The gate’s physical behavior is summarized byin 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 andF (read “false”) for 0.This is because we will examine applications that go far beyond circuit theoryand 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 ofits inputs is true, then its output is true. This differs from common UnitedStates English usage. Generally in spoken and written English, “or” carries theexclusive connotation. If offered a choice of “coffee or tea,” it is understoodthat you may select one but not both. The logical “or” is admits the possibilityof 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 isincluded here so all the gate information is consolidated.

It is standard to write each gate in a linear notation, that is, instead ofdrawing , we write P ∧ Q.(The tradition of writing linear notations to represent two-dimensionalstructures goes back centuries in physics and math.)The notations are as follows (the traditional math notations are provided foryour 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 thiscomputation of outputs:

P Q | ¬ (P ∧ Q)--------------T T | FT F | TF T | TF 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 theircorresponding symbol on the right. Next we apply the operator (gate) with thehighest precedence (covered in Logical Operator Precedence below). In our casethe “()” 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 seewe have ” T ∧ T”–looking that up in the ∧-gate truth table we see the result isalso “T”, and we record that under the “∧” symbol. We do the same thing all theother truth assignments.

After the initial transcribing of the truth values undertheir respective variables, we look up the truth-values in the gate tables, notthe 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 firstrow we see that the truth assignment for the first row, “T”, is “F” and recordit under the “¬” symbol. Do this for every row and we are done.

1 *2------------3p | p ∨ ¬ p4------------5T | T T F T6F | F T T F7------------8Tautology

1 *2------------3p | p ∧ ¬ p4------------5T | T F F T6F | F F T F7------------8Contradictory

2.2. Logika Truth Tables¶

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

1 *2------------3p | p ∨ ¬ p4------------5T | T T F T6F | F T T F7------------8Tautology

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

The first line will always contain a single asterisk (*) over the last operator evaluatedin 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 theend of this chapter.

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

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

The fourth line is another row of -.

Next come the truth assignments. Convention is to start with all True and progresslinearly to all False. Capital T and F must be used. In a truth assignmenteach 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, whenall truth assignments are false, Contradictory is used. All other resultsare 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 toleast-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 compositeclaim that asserts that p holds knowledge sufficient to deduce q.

Lets use a concrete example from K-State. If I know you are majoringin 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 Scienceis 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] inthe 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 seriallink between p and q. First p must be true, then q must alsobe true in order for the implication to be true.

If both are true, the link istrue, 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 sufficientto 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, theimplication is said to be true, or vacuously true. There is certainly noevidence to prove that it is false.

Implication in logic was formalized by William of Ockham, in his bookSumma Logicae in the 14th century. These somewhat convolutedrules add tremendous expressive power to logic and computation. Without themthere 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---------------10Contingent11- 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--------------------10Contingent11- 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 acircuit, knowledge can be said to flow along the wires, where it is transformedby gates and the new knowledge propagates to the next point.

In the circuit annotated above, it is clear what knowledge (facts and deducedfacts) flow in each wire segment. A common mathematical, hence computer sciencetechnique is to represent this type of knowledge flow in specialized type ofgraph 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 collectionof 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 nodesare operators which deduce new facts.

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

When we compare the tree with the logical statement, we see the lowest priorityoperator 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 wiringof 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 ∧ QS = R ∨ QT = ¬ S

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

Each wire in the circuit is named. These are just variable names.Indeed, the first (electronic) computer programs, in the 1940s, weredescriptions 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 aprocessor to compute the values of the equations.In this way, a processor-plus-registers can simulate a circuit, andall computer programs are merely descriptions of circuits in which informationflows 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, whatinformation 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 Sas they travel through the circuit.But this is just tracking the values of the variables in the assignment programwe wrote!The “output variable”/write, named T, has value true.

Just as interesting is that we can analyze the program/circuit before it iscompletely tested.For example, say that the circuit will be inserted into a board where its Pwire 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 andR = 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 ofsubstitution, simplification, and cases analysis.

The point of the previous example is that we can deduce (predict) properties ofthe 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 thatT = ¬Q.Later in the course, we learn deduction rules that calculate this result, notrelying on truth tables.

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

Here, the column underneath OR defines the output.We see this circuit emits false only when P and Q are both true andR 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 variablessaves power, time and material.

This note was adapted from David Schmidt's CIS 301, 2008,Chapter 0course 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.