1.1 How to build circuit out of truth table

• SOP (Sum-of-Product rule): Find the rows of truth table where output is 1. Get the product(AND) of the inputs. Sum(OR) them with the other rows where output is 1.
  • Intuition is AND is more restrictive: you first target the results individually with AND gate then your combine each of the results with the OR gate.
• BUT What if we had more than 1 output? Pretend as if there were 2 truth tables with 1 output, then use the SOP rule on each of the truth tables.

3.1 Describing RELAYS

• “Relay default on”
  • 2 Ordered Inputs : C and IN
  • 1 Output
  • Relay_default_on :: (2 Ordered Inputs) -> (1 Output)
  • Relay_default_on := (NOT C) /\ IN
• “Relay default off”
  • 2 Ordered Inputs : C and IN
  • 1 Output
  • Relay_default_off :: (2 Ordered Inputs) -> (1 Output)
  • Relay_default_off := C /\ IN

3.2 Level NAND

The question is how do we build NAND using Relay_default_on and Relay_default_off?

1. First translate NAND into basic symbols
   

• NOT (A /\ B)

2. Write out available tactics AKA logical equations of “Relay_default_on” and “Relay_default_off”. These logical equations are analogous to term introduction rules in a proof true.

• Rule1: Given any symbols C, IN: we can build term (NOT C) /\ IN
• Rule2: Given any symbols C, IN: we can build term C /\ IN

3. Write out available variables, These variables are analogous to inexhaustable assumptions in a proof tree

• VARIABLES: A B Power

4. Build the solution via the variables
5. A /\ B via Rule2
6. (NOT (A /\ B)) /\ Power via Rule1 applied to 1.
7. Translate back rule into relays
8. Connect A and B to Relay_default_off aka Rule2
9. Connect output of step 1 into C and Power to IN in Relay_default_on aka Rule1

\[\cfrac{C \qquad IN}{\lnot C \land IN}\tag{Relay_default_on}\] \[\cfrac{C \qquad IN}{C \land IN}\tag{Relay_default_off}\] \[\cfrac{X \land Power}{X} \qquad \cfrac{Power \land X}{X} \tag{Logical Reduction Rules}\]

\[\cfrac{\cfrac{A \qquad B}{A \land B}\qquad Power}{\cfrac{\lnot (A \land B) \land Power}{\lnot (A \land B)}}\]

3.3 Level Half-adder

• GOAL: half-adder :: 2 Ordered Inputs -> 2 Ordered Outputs
• VARIABLES: A B
• Understand the MAX/MIN of the problem:
  • The MIN output is 0 and the MAX output is 2 or “10” in binary
  • This means there are 3 states needed for the output, 00, 01, 10
    • Information theory: in theory we can make 8 states just by connecting A to High Output, B to Low Output.
      • Since the problem actually has 3 output, clearly we need some Gates that reduces information.
        Gates like AND, OR, XOR, reduces information into 2 states 0,1.
        If we use 2 Gates one for High-bit, one for Low-bit we can in-theory get MAX 4 states
        BUT our GOAL is 3 states so clearly we need find 2 gates that has 2 rows or 2 Overlapping states in the truth table
• Solution:
  • High-bit := A AND B
  • Low-bit := A XOR B

\[\cfrac{X \qquad Y}{X \land Y} \qquad \cfrac{X \qquad Y}{X \oplus Y} \tag{and-rule xor-rule}\] \[ \cfrac{\cfrac{\cfrac{A \qquad B}{A \land B}}{Hi} \qquad \cfrac{\cfrac{A \qquad B}{A \oplus B}}{Low}}{(Hi,Low)_{Adder}}\tag{the solution of built circuit}\]

Extra stuff using the Adder circuit via elimination rules:

\[ \cfrac{\pi_1(Hi,Low)_{Adder}}{Hi} \qquad \cfrac{\pi_2(Hi,Low)_{Adder}}{Low}\]

3.4 Full Adder

• GOAL: full-adder :: 3 Ordered Inputs -> 2 Ordered Outputs
• VARIABLES: A B C
• Understand the MAX/MIN of the problem:
  • The MIN output is 0 and the MAX output is 3 or “11” in binary
• Take halfadder of A,B then take resultant low bit and halfadder it to C, then the low bit of that is the low bit.
  Take the high bit of both half adders than OR them to get the high bit.

3.5 Multi-bit Adder

• Before our Adders only added 1-bit numbers, but what if we want to add 2-bit numbers with a 1-bit carry number like “11”+“11”+“1” = “111”
• Use 2 full adders