REFERENCE SHEET

Boolean logic, circuits & satisfiability

Connect logical specifications to finite computations on bits.

¬(P ∧ Q) ≡ (¬P ∨ ¬Q)

Definitions

Boolean formula

An expression built from variables taking values in {false,true} and logical connectives. An assignment gives each variable a truth value.

SAT and validity

A formula is satisfiable if some assignment makes it true; valid if every assignment does. Unsatisfiable means no assignment works.

Boolean circuit

A finite directed acyclic network of gates, inputs, and outputs. Unlike a formula tree, a circuit may reuse a subcomputation through multiple outgoing wires.

Key theorems

De Morgan laws

Negating a conjunction gives a disjunction of negations; negating a disjunction gives a conjunction of negations.

Functional completeness

Every Boolean function can be represented using AND, OR, and NOT; NAND alone also suffices.

Circuit evaluation

Given an assignment and an acyclic circuit, evaluate gates in topological order in time linear in the number of gates and wires.

Notable applications

Hardware

Combinational logic implements bit-level arithmetic and control functions.

Constraint solving

Encode a finite collection of requirements as a formula and search for a satisfying assignment.

Work it out

Try before revealing

01 / Compute

Is (P ∨ Q) ∧ ¬P satisfiable? Is it valid?

Hint

Try P=false first.

Solution

It is satisfiable with P=false and Q=true. It is not valid: P=true makes the conjunction false.

02 / Construct

Express NOT P and P AND Q using only NAND, where P NAND Q = ¬(P ∧ Q).

Hint

Feeding the same bit into both NAND inputs negates it.