NAND2GO Chapter 1. Boolean Logic
| 1. Context |
Noam Nisan and Shimo Schocken developed a learning platform from logic gate, the Bottom of computers, to operating system. The first chapter will focus on introducing basic Logic gates. | ||
| 2. Goal |
Let readers know, the Boolean operations belongs to abstract thinking level, how can be associated with the states of physical devices belongs to physical spaces. | ||
| 3. Measurable Effects |
Gates can test successfully on Hardware simulator. | ||
| 4. Outputs | 5. Process | 6. Inputs | |
|
Logic gates build by HDL language. |
Build gates by Nand gates using HDL language developed by Noam Nisan and Shimon Schocken. |
Introduction of Boolean algebra; Basic logic gates; | |
| 7. External Factors | |||
Background
Tens of billions of transistors build modern powerful computers. The function that each transistor can realize is extremely simple, only has two states of high potential and low potential. However, when the extremely large number of these simple transistors are put together, it can achieve very complex operations. As John Ashbery quoted in the first chapter of the lecture on Nand2Tetris, "Such simple things, And we make of them something so complex it defeats us, Almost". So, how these transistors are tied together to achieve so complex calculations? This is one of the questions to be answered in this class. In the first chapter, we will introduce the logic gate and logic operations, these will be used to build the computer's computing unit and storage unit in next chapters. From the first chapter, we will also see that there have never been any numbers in the computer. There are only high level and low level of transistors correspond to the two states of "yes" and "non" of the logic, and only circuits where transistors are connected together with wires, corresponding to the input and output of the logic operation. However, with two logic states and basic logic operations, and they can be repeated countless times, we can finally make complex calculations, as we will see in other chapters.
Boolean algebra
Basic Boolean operators
In Boolean algebra, one of the logical contradictions is assumed to be 0, and the other is assumed to be 1, which digitizes the logical problem. The basic operators of traditional algebra are addition, subtraction, multiplication and division. In Boolean algebra, the basic operators are And, Or, and Not. They can be described as follows:
And(x,y)=1 if x=y=1
And(x,y)=0 otherwise
Or(x,y)=0 if x=y=0
Or(x,y)=1 otherwise
Not(x)=0 if x=1
Not(x)=1 otherwise
These three basic operators are the most basic part of Boolean operations, and can be used to construct any other more complex Boolean operators. However, they are not independent, And operator and Or operator can be expressed as follows:
And(x,y)=Not(Or(Not(x),Not(y))
Or(x,y)=Not(And(Not(x),Not(y))
Boolean functions
Boolean function can be thought of a Boolean operator that describes how to determine Boolean output value based on Boolean input values. It has played a very important role in computer chip design and cryptography. The simplest Boolean functions are Not (x), And (x, y) and Or (x, y), which respectively correspond to the Boolean operators NOT, AND, and OR. Truth table is used to describe these Boolean functions. It lists all possible input values for the Boolean function and gives the corresponding output values. Fig.1 shows the truth table of four Boolean functions: Not (x), And (x, y), Or (x, y), Nand (x, y)
Fig1.1 Truth table(Cited from Nand2Tetris course handout)
For common two-variable Boolean function f (x, y), its truth table is summarized as follows. Since each variable has two possible values of 0 or 1, Four possibilities exist for the two-variable Boolean functions. Fig.2 shows some common two-variable Boolean functions.
Fig 1.2 Two-variable Boolean function(Cited from Nand2Tetris course handout)
According to Boolean logic, we know that complex Boolean operators can be constructed from basic Boolean operators And, Or and Not, while Boolean functions correspond directly to Boolean operators. Therefore, any other Boolean function can be constructed from the basic Boolean functions And (x, y), Or (x, y), Not (x). Since And, Or and Not are not independent, And or Or can be respectively expressed by Or and Not, or And and Not. We can say that Not(x,y) plus one of And(x,y) or Or(x,y), can express any other Boolean function. However, it still need two functions. Is it possible for us to find only one Boolean function that can be used to express any other Boolean functions? The answer is true. For example, we can construct Nand(x,y)=Not(And(x,y)), which has the characteristics of both Not(x,y) and And(x,y). With Nand function, we can construct any other functions, of course include And(x,y), Or(x,y) and Not(x), the there basic Boolean functions, which is showed as follows:
Not(x)=Nand(x,x)
And(x,y)=Not(Nand(x,y))
Or(x,y)=Not(And(Not(x),Not(y))
Logic Gates
Basic Logic Gates
In modern computers, logic gates are the basic components of integrated circuits, which consist of transistors. Logic gates and Boolean functions can be seen as one-to-one correspondence. In this case, the input values of the logic gate correspond to the values of variables of the Boolean function, and the output value corresponds to the value of the Boolean function. There are no number 0 or number 1 in Logic Gates, only two physical states of high potential and low potential. However, number 0 and number 1 can be directly associated with high potential and low potential.
Since complex Boolean functions can be expressed by basic Boolean functions (such as the Nand functions described above), logic gates corresponding to complex Boolean functions can be also assembled by basic logic gates. In this case, for any given input value, we can determine the final operation result of the Boolean function by the last output value of the corresponding logic gate. This is very important, which tells us why computer can carry out complex logic operations. In this way, the Boolean operations, which belongs to abstract thinking level, can be associated with the states of physical devices belongs to physical spaces. In the following chapters, we will see that our familiar algebraic calculations can be realized by Boolean algebra, with the help of binary. Fig.3 shows the relationship between them.
Fig1.3 From Transistor to Algebra Operation(Cited from Nand2Tetris course handout)
Now, we will introduce And Gate, Or Gate and Not Gate, corresponding to And(x,y), Or(x,y) and Not(x). Fig.4 shows the standard symbolic representation of these three logic gates.
Fig1.4 Standard symbolic representation of Logic gates(Cited from Nand2Tetris course handout)
Standard symbols facilitate the intuitive expression of the type of logic gate, but can’t see the function of the logic gate directly from the symbol. In order to clearly express the function of each logic gate, we can also use the programmatic language to describe the logic gate. In general, Out represents the output value of the logic gate. When there is only one input value, use In to represent the input value. When there are two or more input values, we can use a, b, c ... respectively. Logic gate represents the correspondence between the input value and the output value. In this way, we can describe Not Gate, And Gate and Or Gate as follows:
Not gate: out=not in
And gate: out=1 if(a==1.b==1) out=0 othersise
Or gate: out=0 if(a==0.b==0) out=1 othersise
From the basic logic gates above, we can construct any complex logic gates. For example, we construct an ‘AND’ Gate with three input values. The standard symbol is shown in Fig.5(a), and how it is implemented by basic logic gates is shown in Fig.5(b). We can also use the programming language to describe it: out=1, if ((a ==1 and b==1) and (c==1)). Otherwise, out=0.
Standard_symbolic_representation_of_Logic_gate(b)Implementation_of_logic_gate.png){kind=link}
Fig1.5 (a)Standard symbolic representation of Logic gate(b)Implementation of logic gate(Cited from Nand2Tetris course handout)
Circuit implementations
Section 1.3.1 introduces the symbolic representation and programming language representation of logic gates. However, in order to know the details to produce logic gates, we need to know how to describe logic gates by using physical devices. We know that we can use two stages of switch, on and off, to represent the high potential and low potential of transistor. Then, we can connect switches as shown in Fig.6, and let them represent the basic logic gate. We can simply verify that the output of these circuits corresponds exactly to the output of logic gates. Therefore, the basic logic gate can be realized by corresponding circuits. From section 1.3.1 we know that the complex logic gates can be built by basic logic gates. So, we can represent any logic gates by using these circuits in fact.
Fig 1.6 Circuit implementations(Cited from Nand2Tetris course handout)
Fig1.7 Boolean algebra be implemented by switching circuits (cited from Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. Electrical Engineering, 57(12), 713-723.)
From another point of view, the output of logic gates is equivalent to the output of corresponding Boolean function. For each specific Boolean function, we can build corresponding circuits to implement it. This is a very important way to solve problems with computational thinking. The first person to elaborate on this method is Claude Shannon. In 1938, he proposed that Boolean algebra can be implemented by switching circuits in his master's thesis, which made Boolean algebra become the foundation of digital circuits.
Build other Gates by Nand
The three basic gates, Not Gate, And Gate and Or Gate, can’t construct other gates alone. If there is no Not Gate, there is no opposite status. If there is no And Gate or Or Gate, it can’t deal with two or more input values. However, because Nand gate has the characteristics of both Not Gate and And Gate, it can be used to construct any other gates, as stated in section 1.2.2. In this way, we just need to build only one kind of logic gate theoretically, which will be very convenient and economical in production process.
The homework of this chapter is to build other gates by Nand gate. Here, we take the Nand gate as a build-in gate and a basic module, to build Not gate, And gate, Or gate, Xor gate, Mux gate and etc.
Not gate
From section 1.2.1 we know Not(a)=Nand(a,a). Because Boolean function corresponds to Logic gates, we can use Nand gate to build Not gate. Using HDL language developed by Noam Nisan and Shimon Schocken, we can describe Not gate in this way:
CHIP Not {
IN in;
OUT out;
PARTS:
// Put your code here:
Nand (a = in, b = in, out = out);
}
The primary structure of HDL language describing Not gate shows in Fig.8. The reader can learn more about the HDL language based through appendix references. In the HDL simulator built by Noam Nisan and Shimon Schocken, the Nand Gate is built-in and it can be called directly when writing HDL languages. When constructing a logic gate with other functions, we can take quite the same steps. Firstly, Express the Boolean function corresponding to the logic gate need to be built by other Boolean functions corresponding to those logic gates has been built. Then, according to syntax rules of HDL, Converted it to HDL language. Once done, test it on the HDL simulator to verify if it is constructed successfully.
Fig1.8 The structure of HDL language to describe Not gate
And gate
In the same way,according to Boolean function And(a,b)=Not(Nand(a,b)). We can describe And gate:
CHIP And {
IN a, b;
OUT out;
PARTS:
// Put your code here:
Nand(a = a,
b = b,
out = x);
Not(in = x, out =out);
}
Because Not gate has been built in (1) of section 1.3.3, we don’t need to describe it again using HDL language when building And gates. Noam Nisan and Shimon Schocked took this into consideration when building the HDL simulator, all previously built logic gates can be used directly when build current logic gates, in order to avoid cumbersome repetition.
Or Gate
In the same way, according to Boolean function Or(a,b)=Not(And(Not(a),Not(b))). We can describe And gate:
CHIP Or {
IN a, b;
OUT out;
PARTS:
// Put your code here:
Not(in=a, out=na);
Not(in=b, out=nb);
And(a=na, b=nb, out=x);
Not(in=x,out=out);
}
Xor
Xor gate can achieve this function:
out = not (a == b).
Firstly, by deducing, we can get
Xor=Or(And(a,Not(b),And(b,Not(a)))).
According to this expression, we can use HDL language to describe Xor gate:
CHIP Xor {
IN a, b;
OUT out;
PARTS:
// Put your code here:
Not (in=a, out=nota);
Not (in=b, out=notb);
And (a=a, b=notb, out=x);
And (a=nota, b=b, out=y);
Or (a=x, b=y, out=out);
We just give four examples to build logic gates by Nand gate. Readers can construct other logic gates in project 1 of Nand2Tetris for practice. There are many ways to construct logic gates. The result can be tested with HDL simulator.
Pespective
In this chapter, we learned Boolean algebra and logic gates. We see that the Boolean algebra, which belongs to abstract thinking level, can be associated with the states of physical devices belongs to physical spaces. Based on this, the computer can achieve Boolean algebra operations, and then achieve general algebraic operations using binary algorithm.
We can build a little more complex logic gate by Nand gate. In the following chapter, these logic gates will be used to build the most important part of a modern computer, CPU. As we mentioned above, there are many ways to build logic gates and we can test if it is correct or not by HDL simulator. However, the optimal method may be only one, and it determines the effi ciency of the logic gates to achieve required functions. The amount of such components in a computer is staggering. If the efficiency of a component is not optimal, the wasting computational resources will eventually be enormous. Therefore, the optimization of various basic devices, is extremely important in actual design and production process.
Glossary
Computer
Boolean algebra
Logic gate
Transistor
Circuit
References
- Nand2teris, Temporary link failure, Refer to lecture 1
- Nand2teris, Temporary link failure, Refer to chapter 1
- wikipedia, https://en.wikipedia.org/wiki/Transistor, Transistor
- wikipedia, https://en.wikipedia.org/wiki/Logic_gate, Logic_gate
- wikipedia, https://en.wikipedia.org/wiki/Boolean_algebra, Boolean_algebra
- wikipedia, https://en.wikipedia.org/wiki/George_Boole, Personage introduction of George_Boole
- wikipedia, https://en.wikipedia.org/wiki/Claude_Shannon, Personage introduction of Claude_Shannon
Additional Reading Material
- Nand2teris, Temporary link failure, Appendix A: Hardware Description Language (HDL)