Shreyas’ Notes

Advanced Logic in Computer Science

COMP 409

fall, junior year

Liar’s paradox: “This sentence is false”

Sand-heap paradox: Adding one grain doesn’t make a non-heap a heap.

Excluded middle: Nothing between true and false (philosophically sus).

Digital abstraction: High/Low state.

Transitivity of implication:

  1. If pp, then qq (p    qp \implies q)
  2. If qq, then rr (q    rq \implies r)
  3. Therefore if pp, then rr (p    rp \implies r)

Set of symbolic proposition. Set of truth values.

Connecting propositional connectives to logical operations. Let PP be the set of propositions. FF is the smallest set such that:

  1. PFP \subseteq F
  2. [closure] If ψF\psi \in F, then:
    • ¬ψF\neg \psi \in F
    • ψψF\psi \circ \psi \in F

F:={W:W is a set of expressions that contain P and satisfy closure}F' := \bigcap \{W : W \text{ is a set of expressions that contain } P \text{ and satisfy closure} \}

Theorem: FF' is the smallest set that contains PP and satisfies closure.

Alternative definition:

  1. F0=PF_0 = P
  2. Fi+1=Fi{(¬ψ):ψF}{(ϕψ):ψ,ϕF}F_{i + 1} = F_i \cup \{(\neg \psi) : \psi \in F\} \cup \{(\phi \circ \psi) : \psi, \phi \in F\}

Claim: FF' contains PP and satisfies closure.

Theorem: F=FF' = F