Eliminatieregels

Eliminatieregels, oftewel eliminatierules, zijn inferentieregels in formele logica die een samengestelde uitspraak afleiden tot een eenvoudiger of specifieker gevolg. Ze vormen de tegenhanger van invoeringsregels en zijn essentieel bij natuurlijke deductie en bewijssystemen in wiskunde en informatica.

Belangrijke eliminatieregels zijn onder meer: ∧-eliminatie, die uit A ∧ B A afleidt en ook B; ∨-eliminatie, waarbij uit A ∨ B twee subbewijzen worden gevoerd waarmee dezelfde conclusie C volgt (uit A volgt C en uit B volgt C); →-eliminatie (modus ponens), die uit A → B en A B afleidt; ⊥-eliminatie (ex falso quodlibet), waarbij uit een contradictie ⊥ elke gewenste formule kan worden afgeleid. Daarnaast is er ∀-eliminatie: uit ∀x φ(x) volgt φ(t) voor elke term t; ∃-eliminatie: uit ∃x φ(x) en een subbewijs waarin φ(a) leidt tot C, met a als nieuw symbool, volgt C. Verwante vormen omvatten reductio ad absurdum (uit het aannemen van ¬A en het afleiden van ⊥ volgt A) en, in klassieke logica, dubbele negatie-eliminatie ¬¬A → A.

De exacte vorm en beschikbaarheid van deze regels kunnen per logische systeem verschillen. In intuïtieve logica ontbreekt soms ¬¬A → A, of wordt reductio anders geïnterpreteerd. Eliminatieregels zijn fundamenteel voor formele redenering en proof-theorie en worden veel toegepast in wiskundige bewijzen en computationele logica. Zie ook natural deduction, sequentiecalculus en bewijsvoering.