Deduktionsteoremet

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

Deduktionsteoremet är ett metateorem inom logiken, 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 implikation. Alfred Tarski bevisade teoremet 1921, men det tidigaste publicerade beviset var av Jacques Herbrand, 1930.

Definition: 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.

Definition med symboler: H ʌ F \vdash G implicerar H \vdash F→G, där symbolen, \vdash, betecknar syntaktisk konsekvens.

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.

Definition med symboler av RAA-regeln: H ʌ F \vdash K implicerar H \vdash ~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 Lukasiewics, Pergamon Oxford 1963.
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.