---
# System prepended metadata

title: ItC Week 3~4 - Boolean Logic
tags: [Intro_to_Comp]

---

<font face="Dejavu Sans"/>

# ItC Week 3~4 - Boolean Logic

###### tags: `Intro_to_Comp`

- ## Introduction
  
  - Specifications for time(clock)

- ## Logic Circuits
  
  - Combiniational Logic
    - memoryless
    - output instantly be effected by current inputs
  - Sequential Logic
    - has memory
    - output be effected by current & previous inputs
  - Combinational Compositions
    - every element is combinational
    - no cyclic path
    - every node is either an input or connect to exactly 1 output

- ## Boolean Equation
  
  - Half Adder
  - Truth Table
  - $+ \rightarrow or$
  - $\cdot \rightarrow and$
  - Sum-of-Products(SOP) Form
    - all equations can be written in SOP form
    - solution is guaranteed but not optimized
  - Producto-of-Sum(POS) Form
    - similar to SOP, solution is guaranteed but not optimized

- ## Boolean Algebra
  
  - Idendity Theorem
    - $B \cdot 1 = B$
    - $B + 0 = B$
  - Null Element Theorem
    - $B \cdot 0 = 0$
    - $B + 1=1$
  - Idempotency Theorem
    - $B \cdot B = B$
    - $B + B = B$
  - Involution Theorem
    - $\overline{\overline B}=B$
  - Complement Theorem
    - $B \cdot \overline B = 0$
    - $B + \overline B = 1$
  
- ## Boolean Theorems of Several Variables
  
  - Commutativity(交換律)
  - Associativity(結合律)
  - Distributivity(分配律)
  - Covering
  - Consensus(共識)
  - De Morgan's Theorem
    - $\overline {ABCD}=\overline A+\overline B+\overline C+\overline D$
    - $\overline {A+B+C+D} = \overline A \cdot \overline B \cdot \overline C \cdot\overline D$
  - Bubble Pushing
    - start pushing from output, then work towards input

- ## From Logic to Gates

  - Circuit Schematics
    - inputs on left(or top)
    - outputs on right(or bottom)
    - gates flow from left to right
    - straight wires are preferred
  - Contention
    - marked as "X"
    - circuit tries to drive output to 1 and 0
  - Tristate Buffer
    | E  | A | Out |
    | -- | - | --- |
    | 0  | 0 | Z   |
    | 0  | 1 | Z   |
    | 1  | 0 | 0   |
    | 1  | 1 | 1   |
  - Busses
    - connect different components in a computer(CPU, GPU, RAM etc.)
    - only one device is active at once
    - tristate buffers are commonly used here
  
- ## K-Maps
  
  - Features
    - Minimize boolean equations graphically by combining terms
    - $PA+P\overline A=P$
    - Can handle up to 4 inputs
  - Rules
    - Bit order in (00, 01, 11, 10), so that adjacent rows/ columns only
      differ in 1 bit
    - Every 1 must be "circled" at least once (can be more than once)
    - Each circle must span $2^x$ squares in each direction
    - Each circle must be as large as possible
    - A "don't care" is only cirlced when it helps minimizing the equation
    - The map can be transform in to a torus(donut shape)

- ## Combinaitonal building blocks
  
  - Multiplexer
    - Select between one of $N$ inputs to output
    - $log_2 N$-bits select input
    - Implementation
      - Logic gates
      - Tristates
    - 4:1 Mutiplexer implementation
      - Logic gates
      - Tristates
      - 2:1 multiplexer
    - Application
      - As a look up table
        - ~~Just plug it in(TM)~~
  - Decoder
    - $N$ inputs, $2^N$ outputs
    - Only outpt HIGH on one output
    - Example
      - memory locator (input = address, output = physical memory)

{%hackmd BJrTq20hE %}
