Deduktionsteoremet

Från Wikipedia
Hoppa till navigering Hoppa till sök
Uppslagsordet ”Absurdumregeln” leder hit. För slutledningsregeln i satslogik, se Absurditetsregeln.

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 absurdum[redigera | redigera wikitext]

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 även[redigera | redigera wikitext]

Källor[redigera | redigera wikitext]

  1. ^ Metalogic. An Introduction to the Metatheory of Standard First-Order Logic, Geoffrey Hunter, MACMILLAN 1971.
  2. ^ Elements of Mathematical Logic, Jan Łukasiewicz, Pergamon Oxford 1963.
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.