reveal.js

# Combinational Logic

---

CS 130 // 2025-10-06

# Digital Logic Review

<!--

### Who came up with these logic gate diagrams?

https://hsm.stackexchange.com/questions/3037/the-origin-of-logic-gate-symbols
- in short: we're not sure 
- they probably developed by convention over time

A student told me that he saw something that traced them back to George Boole - the inventor of Boolean Algebra

-->

## Boolean Algebra
- We can represent logic gate computations as using **Boolean algebra**
- 
 $\overline{A}\cdot B+A\cdot C$ means the same thing as:
    + `((not A) and B) or (A and C)`

## Universal Gates
- The **NAND** gate and the **NOR** gate are "universal" and can be used to construct every other gate
- Using only **NAND** gates, construct circuits that are equivalent to NOT, AND, and OR gates

![NOT from NAND](/Fall2025/CS130/assets/images/NOT_from_NAND.png)
![AND from NAND](/Fall2025/CS130/assets/images/AND_from_NAND.png)
![OR from NAND](/Fall2025/CS130/assets/images/OR_from_NAND.png)

### Multiplexor From Last Time

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

![Multiplexor Circuit Diagram](/Fall2025/CS130/assets/images/multiplexor_diagram.png)

</div>
<div>

</div>
</div>

#### Demo: Designing and Testing Circuits with Logisim

[Installing Logisim](../../resources/installing-logisim/)

![Multiplexor Circuit Diagram](/Fall2025/CS130/assets/images/logisim_multiplexor.png)

# Combinational Logic

## Combinational Logic
- **Combinational** logic circuits don't have memory
    + 
 Output depends on only the input
    + 
 Can be completely specified by a truth table
- 
 **Sequential** logic circuits do have memory
    + 
 Output depends on both the input and current state of memory

## Sum of Products Form
- All combinational circuits can be converted to a **sum of products** form that makes them especially easy to implement with gates

---

- 
 Need to identify the 1s in the output
- 
 Construct a product term such as $\overline{A}\cdot\overline{B}\cdot C$ for each 1 in output
- 
 "Sum" them together

</div>
<div style="font-size: 60%">
<table>
  <tbody>
    <tr> <th>A</th> <th>B</th> <th>C</th> <th bgcolor="lightgray"></th> <th><b>D</b></th> </tr>
    <tr> <th>0</td> <td>0</td> <td>0</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td>0</td> <td>0</td> <td>1</td> <td bgcolor="lightgray"></td> <td><b>1</b></td> </tr>
    <tr> <td>0</td> <td>1</td> <td>0</td> <td bgcolor="lightgray"></td> <td><b>1</b></td> </tr>
    <tr> <td>0</td> <td>1</td> <td>1</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td>1</td> <td>0</td> <td>0</td> <td bgcolor="lightgray"></td> <td><b>1</b></td> </tr>
    <tr> <td>1</td> <td>0</td> <td>1</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td>1</td> <td>1</td> <td>0</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td>1</td> <td>1</td> <td>1</td> <td bgcolor="lightgray"></td> <td><b>1</b></td> </tr>
  </tbody>
</table>
</div>
</div>

### Example

<div class="twocolumn" >
<div>
  
<span style="color:blue" class="fragment">$\overline{A}\cdot\overline{B}\cdot C$ </span> <span class="fragment" >+</span> <span style="color:red" class="fragment">$\overline{A}\cdot B\cdot \overline{C}$ </span>  <span class="fragment" >+</span>  <span style="color:skyblue" class="fragment">$A \cdot \overline{B}\cdot \overline{C}$ </span>  <span class="fragment" >+</span>  <span style="color:orange" class="fragment">$A \cdot B \cdot C$ </span>

</div>
<div style="font-size: 60%">
<table>
  <tbody>
    <tr> <th>A</th> <th>B</th> <th>C</th> <th bgcolor="lightgray"></th> <th><b>D</b></th> </tr>
    <tr> <th>0</td> <td>0</td> <td>0</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td style="color:blue">0</td> <td style="color:blue">0</td> <td style="color:blue">1</td> <td bgcolor="lightgray"></td> <td style="color:blue"><b>1</b></td> </tr>
    <tr> <td style="color:red">0</td> <td style="color:red">1</td> <td style="color:red">0</td> <td bgcolor="lightgray"></td> <td style="color:red"><b>1</b></td> </tr>
    <tr> <td>0</td> <td>1</td> <td>1</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td style="color:skyblue">1</td> <td style="color:skyblue">0</td> <td style="color:skyblue">0</td> <td bgcolor="lightgray"></td> <td style="color:skyblue"><b>1</b></td> </tr>
    <tr> <td>1</td> <td>0</td> <td>1</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td>1</td> <td>1</td> <td>0</td> <td bgcolor="lightgray"></td> <td><b>0</b></td> </tr>
    <tr> <td style="color:orange">1</td> <td style="color:orange">1</td> <td style="color:orange">1</td> <td bgcolor="lightgray"></td> <td style="color:orange"><b>1</b></td> </tr>
  </tbody>
</table>
</div>
</div>

## Exercise: Sum of Products

</div>
<div>

- Write-out the sum-of-products for this truth table
   + Inputs are A, B, C. 
   + Outputs are Y1, Y0
  - Draw the circuit by hand
  - Draw the circuit in Logisim
   + Manually test some inputs
  - Create a run test vector

*NB:* circuits built from the sum-of-products have two stages - ANDs then ORs
  - this is called a **programmable logic array** or PLA

</div>
</div>

## Assignment

- [Assignment 4](../../assignments/assignment-4/)
  - Given a truth table, design a circuit
  - Use sum-of-products
  - implement it in Logisim
  - test it with a test vector
  - submit screenshot