Deduktionsteoremet
Deduktionsteoremet är ett metateorem inom satslogiken, vilket även kallas CP-regeln, Conditional Proof. Teoremet är en vid bevisföring effektiv 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.
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 absurdum. 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, Law of absurdity, 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 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. |