Turing Complete – Basic Logic Manual

A truth table is a table that assigns each combination of truth values of all variables in an expression with logical operator(s) to a truth value. The following are the truth tables of three common logical operators: NOT, AND and OR.
Negation (NOT): the opposite of the truth value of a variable (denoted by [A])

Conjunction (AND): true if both two variables are true (denoted by AB)

Disjunction (OR): true if one of two variables is true (denoted by A+B)

Notes: If no parenthesis is used, the priority of operation always follows the order: negation, conjunction, disjunction and from left to right if in the same order. For example, A[B]C+[A] equals ((A([B]))C)+([A]).

Boolean algebra is a binary operation structure that consists of logical variables, constants 0 and 1, and logical operations AND, OR and NOT satisfying the following properties:

In the game, we can optimize our design by using the properties above to minimize the number of logic gates and delay. For example, we can use the distributive property to reduce the number of logic gates we use from three to two.

De Morgan’s laws allow us to convert AND, OR, NAND, or NOR gates into another. Circuits in the same color are logically equivalent (have the same truth value). Output is inverted when we convert gates between left and right. Input is inverted when we convert gates between top and bottom.

For every logic circuit, we can use AND or OR gates to accurately control the circuit’s conditions, which means we can freely assign which combinations of truth values to 1. Due to the associative and commutative property, the order of operations and inputs has no effect on the result of a circuit when any number of AND gates (or OR gates) are used individually. So,

Use AND gates when all conditions are required.

Use OR gates when one of conditions is required.

A Karnaugh map is the truth table used for the simple analysis of a logic circuit with two up to four inputs. The head of rows or columns of a Karnaugh map represents every possible combination of truth values of input (usually pairs of input appears in the head of either rows or columns) respectively. Each intersection of a row and a column represents the truth value to which the corresponding combination is assigned. For example, in a four-variable Karnaugh map,

The truth value in the third row and the fourth column shows the output is 1 when the input A,B,C,D are 1,0,1,1 respectively. So we can write down the conjunction of each condition of input:

• A[B]CD

Similarly we have the rest of all conditions that make the output be 1:

• [A]B[C]D
• [A]BC[D]
• [A]BCD
• AB[C]D

Finally we get the Boolean sum of products of this truth table by writing down the disjunction of all the conjunctions listed above:

• [A]B[C]D+[A]BC[D]+[A]BCD+A[B]CD+AB[C]D

Let X,Y be Boolean expressions. Based on the operation laws, we have

• XY+X[Y]=X(Y+[Y])=X1=X

Therefore we can simplify the expression of any form XY+X[Y] to X. For example, in the sum of products mentioned above, we have

• [A]BC[D]+[A]BCD=[A]BC (X=[A]BC, Y=D)
• [A]B[C]D+AB[C]D=B[C]D (X=B[C]D, Y=A)

Replace the original terms with these, we have

• [A]BC+A[B]CD+B[C]D

Based on the distributive property, we can simplify the terms containing either B or D as needed. If we want to simplify the terms containing B, we have

• B([A]C+[C]D)+A[B]CD

This logic circuit requires three NOT gates, six AND gates and two OR gates. Readers can check the result.

Although Boolean sums of products cannot guarantee the optimal design, it helps us figure out designs that satisfy the condition of complex logic circuits.