Lista över slutledningsregler

Detta är en lista över inferensregler , logiska lagar som relaterar till matematiska formler.

Introduktion

Inferensregler är syntaktiska transformationsregler som man kan använda för att dra slutsatser från en premiss för att skapa ett argument. En uppsättning regler kan användas för att sluta sig till vilken giltig slutsats som helst om den är komplett, samtidigt som man aldrig kan sluta sig till en ogiltig slutsats om den är sund. En sund och komplett uppsättning regler behöver inte inkludera alla regler i följande lista, eftersom många av reglerna är överflödiga och kan bevisas med de andra reglerna.

Regler för ansvarsfrihet tillåter slutledning från en subderivation baserad på ett tillfälligt antagande. Nedan notationen

$\varphi \vdash \psi$

indikerar en sådan underledning från det tillfälliga antagandet $\varphi$ till $\psi$ .

Regler för klassisk sententialkalkyl

Sententialkalkyl är också känd som propositionskalkyl .

Regler för negationer

Reductio ad absurdum (eller Negation Introduction )

$\varphi \vdash \psi$

${\underline {\varphi \vdash \lnot \psi }}$

$\ lnot \varphi$

Reductio ad absurdum (relaterad till lagen om utesluten mitt )

$\lnot \varphi \vdash \psi$

${\underline {\lnot \varphi \ vdash \lnot \psi }}$

$\varphi$

Ex contradictione quodlibet

$\varphi$

${\underline {\lnot \varphi }}$

$\psi$

Dubbel negationseliminering

${\underline {\lnot \lnot \varphi }}$

$\varphi$

Dubbelnegeringsintroduktion

${\underline {\varphi \quad \quad }}$

$\lnot \lnot \varphi$

Regler för villkor

Deduktionssats (eller villkorlig introduktion )

${\underline {\varphi \vdash \psi }}$

$\varphi \rightarrow \psi$

Modus ponens (eller villkorlig eliminering )

$\varphi \rightarrow \psi$

${\underline {\varphi \quad \quad \quad }}$

$\psi$

Modus tollens

$\varphi \rightarrow \ psi$

${\underline {\lnot \psi \quad \quad \quad }}$

$\lnot \varphi$

Regler för konjunktioner

Adjunktion (eller konjunktionsinledning )

$\varphi$

${\underline {\psi \quad \quad \ \ }}$

$\varphi \land \psi$

Förenkling (eller konjunktion Elimination )

${\underline {\varphi \land \psi }}$

$\varphi$

${\underline {\varphi \land \psi }}$

$\psi$

Regler för disjunktioner

Addition (eller disjunktionsintroduktion )

${\underline {\varphi \quad \quad \ \ }}$

$\varphi \lor \psi$

${\underline {\psi \quad \quad \ \ }}$

$\varphi \lor \psi$

Fallanalys (eller Proof by Cases eller Argument by Cases or Disjunction elimination )

$\varphi \rightarrow \chi$

$\psi \rightarrow \chi$

${\underline {\varphi \lor \psi }}$

$\chi$

Disjunktiv syllogism

$\varphi \lor \psi$

${\underline {\lnot \varphi \quad \quad }}$

$\psi$

$\varphi \lor \psi$

${ \displaystyle {\underline {\lnot \psi \quad \quad }}}$

$\varphi$

Konstruktivt dilemma

$\varphi \rightarrow \chi$

$\psi \rightarrow \ xi$

${\underline {\varphi \lor \psi }}$

$\chi \lor \xi$

Regler för biconditionals

Bivillkorlig introduktion

$\varphi \rightarrow \psi$

${\underline {\psi \rightarrow \varphi }}$

$\varphi \leftrightarrow \psi$

Bivillkorlig eliminering

$\varphi \leftrightarrow \psi$

${\underline {\varphi \quad \quad }}$

$\psi$

$\varphi \leftrightarrow \psi$

${\underline {\psi \quad \quad }}$

$\varphi$

$\varphi \leftrightarrow \psi$

${\underline {\ lnot \varphi \quad \quad }}$

$\lnot \psi$

$\varphi \leftrightarrow \psi$

${\underline {\lnot \psi \quad \ quad }}$

$\lnot \varphi$

$\varphi \leftrightarrow \psi$

${\underline {\psi \lor \varphi }}$

$\psi \land \varphi$

$\varphi \leftrightarrow \psi$

${\underline {\lnot \psi \lor \lnot \varphi }}$

$\lnot \psi \land \lnot \varphi$

Regler för klassisk predikatkalkyl

I följande regler är $\varphi (\beta /\alpha )$ exakt som $\varphi$ förutom att ha termen $\beta$ varhelst ${\ displaystyle \varphi }$ har den fria variabeln $\alpha$ .

Universell generalisering (eller universell introduktion )

${\underline {\varphi {(\beta /\alpha )}}}$

$\forall \alpha \,\varphi$

Restriktion 1: $\beta$ är en variabel som inte förekommer i $\varphi$ . Restriktion 2: $\beta$ nämns inte i några hypoteser eller oavslutade antaganden.

Universal Instantiation (eller Universal Elimination )

$\forall \alpha \,\varphi$

${\overline {\varphi {(\beta /\alpha )}}}$

Begränsning: Ingen fri förekomst av $\alpha$ i $\varphi$ faller inom ramen för en kvantifierare som kvantifierar en variabel som förekommer i $\beta$ .

Existentiell generalisering (eller existentiell introduktion )

${\underline {\varphi (\beta /\alpha )}}$

$\exists \alpha \,\varphi$

Begränsning: Ingen fri förekomst av $\alpha$ i $\varphi$ faller inom ramen för en kvantifierare som kvantifierar en variabel som förekommer i $\beta$ .

Existentiell instansiering (eller existentiell eliminering )

$\exists \alpha \,\varphi$

${\underline {\varphi (\beta /\alpha )\vdash \ psi }}$

$\psi$

Restriktion 1: $\beta$ är en variabel som inte förekommer i $\varphi$ . Restriktion 2: Det finns ingen förekomst, fri eller bunden, av $\beta$ i $\psi$ . Restriktion 3: $\beta$ nämns inte i några hypoteser eller oavslutade antaganden.

Regler för substrukturell logik

Följande är specialfall av universell generalisering och existentiell eliminering; dessa förekommer i substrukturell logik, såsom linjär logik .

Regel för försvagning (eller monotoni av entailment ) (aka no-cloning theorem )

$\alpha \vdash \beta$

${\overline {\alpha ,\alpha \vdash \ beta }}$

Regel för kontraktion (eller idempotens av entailment ) (aka no-deleting theorem )

${\underline {\alpha ,\alpha ,\gamma \vdash \beta }}$

$\alpha ,\gamma \vdash \beta$

Tabell: Regler för slutledning

Reglerna ovan kan sammanfattas i följande tabell. Kolumnen " Tautologi " visar hur man tolkar notationen för en given regel.

Regler för slutledning	Tautologi	namn
${\begin{aligned}p\\p\rightarrow q\\\därför {\overline {q\quad \quad \quad }}\\\end{aligned}}$	$(p\wedge (p\högerpil q))\högerpil q$	Modus ponens
${\begin{aligned}\neg q\\p\högerpil q\\\därför {\overline {\neg p\quad \quad \quad }}\\\end {Justerat}}$	$(\neg q\wedge (p\högerpil q))\högerpil \neg p$	Modus tollens
${\begin{aligned}(p\vee q)\vee r\\\därför {\overline {p\vee (q\vee r )}}\\\end{aligned}}$	$((p\vee q)\vee r)\högerpil (p\vee (q\vee r))$	Associativ
${\begin{aligned}p\wedge q\\\därför {\overline {q\wedge p}}\\\end{aligned}}$	$(p\wedge q)\rightarrow (q\wedge p)$	Kommutativ
${\begin{aligned}p\rightarrow q\\q\rightarrow p\\\därför {\overline {p\leftrightarrow q}}\\\end{aligned }}$	$((p\rightarrow q)\wedge (q\rightarrow p))\rightarrow (p\leftrightarrow q)$	Lagen om bivillkorliga satser
${\begin{aligned}(p\wedge q)\högerpil r\\\därför {\overline {p\rightarrow (q\rightarrow r )}}\\\end{aligned}}$	$((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))$	Export
${\begin{aligned}p\rightarrow q\\\därför {\overline {\neg q\rightarrow \neg p}}\\\end{aligned}}$	$(p\högerpil q)\högerpil (\neg q\högerpil \neg p)$	Införlivande eller kontrapositionslag
${\begin{aligned}p\rightarrow q\\q\rightarrow r\\\därför {\overline {p\rightarrow r}}\\\end{aligned }}$	$((p\högerpil q)\wedge (q\högerpil r))\högerpil (p\högerpil r)$	Hypotetisk syllogism
${\begin{aligned}p\rightarrow q\\\därför {\overline {\neg p\vee q}}\\\end{aligned}}$	$(p\högerpil q)\högerpil (\neg p\vee q)$	Materiell implikation
${\begin{aligned}(p\vee q)\wedge r\\\därför {\overline {(p\wedge r)\vee (q\kil r)}}\\\end{justerad}}$	$((p\vee q)\wedge r)\högerpil ((p\wedge r)\vee (q \wedge r))$	Distributiv
${\begin{aligned}p\rightarrow q\\\därför {\overline {p\rightarrow (p\wedge q)}}\\\end{aligned }}$	$(p\rightarrow q)\rightarrow (p\rightarrow (p\wedge q))$	Absorption
${\begin{aligned}p\vee q\\\neg p\\\därför {\overline {q\quad \quad \quad }}\\\end{aligned} }$	$((p\vee q)\wedge \neg p)\högerpil q$	Disjunktiv syllogism
${\begin{aligned}p\\\därför {\overline {p\vee q}}\\\end{aligned}}$	$p\rightarrow (p\vee q)$	Tillägg
${\begin{aligned}p\wedge q\\\därför {\overline {p\quad \quad \quad }}\\\end{aligned}}$	$(p\wedge q)\högerpil p$	Förenkling
${\begin{aligned}p\\q\\\därför {\overline {p\wedge q}}\\\end{aligned}}$	$((p)\wedge (q))\högerpil (p\wedge q)$	Samband
${\begin{aligned}p\\\därför {\overline {\neg \neg p}}\\\end{aligned}}$	$p\rightarrow (\neg \neg p)$	Dubbel negation introduktion
${\begin{aligned}p\vee p\\\därför {\overline {p\quad \quad \quad }}\\\end{aligned}}$	$(p\vee p)\högerpil p$	Disjunktiv förenkling
${\begin{aligned}p\vee q\\\neg p\vee r\\\därför {\overline {q\vee r}}\\\ end{aligned}}$	$((p\vee q)\wedge (\neg p\vee r))\högerpil (q\vee r)$	Upplösning
${\begin{aligned}p\rightarrow q\\r\rightarrow q\\p\vee r\\\därför {\overline {q\quad \quad \quad }}\\\end{aligned}}$	$((p\högerpil q)\wedge (r\högerpil q)\wedge (p\vee r))\högerpil q$	Disjunktion Eliminering

Alla regler använder de grundläggande logiska operatorerna. En komplett tabell med "logiska operatorer" visas av en sanningstabell , som ger definitioner av alla möjliga (16) sanningsfunktioner för 2 booleska variabler ( p , q ):

sid	q		0	1	2	3	4	5	6	7		8	9	10	11	12	13	14	15
T	T		F	F	F	F	F	F	F	F		T	T	T	T	T	T	T	T
T	F		F	F	F	F	T	T	T	T		F	F	F	F	T	T	T	T
F	T		F	F	T	T	F	F	T	T		F	F	T	T	F	F	T	T
F	F		F	T	F	T	F	T	F	T		F	T	F	T	F	T	F	T

där T = sant och F = falskt, och kolumnerna är de logiska operatorerna :

• 0 , falsk , Motsägelse ;
• 1 , NOR, Logisk NOR ( Peirces pil );
• 2 , Omvänd icke-implikation ;
• 3 , ¬p , Negation ;
• 4 , Materiell icke-implikation ;
• 5 , ¬q , Negation ;
• 6 , XOR , Exklusiv disjunktion ;
• 7 , NAND , Logisk NAND ( Sheffer stroke );
• 8 , AND , logisk konjunktion ;
• 9 , XNOR , Om och endast om , Logiskt tvåvillkorligt ;
• 10 , q , projektionsfunktion ;
• 11 , om/då , Logisk implikation ;
• 12 , s , Projektionsfunktion ;
• 13 , then/if, Converse implikation ;
• 14 , ELLER, logisk disjunktion ;
• 15 , sant , Tautologi .

Varje logisk operator kan användas i ett påstående om variabler och operationer, vilket visar en grundläggande inferensregel. Exempel:

• Kolumn-14-operatorn (OR), visar Additionsregel : när p =T (hypotesen väljer de två första raderna i tabellen), ser vi (vid kolumn-14) att p ∨ q =T.

  Vi kan också se att med samma premiss är en annan slutsats giltig: kolumnerna 12, 14 och 15 är T.

• Kolumn-8-operatorn (AND) visar förenklingsregeln : när p ∧ q =T (första raden i tabellen), ser vi att p =T.

  Med denna utgångspunkt drar vi också slutsatsen att q =T, p ∨ q =T, etc. enligt kolumnerna 9–15.

• Kolumn-11-operatorn (IF/THEN), visar Modus ponens-regeln : när p → q =T och p =T uppfyller endast en rad i sanningstabellen (den första) dessa två villkor. På denna rad q också sant. Därför, närhelst p → q är sant och p är sant, måste q också vara sant.

Maskiner och välutbildade människor använder denna syn på tabellmetoden för att göra grundläggande slutsatser och för att kontrollera om andra slutsatser (för samma lokaler) kan erhållas.

Exempel 1

Tänk på följande antaganden: "Om det regnar idag, så åker vi inte på en kanot idag. Om vi ​​inte åker på en kanottur idag, så åker vi på en kanottur imorgon. Därför (Matematisk symbol för "därför" är $\därför$ ), om det regnar idag åker vi på en kanottur imorgon". För att använda slutledningsreglerna i tabellen ovan låter vi $p$ vara propositionen "Om det regnar idag", $q$ vara "Vi kommer inte att åka kanot idag" och låter $r$ vara "Vi åker på kanottur imorgon". Då är detta argument av formen:

${\begin{aligned}p\rightarrow q\\q\rightarrow r\\\därför {\overline {p\rightarrow r}}\\\end{aligned }}$

Exempel 2

Tänk på en mer komplex uppsättning antaganden: "Det är inte soligt idag och det är kallare än igår". "Vi kommer att bada bara om det är soligt", "Om vi ​​inte går och simmar, så ska vi grilla", och "Om vi ​​ska grilla, då kommer vi att vara hemma vid solnedgången" leder till slutsatsen " Vi kommer att vara hemma vid solnedgången." Bevis genom slutledningsregler: Låt $p$ vara propositionen "Det är soligt idag", $q$ propositionen "Det är kallare än igår", $r$ propositionen "Vi kommer att simma", $s$ förslaget "Vi ska grilla", och $t$ förslaget "Vi kommer att vara hemma vid solnedgången". Då blir hypoteserna $\neg p\wedge q,r\rightarrow p,\neg r\rightarrow s$ och $s\rightarrow t$ . Med vår intuition antar vi att slutsatsen kan vara $t$ . Med hjälp av tabellen för slutledningsregler kan vi enkelt bevisa gissningen:

Steg	Anledning
1. $\neg p\wedge q$	Hypotes
2. $\neg p$	Förenkling med steg 1
3. $r\rightarrow p$	Hypotes
4. $\neg r$	Modus tollens med steg 2 och 3
5. $\neg r\rightarrow s$	Hypotes
6. $s$	Modus ponens med steg 4 och 5
7. $s\rightarrow t$	Hypotes
8. $t$	Modus ponens med steg 6 och 7

Se även

Lista över logiska system

Modus ponendo tollens