<h1class="courselink">Build A Modern Computer from First Principles</h1>
<h2class="lecturer">Coursera</h2>
<h2class="episodetitle">Week 1</h2>
</div>
<article>
<p>The software for the course can be dowmloaded from <ahref="http://nand2tetris.org/software.php">here</a>.</p>
<h2class="episodetitle">Module 1: Boolean Functions and Gate Logic Roadmap</h2>
<p>In this module, we will be looking at Boolean algebra and the implementation of Boolean functions using logic gates. We will also learn how to use a Hardware Description Language (HDL) to specify gates and chips. This will lead on to project 1 where we will build, simular and test 15 elementary logic gates which will later be used to build the ALU for our computer.</p>
<p>We can extend Boolean logic to express Boolean functions such as</p>
<preclass="inset">f(x, y, z) = (x AND y) OR (NOT(x) AND z)</pre>
<p>As an example, let's assume that x = 1, y = 1 and z = 0. If we start by evaluating the expression in the first parentheses (let's call that subexpression 1), a AND y, this returns a 1 and we can actualy stop there because whether the expression in the second parentheses (subexpression 2) returns a 1 or a 0, the overall expression will return a 1. We know this because, regadrless of how complex the expressions in the parentheses might be, it comes down to an OR statement where the result of the expression will return a 1 if either subexpression 1 or subexpression 2 returns a 1. We already know that the subexpression 1 returns a 1 so the whole expression must return a 1.</p>
<p>Let's try another example where x = 0, y = 0 and z = 1. This time subexpression 1 returns a 0. In essence, that means whatever value is returned by subepxression 2 will be returned by the expression. In other words, if subexpression 2 returns a 0, the expression becomes 0 OR 0 and so 0 is returned. If it returns a 1, the expression becomes 0 OR 1 and a 1 is returned. Subexpression 2 has two stages. The first is NOT(x) which in this case returns a 1. We then take this value and AND it with z which gives us 1 and 1 so subexpression 2 returns a 1.</p>
<p>This means that the expression simplifies down to 0 OR 1 and so it returns a 1.</p>
<p>These results tell us a little bit about the function but if we want to know precisely what this function is doing (that is, what is it for) a useful starting point is to list all the possible input and all the possible outputs.</p>
<preclass="inset">
x y z f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1</pre>
<p>So, here we have essentially two definitions of the same expression, the first in the form of a formula and the second in the form of a truth table</p>
<p>Boolean logic contains some of the same laws as are found in arithmetic.</p>
<h3>Commutative Laws</h3>
<preclass="inset">
• (x AND y) = (y AND x)
• (x OR y) = (y OR x)</pre>
<h3>Associative Laws</h3>
<preclass="inset">
• (x AND (y AND z)) = ((x AND y) AND z)
• (x OR (y OR z))= ((x OR y) OR z)</pre>
<h3>Distributive Laws</h3>
<preclass="inset">
• (x AND (y OR z)) = (x AND y) OR (x AND z)
• (x OR (y AND z)) = (x OR y) AND (x OR z)</pre>
<h3>De Morgan Laws</h3>
<preclass="inset">
• NOT(x AND y) = NOT(x) OR NOT(y)
• NOT(x OR Y) = NOT(x) AND NOT(y)</pre>
<p>We can use these idenities to simplify or change a Boolean expression.</p>
<p>Example</p>
<preclass="inset">NOT(NOT(x) AND NOT(x OR y))</pre>
<h3>Step 1</h3>
<p>We can useDe Morgans law to change the last part of the expression - the NOT(x OR y). We can express this as NOT(x) AND NOT(y) so this gives us</p>
<preclass="inset">NOT(NOT(x) AND NOT(x) AND NOT(y))</pre>
<p>According to the associative law, we can evaluate the part in the brackets as NOT(x) AND (NOT(x) AND NOT(y)) or (NOT (x) AND NOT(x)) AND NOT(y). If we take the latter expression, this means that we will start by evaluating NOT(x) AND NOT(x)</p>
<p>Now, if x = 0, NOT (x)=1</p> NOT(x) AND NOT(x) will also return 1 (since we are effectively ANDing x with itself the result is x) so similarly, if x = 1, NOT(x) will return 0 as will NOT(x) AND NOT(x) so we can rewrite NOT(x) and NOT(x) as simply NOT(x). This is referred to as the Idempotence Law. Our formula then becomes
<preclass="inset">NOT(NOT(x) AND NOT(y))</pre>
<p>Here, we can use De Morgans Law again so the expression becomes</p>
<preclass="inset">NOT(NOT(x) OR NOT(NOT(y))</pre>
<p>The next part should be fairly obvious. NOT(x) inverts the value of x so 0 becomes 1 and 1 becomes 0. NOT(NOT(x)) inverts it twice so 0 becomes 1 becomes 0 and 1 becomes 0 becomes 1 (the Double Negation Law). So, we can say that NOT(NOT(x)) is just x and the same applies for y so our expression then becomes</p>
<preclass="inset">x OR y</pre>
<p>Now, let's consider the truth table for this expression. We will assume that f is the result of evaluating the expression</p>
<preclass="inset">
x y f
0 0 0
0 1 1
1 0 1
1 1 1</pre>
<p>This shows us that the expression is equivalent to x OR y since it produces the same truth table.</p>
<p>A truth table won't always give you a clear and obvious result as we have here, so sometimes a bit of algebraic manipulation may be required and this manipulation may also not yield a nice simple result, we may well end up with a complicated formula. However, both techniques allow to find alternative forms of the same Boolean expression.</p>
<h2class="sectiontitle">Unit 1.2: Boolean Function Synthesis</h2>
