15-110 Spring 2011
Honors/Bonus Notes:  Arithmetic as Logic

• Topics
• Part 1:  Automating Logic with Circuits
• xLogicCircuits (run online here or download the jar file to run offline here).  You cannot save files when running online.
• Association between boolean logic expressions, truth tables, and circuits
• Disjunctive Normal Form (DNF)
• Expressing any boolean logic expression using just and/or/not (with DNF)
• Define "row selectors" where expression is true (1).  These are really conjuncts of variables and their negations.
• "or" together the "row selectors".  This is really a disjunct of those conjuncts.
• Key:  for any boolean logic expression, you can build a physical circuit that computes that expression using just and/or/not gates.  Incredible!
• Corollary:  Because of this, any programming language just needs to provide and/or/not operators to be able to define any logical function in that language.  So that's why they do that!
• DeMorgan's Law (both versions)
• A and B == not ((not A) or (not B))
• A or B == not ((not A) and (not B))
• Using DeMorgan's Law to convert an and/or/not expression into either an or/not or an and/not expressions
• The Nor and Nand logical operators
• Expressing or/not expressions as just nor (or just nand) expressions
• Key:  for any boolean logic expression, you can build a physical circuit that computes that expression using just nor (or nand) gates.  Amazing!
• not A == A nor A
• A or B == not (not (A or B)) == not (A nor B) == (A nor B) nor (A nor B)  (tada!)
  
  
• Part 2:  Arithmetic as Logic (which then can be automated using circuits)
• 1-Bit Addition
• Input:  two one-bit binary values, A and B.
• Output:  one two-bit binary value, C (with bits C1 and C2), where C = A + B.
• Key:  We convert arithmetic to logic by viewing each bit C1 and C2 as its own function.  Wow!
• C1 = A and B
• C2 = A xor B
• Half Adder
• The circuit we just defined is called a "half adder"
• Full Adder
• Input:  three one-bit binary values, A and B and C
• Output:  one two-bit binary value D (with bits D1 and D2), where D = A + B + C
• Can be constructed using two half-adders and one or gate.
• Key:  a full adder models the process of adding one column in the standard addition algorithm
• The 3 inputs are the 2 corresponding digits from the numbers being added plus the carry digit from the preceding column.
• The 2 outputs are the solution digit for this column (D2) and the carry digit for the next column (D1).
• K-Bit Adder
• Daisy-Chaining:  Connecting the carry output from each full adder to the next full adder's input.
• xLogicCircuits contains a sample 4-bit adder, but we could trivially extend this to a 32-bit adder or larger.
• Conclusion:  we have reduced 32-bit addition to logic which we then can automate as physical circuits.  Wahoo!
• The next steps (if we had time, which we did not, and which we did not cover, and which are you not responsible for):
• memory (how do we store and retrieve data?),
• machine architecture (how do we make a general-purpose computer)
• machine language (how do we program that general-purpose computer)
• compilers (how do we program that general-purpose computer in a more human-understandable way?)
• virtual machines and interpreters (how do we program in a very-high-level and platform-independent way?)
• Which leads us to...  Python (and Javascript and Java and Ruby and Groovy and...) 
• So there are one or two missing pieces in understanding how your Python programs are automated by some electricity and a bucket of sand (ok, a silicon wafer), but at least we covered how to use those things to add two numbers!