Deduktionsteoremet
Deduktionsteoremet (även kallad "CP-regeln", från engelska: Conditional Proof) är ett metateorem inom satslogiken. Teoremet är en vid bevisföring effektiv[förtydliga] slutledningsregel, som ofta används då en slutsats skall härledas, där huvudoperationen är en materiell implikation. Alfred Tarski bevisade teoremet 1921, men det tidigaste publicerade beviset var av Jacques Herbrand, 1930.
Deduktionsteoremet: Om man från en premissmängd H = {P1,....Pn} jämte en formel F kan härleda slutsatsen G, så kan man från H härleda F→G.
Deduktionsteoremet uttryckt med symboler: H ʌ F G implicerar H F→G, där symbolen, , betecknar syntaktisk konsekvens.[förtydliga]
I det fall då premissmängden H är tom följer av deduktionsteoremet, att F G implicerar F→G, vilket betyder att F→G är en tautologi.
Reductio ad absurdumRedigera
Om den härledda satsen G är en kontradiktion K, så följer av F→K och med stöd av den så kallade absurditetsregeln ("Ab-regeln") att F är falsk. Om man således, från H och F kan härleda en kontradiktion, så kan man med Ab-regeln dra slutsatsen att F är falsk. Den slutledningsregel man får vid sammansättning av CP-regeln och Ab-regeln går under namnet Reductio ad absurdum, den så kallade Reductio ad absurdum-regeln ("RAA-regeln").
RAA-regeln uttryckt med symboler: H ʌ F K implicerar H ~F.[1][2]
Se ävenRedigera
KällorRedigera
- ^ Metalogic. An Introduction to the Metatheory of Standard First-Order Logic, Geoffrey Hunter, MACMILLAN 1971.
- ^ Elements of Mathematical Logic, Jan Łukasiewicz, Pergamon Oxford 1963.
- Shoenfield, Joseph R. Mathematical Logic, A K Peters, ISBN 978-1-56881-135-2, Nackit, Massachusetts 2001.
Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia. |