reveal.js

## Logic Gates and Truth Tables

---

CS 130 // 2025-10-01

## Vermeer Digital Bulldogs

https://www.drake.edu/cs/internships/vermeerdigitalbulldogs/

Deadline is October 15th

### Preparing for part 2 of the course

We will soon be using a digital logic simulator called Logisim-Evolution

* [Information here](https://github.com/logisim-evolution/logisim-evolution)
* [Download here](https://github.com/logisim-evolution/logisim-evolution/releases/tag/v3.7.2) - make sure to get v3.7.2
  - **jar** file: should work for anyone (similar to MARS)
  - **msi** file: installer for Windows (you probably want x86 version)
  - **dmg** file: installer for Mac (may or may not work for M1/M2/M3 Macs)

# Course Themes

## Overarching Theme
- Learning how a high-level program is actually executed on your computer's processor

![Compiler-Assembler Diagram](/Fall2025/CS130/assets/images/COD/compiler-assembler.png)

## Trajectory of the Course
1. Assembly language programming
2. **Digital logic**
3. Processor architecture
4. The C Programming Language

## Basic CPU Operations
- Recall that most operations operate on one or more 32-bit registers
    + 
 `add $s0,` `$s1`, `$s2` takes two 32-bit numbers, adds them up, and produces a new 32-bit number
- 
 How can we build a machine that takes 0s and 1s as input and produces 0s and 1s as output?

# Digital Logic

NOTE: Discuss how hard electrical engineering is and why it is so useful to focus on the simplicity of digital logic

## Transistors
- CPU instructions are implemented with nanoscale switches called **transistors**

![Light bulb](https://makercise.com/wp-content/uploads/2015/11/vlcsnap-2015-11-17-20h50m57s882.png.jpg)

</div>
<div>

You can think of a transistor as a "switch" with states "on" and "off"

</div>
</div>

## Digital Logic
- Learning about electricity, capacitors, resistors, is beyond the scope of this course
- 
 For now, it is useful to abstract away the details of electrical engineering
- 
 We will think about circuits in terms of 0s and 1s going through the wires of a circuit

## Input/Output as Voltages
<div class="twocolumn">
<div>

- The 0s and 1s of our circuits will be "low" and "high" voltages across a wire, similar to a light bulb being "on" and "off"

</div>
<div>

![Bits as light bulbs](https://miro.medium.com/max/2400/1*Um-qKrB2QLxRU0C8CkCCeg.png)

</div>
</div>

## Logic Gates
- A **logic gate** is an elementary circuit that takes one or more bits as input and produces one or more bits as output
- 
 Many of these logic gates can be constructed with one or two transistors

## AND Gate

<table>
  <tbody>
    <tr>
      <td>Input 1</td>
      <td>Input 2</td>
      <td>Output</td>
    </tr>
    <tr>
      <td>0</td>
      <td>0</td>
      <td>0</td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
      <td>0</td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
      <td>0</td>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>1</td>
    </tr>
  </tbody>
</table>

![AND Gate](/Fall2025/CS130/assets/images/gates/and.png)

## OR Gate

<table>
  <tbody>
    <tr>
      <td>Input 1</td>
      <td>Input 2</td>
      <td>Output</td>
    </tr>
    <tr>
      <td>0</td>
      <td>0</td>
      <td>0</td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
      <td>1</td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>1</td>
    </tr>
  </tbody>
</table>

![OR Gate](/Fall2025/CS130/assets/images/gates/or.png)

## NOT Gate

<table>
  <tbody>
    <tr>
      <td>Input</td>
      <td>Output</td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
    </tr>
  </tbody>
</table>

![NOT Gate](/Fall2025/CS130/assets/images/gates/not.png)

## NAND Gate

<table>
  <tbody>
    <tr>
      <td>Input 1</td>
      <td>Input 2</td>
      <td>Output</td>
    </tr>
    <tr>
      <td>0</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
      <td>1</td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>0</td>
    </tr>
  </tbody>
</table>

![NAND Gate](/Fall2025/CS130/assets/images/gates/nand.png)

## NOR Gate

<table>
  <tbody>
    <tr>
      <td>Input 1</td>
      <td>Input 2</td>
      <td>Output</td>
    </tr>
    <tr>
      <td>0</td>
      <td>0</td>
      <td>1</td>
    </tr>
    <tr>
      <td>0</td>
      <td>1</td>
      <td>0</td>
    </tr>
    <tr>
      <td>1</td>
      <td>0</td>
      <td>0</td>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>0</td>
    </tr>
  </tbody>
</table>

![NOR Gate](/Fall2025/CS130/assets/images/gates/nor.png)

## XOR Gate

![XOR Gate](/Fall2025/CS130/assets/images/gates/xor.png)

(exclusive OR)

### Demo: What is the truth table for the following circuit?

---

![Simple circuit](/Fall2025/CS130/assets/images/gates/simple-circuit.png)

</div>
<div>

</div>
</div>

#### Exercise

1. Fill out the truth table
2. Describe what the circuit does using words

![Simple circuit](/Fall2025/CS130/assets/images/gates/xorcise.png)

</div>
<div>

</div>
</div>

*NB:* a filled dot where wires cross means that the wire splits. If no dot appears, it means one wire is routed over the top of the other.

### Symbolically describing a circuit

![Simple circuit](/Fall2025/CS130/assets/images/gates/simple-circuit.png)
 
  </div>
  <div>
  $$D = \overline{(A\cdot B)} + (B \cdot C)$$
  </div>
</div>

- $\overline{A}$ "not $A$"
- $\cdot$ "and"
- $+$ "or"

### Exercise

Symbolically describe the circuit

![Simple circuit](/Fall2025/CS130/assets/images/gates/xorcise.png)

### Exercise

1. Draw a circuit representing the logic symbols
2. Write the truth table for the circuit

$$ C = (A \cdot \overline{S}) + (B \cdot S) $$

### Challenge Exercise

Can you come up with a circuit that has this truth table?
- A, B, and C are inputs
- E is an output

Verbally describe what this circuit does.

Write the logic symbols representing this circuit.

</div>
<div>

</div>
</div>