From Puzzles to Programming

This has nothing to do with puzzles or programming, but knowledge about puzzles or programs will not be complete without mentioning digital logic. Digital logic is the study that allows the design of digital circuits and other digital systems such as adders, multipliers, and so on. Once you know its basics, you will find it easy and as entertaining as solving logic puzzles or mathematical problems. It uses a mathematical discipline known as Boolean algebra. The name is in the honor of an English mathematician George Boole who proposed the basic principles of this algebra in 1854. Almost one century later, Claude Shannon, a research assistant at M.I.T, suggested the use of Boolean algebra to solve problems in relay-switching circuit design. His techniques were subsequently used in the analysis and design of many electronic digital circuits.

Boolean algebra makes use of logical variables (also called operands) and operations. Since we are dealing with binary data, a variable may take on the value 1 (true) or 0 (false) - as long as quantum computers are under research, we will keep using the binary system, of course referring to the on/off conditions of transistors in the current computers. The basic logical operations are AND, OR, and NOT. These will be symbolically represented as ^, +, and ' respectively:

A AND B = A^B yields 1 or 'on' (true) if and only if both of its operands are 1 (true)    

A OR B = A + B yields 1 (on or true) if either or both operands are  1 (true).

NOT A = A' inverts the value of its operand.

Other operations include NAND which functions as the complement or NOT of the AND function:

A NAND B = NOT(A AND B) = (A^B)' and NOR that functions as the complement or NOT of OR: A NOR B = NOT(A OR B) = (A+B)'

Another operation is the exclusive-or (XOR) of two operands is 1 (true) if and only if exactly one of the operands is 1. The following table shows the values produced by the different operations on the variables A and B:

 

A	B	NOT A	A^B	A+B	A XOR B	A NAND B	A NOR B
0	0	1	0	0	0	1	1
0	1	1	0	1	1	1	0
1	0	0	0	1	1	1	0
1	1	0	1	1	0	0	0

 

Basic Laws in Boolean algebra:

Commutative Laws: A ^ B = B ^ A; A + B = B + A

Distributive Laws: A^(B+C) = (A^B)+(A^C);

                   A+(B^C) = (A+B)^(A+C);

Identity Laws:     A^1 = A;  0+A = A;

Inverse Laws:      A^A’ = 0; A^A’ = 1;

Others: 0^A = 0; 1+A = 1; A^A = A; A+A = A

Associative Laws: A^(B^C) = (A^B)^C; A+(B+C) = (A+B)+C

DeMorgan’s Theorem: 1- (A+B)’ = A’^B’; 2-(A^B)’ = A’+B’;

A proof for the first DeMorgan’s theorem is as follows:

If we prove that (A+B)+(A’^B’) = 1 and (A+B)^(A’^B’) = 0 then (A+B)’ = A’^B’ by the inverse laws.

(A+B)+(A’^B’) = ((A+B)+A’)^((A+B)+B’) distributive laws

              = (B+(A+A’))^(A+(B+B’)) associativity and commutativity

              =  (B+1)^(A+1) = 1^1 = 1

Similarly, (A+B)^(A’^B’) = 0, and so (A+B)’ = A’^B’

Also, the second DeMorgan’s theorem can be proved in the same way.

The design and implementation of digital circuits are simpler if only one or two types of gates are used. For example AND, and Not can form OR operation. This can be done by simply using DeMorgan’s law: (A+B)’ = A’^B’ and in other words, A+B = (A’^B’)’.

Can the operations AND, OR, and NOT be implemented solely with NAND gates?

The answer is yes. The NAND as we said earlier is NOT(AND). It is like a combination of these operations, and both can generate OR. Hence, it is possible to generate all the other 3 gates from only NAND gate. The below figure demonstrates this. Actually, for this reason, the digital circuits are frequently implemented with NAND gates.