Boolean Logic, Logic Gates, and Computer Architecture 9/22

Pixel Color Representation

• Subcharacter units create words or strings of visual data.
• Instruction pixels: Each pixel is represented by numbers ranging from $0$ to $255$.
• Color composition: Channels for Red, Green, and Blue (RGB) use these numeric values from $0$ to $255$ per channel.
• Any color in the spectrum can be produced by combining specific numeric values across the RGB channels.

Boolean Logic & Elementary Gates

• Central Processing Units (CPUs) contain billions of transistors performing basic arithmetic and logical operations such as addition, subtraction, division, and negation.
• Functional Analogy:
  • A function acts like a black box or a blender: specific inputs yield specific outputs governed by the functional design of the box.
  • Blender example: Fruits and milk placed in a blender yield a milkshake; placing fruit inside cannot yield a car.
  • Factory example: Raw materials fed into a manufacturing factory yield specialized car components (cylinders, engines, tires).
  • CPU function: Billions of embedded logic components process electrical signals based on deterministic Boolean logic.
• Definition of Boolean Function:
  • A function mapping input variables to unique outputs where all inputs and outputs are Boolean values ($0$ or $1$).
  • A valid function cannot produce two different outputs for a single input.
• NOT Gate (Negation / Inverter):
  • Operator symbol: Bar over the variable ($\bar{x}$ or $x\text{ bar}$).
  • Circuit symbol: A triangle with a small circle at its tip.
  • Functionality: Inverts the binary value of input $x$.
  • Truth values:
  • If $x = 0$, then $\bar{x} = 1$.
  • If $x = 1$, then $\bar{x} = 0$.
• OR Gate (Disjunction):
  • Operator symbol: Plus sign ($+$).
  • Circuit symbol: A gate with a curved rear input line and a pointed front output tip.
  • Functionality: Evaluates to $1$ (true) if at least one input condition is $1$ (true).
  • Real-world scenario: Requirement to enroll in CS 110 or MATH 140. Enrolling in CS 110, MATH 140, or both satisfies the condition ($1$).
  • Hardware scenario: Purchasing Computer A, Computer B, or both.
  • Truth values:
  • Evaluates to $0$ (false) only when neither input condition is fulfilled (e.g., enrolled in neither CS 110 nor MATH 140).
• AND Gate (Conjunction):
  • Operator symbol: Dot ($\cdot$) or written directly adjacent without a symbol.
  • Circuit symbol: A gate with a straight rear input line and a rounded D-shaped front.
  • Functionality: Evaluates to $1$ (true) if and only if all input conditions are simultaneously $1$ (true).
  • Real-world scenario: To take CS 210, a student must complete prerequisite courses CS 110 and CS 140 with a grade of C+ or higher, sit in class, complete assignments, and take exams.
  • Interdependence: Dependent on all conditions being met; if any single condition is $0$ (false), the entire statement evaluates to $0$ (false).
  • Truth table for AND ($\cdot$):
  • $0 \cdot 0 = 0$
  • $0 \cdot 1 = 0$
  • $1 \cdot 0 = 0$
  • $1 \cdot 1 = 1$

Minterm Expansion Algorithm

• Purpose: Expresses any arbitrary Boolean function entirely in terms of fundamental Boolean operators (AND, OR, NOT).
• Analogy: Creating a structural physical template (like a mold used for pouring melted plastic to yield shoes or sandals), applied digitally to construct logical hardware.
• Step-by-Step Procedure:
  1. Construct the complete truth table for the desired Boolean function.
  2. Identify and delete all rows where the output function value is $0$.
  3. For each remaining row where the function output is $1$, construct a minterm:
  • For each variable $x$, write $x$ if its value in that row is $1$.
  • Write $\bar{x}$ if its value in that row is $0$.
  • Connect all variables within the row using the AND ($\cdot$) operator.
  1. Combine all individual minterm expressions together using the OR ($+$) operator to obtain the final Boolean expression.

Logical Implication

• Definition & Form:
  • Represented as $P \rightarrow Q$ or $x \rightarrow y$, read as "If $P$, then $Q$" (where $P$ is the cause/hypothesis and $Q$ is the effect/conclusion).
  • Cause ($x$) and Effect ($y$) logical framework: Evaluates the consistency of the conclusion given the cause.
• Case Analysis & Truth Rules:
  • $0 \rightarrow 0 = 1$ (True): Absence of cause ($x = 0$) and absence of effect ($y = 0$). (Example: It does not rain, and the ground is not wet).
  • $0 \rightarrow 1 = 1$ (True): Absence of cause ($x = 0$), but effect occurs ($y = 1$). Valid because external factors could cause the outcome without invalidating the implication. (Example: It does not rain, but the ground is wet due to spilled water or previous rain).
  • $1 \rightarrow 1 = 1$ (True): Presence of cause ($x = 1$) produces the expected effect ($y = 1$). (Example: It rains, and the ground is wet).
  • $1 \rightarrow 0 = 0$ (False): Cause occurs ($x = 1$), but promised effect fails to occur ($y = 0$). This contradiction is the only condition that makes implication false. (Example: It rains, but the ground is not wet).
• Course Grade Example:
  • Statement: "If you score over 93 in this course, then you will get an A."
  • Score $\le 93$ ($0$), do not get A ($0$) $\rightarrow$ True ($1$).
  • Score $\le 93$ ($0$), get A ($1$) $\rightarrow$ True ($1$) (e.g., achieved high scores on other coursework).
  • Score $> 93$ ($1$), get A ($1$) $\rightarrow$ True ($1$).
  • Score $> 93$ ($1$), DO NOT get A ($0$) $\rightarrow$ False ($0$) (contradiction).
• Minterm Expansion for Implication ($x \rightarrow y$):
  • Truth table rows with output $1$:
  • Row 1 ($x = 0, y = 0$): $\bar{x} \cdot \bar{y}$
  • Row 2 ($x = 0, y = 1$): $\bar{x} \cdot y$
  • Row 4 ($x = 1, y = 1$): $x \cdot y$
  • Expression:     $\text{Implication}(x, y) = \bar{x} \cdot \bar{y} + \bar{x} \cdot y + x \cdot y$
• Circuit Architecture for Implication:
  • Constructed using NOT gates on inputs, fed into AND gates for each minterm, with outputs combined via multi-input OR gates.

Universal and Specialized Gates

• NAND Gate (Not AND):
  • Inverts the result of an AND operation.
  • Commonly utilized in solid-state flash memory (SSD) technology.
  • Truth table for NAND:
  • $0, 0 \rightarrow 1$
  • $0, 1 \rightarrow 1$
  • $1, 0 \rightarrow 1$
  • $1, 1 \rightarrow 0$
  • Minterm Expansion for NAND:     $\text{NAND}(a, b) = \bar{a} \cdot \bar{b} + \bar{a} \cdot b + a \cdot \bar{b}$
• NOR Gate (Not OR):
  • Inverts the result of an OR operation, represented as $\overline{x + y}$.
  • Truth table for NOR:
  • $0, 0 \rightarrow 1$
  • $0, 1 \rightarrow 0$
  • $1, 0 \rightarrow 0$
  • $1, 1 \rightarrow 0$
• XOR Gate (Exclusive OR):
  • Operator symbol: Circle with a plus sign ($\oplus$).
  • Circuit symbol: Similar to an OR gate with an additional curved boundary line on the input side.
  • Functionality: Evaluates to $1$ (true) if and only if inputs are strictly opposite in value.
  • Truth table for XOR ($a \oplus b$):
  • $0 \oplus 0 = 0$
  • $0 \oplus 1 = 1$
  • $1 \oplus 0 = 1$
  • $1 \oplus 1 = 0$

Binary Arithmetic & Hardware Adders

• Binary Addition Fundamentals:
  • $0 + 0 = 0$ (Carry = $0$, Sum = $0$)
  • $1 + 0 = 1$ (Carry = $0$, Sum = $1$)
  • $0 + 1 = 1$ (Carry = $0$, Sum = $1$)
  • $1 + 1 = 10_2$ (Carry = $1$, Sum = $0$)
  • Analogy: Decimal addition of $9 + 1 = 10$, producing a sum of $0$ and a carry of $1$.
• Half Adder Circuit:
  • Purpose: Adds two $1$-bit binary numbers ($a$ and $b$).
  • Inputs: Two $1$-bit signals ($a$, $b$).
  • Outputs:
  • Sum bit: Evaluated using an XOR gate ($\text{Sum} = a \oplus b$).
  • Carry bit: Evaluated using an AND gate ($\text{Carry} = a \cdot b$).
  • Encapsulated as a black box taking two binary input bits and outputting a two-bit binary representation ($\text{Carry}, \text{Sum}$).
• Full Adder Circuit:
  • Purpose: Adds two $1$-bit binary numbers along with a Carry input from a previous addition stage.
  • Inputs: Three $1$-bit signals ($x$, $y$, and $\text{Carry}_{in}$).
  • Outputs: Two $1$-bit signals ($\text{Carry}_{out}$ and $\text{Sum}$).
  • Truth Table for Full Adder:
  • Inputs $(0, 0, 0) \rightarrow \text{Carry}_{out} = 0, \text{Sum} = 0$
  • Inputs $(0, 0, 1) \rightarrow \text{Carry}_{out} = 0, \text{Sum} = 1$
  • Inputs $(0, 1, 0) \rightarrow \text{Carry}_{out} = 0, \text{Sum} = 1$
  • Inputs $(0, 1, 1) \rightarrow \text{Carry}_{out} = 1, \text{Sum} = 0$
  • Inputs $(1, 0, 0) \rightarrow \text{Carry}_{out} = 0, \text{Sum} = 1$
  • Inputs $(1, 0, 1) \rightarrow \text{Carry}_{out} = 1, \text{Sum} = 0$
  • Inputs $(1, 1, 0) \rightarrow \text{Carry}_{out} = 1, \text{Sum} = 0$
  • Inputs $(1, 1, 1) \rightarrow \text{Carry}_{out} = 1, \text{Sum} = 1$
• $n$-bit Ripple Carry Adder:
  • Formed by chaining $n$ full adder circuits sequentially.
  • Allows addition of multi-bit binary numbers by passing the $\text{Carry}_{out}$ from bit position $i$ as the $\text{Carry}_{in}$ to bit position i+1$.\n\n# Memory Elements & Latches\n\n- Latch Circuit:\n - Fundamental hardware component used to store binary state in memory systems.\n - Structure: Composed of two cross-coupled NOR gates, where the output of the first NOR gate feeds into an input of the second NOR gate, and the output of the second NOR gate feeds back into the first.\n - Memory capacity: Billions of interconnected latches construct 1\,\text{GB} of Random Access Memory (RAM).\n\n# Computer Architecture & Von Neumann Model\n\n- Von Neumann Architecture:\n - Designed by John von Neumann in the 1960s; forms the baseline structural paradigm for modern computing systems.\n - Key Components:\n - Central Processing Unit (CPU) containing an Arithmetic Logic Unit (ALU) and control structures.\n - Random Access Memory (RAM).\n - Input/Output (I/O) interfaces.\n - System Buses: High-speed communication lines connecting CPU, memory, and I/O devices.\n - Execution Model: Programs consist of long sequential lists of instructions stored in RAM, executed by the CPU one instruction at a time.\n- Memory Hierarchy & Storage Analogy:\n - CPU Registers & Cache:\n - Cache: High-speed memory embedded directly within the CPU chip (typically a few megabytes). Holds essential hardware-level instructions.\n - Analogy: Information stored directly in the human brain.\n - RAM (Random Access Memory):\n - Fast volatile memory constructed from semiconductor transistors.\n - Analogy: Items placed on an active workspace table. If data is not loaded onto the table (RAM), the CPU cannot process it.\n - Secondary Storage (SSD / HDD):\n - Magnetic Hard Disk Drives (HDD) or modern NAND flash-based Solid State Drives (SSD).\n - Analogy: Books stored away on library shelves. Reading from secondary storage requires significantly longer retrieval times compared to RAM or cache.\n- Special CPU Registers:\n - Program Counter (PC): Dedicated register tracking the memory address of the next instruction scheduled for execution.\n - Instruction Register: Dedicated register holding the current instruction actively being executed or decoded.\n\n# Questions & Discussion\n\n- Cause-and-Effect Logic in Implication:\n - Question: Why does input 0, 0$or$0, 1$yield$1$(true) in implication, whereas$1, 0$yields$0 (false)?\n - Response: Implication analyzes whether an effect contradicts its stated cause. If no cause occurs (x = 0$), any outcome ($y = 0$or$y = 1$) is logically acceptable because no promise was broken. When cause occurs ($x = 1$), failure to produce the required result ($y = 0) represents a logical violation (false).\n- Burger Scenario Clarification:\n - Question: How does an intuitive real-world scenario map to binary values in implication?\n - Response:\n - 0, 0$: You have not eaten the burger ($x = 0$), and the burger has not been eaten ($y = 0$)$\rightarrow$True ($1).\n - 0, 1$: You have not eaten the burger ($x = 0$), but the burger has been eaten ($y = 1$)$\rightarrow$True ($1) (someone else ate it).\n - 1, 0$: You ate the burger ($x = 1$), but the burger has NOT been eaten ($y = 0$)$\rightarrow$False ($0) (impossible physical contradiction).\n - 1, 1$: You ate the burger ($x = 1$), and the burger has been eaten ($y = 1$)$\rightarrow$True ($1).\n- Operation Rules vs. Arithmetic:\n - Question: Why does 0 \cdot 0 = 0$for AND, but$0 \rightarrow 0 = 1 for implication?\n - Response: Different operations follow distinct operational rules defined in Boolean algebra, just as addition, multiplication, differentiation, and integration carry distinct operational rules in standard algebra and calculus.\n- NAND vs. AND Operations:\n - Question: Why is NAND output the inverse of AND?\n - Response: NAND stands for "NOT AND". Its output is generated by taking the exact truth values of an AND operation and negating them (0 \rightarrow 1$and$1 \rightarrow 0$$).