Metatheorie

Formule Inductie

1. Basisstap
   Laat zien dat B opgaat voor de atomen.
2. Inductiestap
   Laat zien dat, als B opgaat voor de formules φ, ψ, dan ook voor hun combinaties, ¬φ, φ ∧ ψ, φ ∨ ψ, φ → ψ en φ ↔ ψ.

Subformule

Notatie: subf(φ),    bv: subf( ((p ∧ q) ∧ ( p → ¬q)) ) = 8

Een formule heet een subformule van een formule φ als die formule als een aaneengesloten deel in φ voorkomt.

Maximaal consistent

Als een consistente verzameling Γ niet meer uit te breiden is tot een grotere consistente verzameling, dan heet Γ maximaal consistent.

Theorieen

Functioneel Volledigheid

Het paar connectieven {¬, ∧} is functioneel volledig

functioneel volledig

C is een verzameling van connectieven. {¬, ∨} C heet functioneel volledig als elke formule φ logisch equivalent is met een formule ψ die slechts connectieven uit C bevat.

.
Cq.: Voor elke formule φ is er een logisch equivalente formule φ'die alleen met ¬ en ∧ geconstrueerd is.

• (¬ φ)' = ¬ φ'
• (φ ∧ ψ)' = φ' ∧ ψ'
• (φ ∨ ψ)' = ¬(¬ψ' ∧ ¬ φ')
• (φ → ψ)' = ¬(φ' ∧ ¬ψ')
• (φ ↔ ψ)'= (φ → ψ)' ∧ (ψ → φ)'

Dualiteit

Notatie: φ^d

De formule die onstaat door elk voorkomen van ∧ in φ te vervangen door ∨ en elk voorkomen van ∨ door ∧.
Laat φ, ψ formules zijn waarin alleen de connectieven ∧, ∨, ¬ voorkomen. Dan geldt:

⊨ φ ↔ ψ → ⊨ φ^d ↔ ψ^d