ICS 6B Chapter 5

5.1: An introduction to Boolean algebra

Boolean algebra: a set of rules and operations for working with variables with values of 0 or 1; similar to propositional logic
- Boolean multiplication: Denoted by • and works the same as regular multiplication, logically the same as ∧
  - Table:
- Boolean addition: Denoted by + and works the same as regular addition except 1 + 1 = 1, logically the same as ∨
  - Table:
- Complement: Denoted by an over bar, works the same as the ¬ operator: 0 becomes 1 and 1 becomes 0
Relates to digital logic which is used to create computers
Variables that have a value of 1 or 0 are called Boolean variables, and Boolean expressions can be created by using Boolean operations on Boolean variables
Rules of precedence for boolean operations:
- Boolean multiplication takes precedence over Boolean addition.
- The complement operation is applied as soon as the entire expression under the bar is evaluated.
- Parentheses can be used to override the precedence rules.
Two Boolean expressions are equivalent if, for any combination of values of its variables, they have the same value
- Laws of Boolean algebra:

Boolean functions map multiple Boolean input values to the set {0, 1}
- Can be represented by an input/output table (similar to a truth table) but is not feasible for larger numbers of inputs, as the outputs are equal to 2^k where k = the number of inputs
- Can express functions using Boolean expressions
Steps to derive a Boolean function via table:
- Literal: One expression that either equals a variable or a variable’s complement
- Must take the minterm (a group of literals that make each variable equal 1) of each row that equals 1

The disjunctive normal form (DNF) is a Boolean expression that is the sum of products of literals
- Example:
The conjunctive normal form (DNF) is a Boolean expression that is the sum of sums of literals
- Example:

A set of operations is functionally complete if any Boolean expression can be rewritten using the set
- {addition, multiplication, complement} is functionally complete
- {multiplication, complement} is also functionally complete because addition can be rewritten with multiplication:
- {addition, complement} is also functionally complete because multiplication can be rewritten as addition:
NAND operation is denoted by ↑ and returns the complement of Boolean multiplication
NOR operation is denoted by ↓ and returns the complement of Boolean addition
- Tables for NAND and NOR:
One way to test functional completeness is to start with a known set and try replacing one of the operations with another

The Boolean satisfiability (SAT) problem asks if a Boolean expression can possibly evaluate to 1
- If you can set it equal to 1, then it is satisfiable; if not, it is unsatisfiable
- A particular set of values satisfies a Boolean expression if it makes it equal to 1
- There is no sufficient, fast method to solve SAT, as you have to check each input
If an expression is in DNF form, then it is easy to check if the expression is satisfiable
- Check if one of the literals does NOT contain a variable and its complement
In the CNF form, it is harder to check if the expression is satisfiable; you must check if each of the constraints equals 1 given a set of input values

Boolean algebra is used to create circuits an electronic devices
- A circuit built from electrical devices is called a gate, and a gate receives an input of Boolean values and returns an output
- AND gates represent Boolean multiplication, OR gates represent Boolean addition, and the inverter represents the complement
- Can combine gates together to create complex functions
This class will focus only on combinatorial circuits which do not store variables or loop
- Combinatorial circuits compute a Boolean function
- Finding a Boolean function from a circuit: