Elenco delle regole di inferenza - List of rules of inference

Questo è un elenco di regole di inferenza , leggi logiche che si riferiscono a formule matematiche.

introduzione

Le regole di inferenza sono regole di trasformazione sintattica che si possono usare per dedurre una conclusione da una premessa per creare un argomento. Un insieme di regole può essere utilizzato per inferire qualsiasi conclusione valida se è completa, senza mai inferire una conclusione non valida, se è valida. Non è necessario che un insieme di regole valido e completo includa tutte le regole nell'elenco seguente, poiché molte regole sono ridondanti e possono essere verificate con le altre regole.

Le regole di discarico consentono l'inferenza da una subderivazione basata su un'ipotesi temporanea. Sotto, la notazione

${\displaystyle \varphi \vdash \psi}$

indica tale subderivazione dall'assunzione temporanea a . ${\displaystyle \varphi}$${\displaystyle \psi}$

Regole per il calcolo sentenziale classico

Il calcolo sentenziale è anche conosciuto come calcolo proposizionale .

Regole per le negazioni

Reductio ad absurdum (o Negazione Introduzione )

${\displaystyle \varphi \vdash \psi}$

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

${\displaystyle \lnot \varphi }$

Reductio ad absurdum (relativo alla legge del terzo escluso )

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

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

${\displaystyle \varphi}$

Ex contraddizioni quodlibet

${\displaystyle \varphi}$

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

${\displaystyle \psi}$

Eliminazione doppia negazione

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

${\displaystyle \varphi}$

Introduzione alla doppia negazione

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

${\displaystyle \lnot \lnot \varphi }$

Regole per i condizionali

Teorema di deduzione (o introduzione condizionale )

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

${\displaystyle \varphi \rightarrow \psi}$

Modus ponens (o eliminazione condizionale )

${\displaystyle \varphi \rightarrow \psi}$

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

${\displaystyle \psi}$

Modus tollens

${\displaystyle \varphi \rightarrow \psi}$

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

${\displaystyle \lnot \varphi }$

Regole per le congiunzioni

Aggiunzione (o Congiunzione Introduzione )

${\displaystyle \varphi}$

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

${\displaystyle \varphi \land \psi}$

Semplificazione (o eliminazione della congiunzione )

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

${\displaystyle \varphi}$

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

${\displaystyle \psi}$

Regole per le disgiunzioni

Addizione (o Disgiunzione Introduzione )

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

${\displaystyle \varphi \lor \psi}$

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

${\displaystyle \varphi \lor \psi}$

Analisi del caso (o Prova per casi o Argomento per casi o Eliminazione della disgiunzione )

${\displaystyle \varphi \rightarrow \chi}$

${\displaystyle \psi \rightarrow \chi}$

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

${\displaystyle \chi}$

sillogismo disgiuntivo

${\displaystyle \varphi \lor \psi}$

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

${\displaystyle \psi}$

${\displaystyle \varphi \lor \psi}$

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

${\displaystyle \varphi}$

Dilemma costruttivo

${\displaystyle \varphi \rightarrow \chi}$

${\displaystyle \psi \rightarrow \xi}$

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

${\displaystyle \chi \lor \xi}$

Regole per i bicondizionali

Introduzione bicondizionale

${\displaystyle \varphi \rightarrow \psi}$

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

${\displaystyle \varphi \leftrightarrow \psi}$

Eliminazione bicondizionale

${\displaystyle \varphi \leftrightarrow \psi}$

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

${\displaystyle \psi}$

${\displaystyle \varphi \leftrightarrow \psi}$

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

${\displaystyle \varphi}$

${\displaystyle \varphi \leftrightarrow \psi}$

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

${\displaystyle \lnot \psi}$

${\displaystyle \varphi \leftrightarrow \psi}$

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

${\displaystyle \lnot \varphi }$

${\displaystyle \varphi \leftrightarrow \psi}$

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

${\ displaystyle \ psi \ land \ varphi}$

${\displaystyle \varphi \leftrightarrow \psi}$

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

${\displaystyle \lnot \psi \land \lnot \varphi }$

Regole del calcolo classico dei predicati

Nelle regole seguenti, è esattamente come tranne che per avere il termine dovunque ha la variabile libera . ${\displaystyle \varphi (\beta /\alpha)}$${\displaystyle \varphi}$${\displaystyle \beta}$${\displaystyle \varphi}$${\displaystyle\alpha}$

Generalizzazione universale (o introduzione universale )

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

${\displaystyle \forall \alpha \,\varphi }$

Restrizione 1: è una variabile che non si verifica in . Restrizione 2: non è menzionata in nessuna ipotesi o ipotesi non appurata. ${\displaystyle \beta}$${\displaystyle \varphi}$
${\displaystyle \beta}$

Istanziazione universale (o eliminazione universale )

${\displaystyle \forall \alpha \,\varphi }$

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

Limitazione: nessuna occorrenza libera di in rientra nell'ambito di un quantificatore che quantifica una variabile che si verifica in . ${\displaystyle\alpha}$${\displaystyle \varphi}$${\displaystyle \beta}$

Generalizzazione esistenziale (o introduzione esistenziale )

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

${\displaystyle \exists \alpha \,\varphi }$

Limitazione: nessuna occorrenza libera di in rientra nell'ambito di un quantificatore che quantifica una variabile che si verifica in . ${\displaystyle\alpha}$${\displaystyle \varphi}$${\displaystyle \beta}$

Istanziazione esistenziale (o eliminazione esistenziale )

${\displaystyle \exists \alpha \,\varphi }$

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

${\displaystyle \psi}$

Restrizione 1: è una variabile che non si verifica in . Limitazione 2: non vi è alcuna occorrenza, libera o vincolata, di in . Restrizione 3: non è menzionata in nessuna ipotesi o ipotesi non appurata. ${\displaystyle \beta}$${\displaystyle \varphi}$
${\displaystyle \beta}$${\displaystyle \psi}$
${\displaystyle \beta}$

Regole di logica sottostrutturale

I seguenti sono casi speciali di generalizzazione universale ed eliminazione esistenziale; questi si verificano in logiche sottostrutturali, come la logica lineare .

Regola dell'indebolimento (o monotonia del coinvolgimento ) (noto anche come teorema di non clonazione )

${\displaystyle \alpha \vdash \beta}$

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

Regola di contrazione (o idempotenza di implicazione ) ( nota anche come teorema di non cancellazione )

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

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

Tabella: regole di inferenza

Le regole di cui sopra possono essere riassunte nella tabella seguente. La colonna " Tautologia " mostra come interpretare la notazione di una data regola.

Regole di inferenza	Tautologia	Nome
${\displaystyle {\begin{allineato}p\\p\rightarrow q\\\quindi {\overline {q\quad \quad \quad}}\\\end{allineato}}}$	${\displaystyle (p\wedge (p\rightarrow q))\rightarrow q}$	Modus ponens
${\displaystyle {\begin{allineato}\neg q\\p\rightarrow q\\\quindi {\overline {\neg p\quad \quad \quad}}\\\end{allineato}}}$	${\displaystyle (\neg q\wedge (p\rightarrow q))\rightarrow\neg ​​p}$	Modus tollens
${\displaystyle {\begin{allineato}(p\vee q)\vee r\\\quindi {\overline {p\vee (q\vee r)}}\\\end{allineato}}}$	${\displaystyle ((p\vee q)\vee r)\rightarrow (p\vee (q\vee r))}$	Associativo
${\displaystyle {\begin{allineato}p\cuneo q\\\quindi {\overline {q\cuneo p}}\\\end{allineato}}}$	${\displaystyle (p\cuneo q)\rightarrow (q\cuneo p)}$	Commutativo
${\displaystyle {\begin{allineato}p\rightarrow q\\q\rightarrow p\\\quindi {\overline {p\leftrightarrow q}}\\\end{allineato}}}$	${\displaystyle ((p\rightarrow q)\wedge (q\rightarrow p))\rightarrow (\ p\leftrightarrow q)}$	Legge delle proposizioni bicondizionali
${\ displaystyle {\ begin {align} (p \ wedge q) \ rightarrow r \\\ quindi {\ overline {p \ rightarrow (q \ rightarrow r)}} \\\ end {align}}}$	${\displaystyle ((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))}$	Esportazione
${\displaystyle {\begin{allineato}p\rightarrow q\\\quindi {\overline {\neg q\rightarrow\neg ​​p}}\\\end{allineato}}}$	${\displaystyle (p\rightarrow q)\rightarrow (\neg q\rightarrow\neg ​​p)}$	Legge di trasposizione o contrapposizione
${\displaystyle {\begin{allineato}p\rightarrow q\\q\rightarrow r\\\quindi {\overline {p\rightarrow r}}\\\end{allineato}}}$	${\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r))\rightarrow (p\rightarrow r)}$	sillogismo ipotetico
${\displaystyle {\begin{allineato}p\rightarrow q\\\quindi {\overline {\neg p\vee q}}\\\end{allineato}}}$	${\displaystyle (p\rightarrow q)\rightarrow (\neg p\vee q)}$	Implicazione materiale
${\displaystyle {\begin{allineato}(p\vee q)\cuneo r\\\quindi {\overline {(p\cuneo r)\vee (q\cuneo r)}}\\\end{allineato}} }$	${\ Displaystyle ((p\vee q)\cuneo r)\rightarrow ((p\cuneo r)\vee (q\cuneo r))}$	Distributivo
${\displaystyle {\begin{allineato}p\rightarrow q\\\quindi {\overline {p\rightarrow (p\wedge q)}}\\\end{allineato}}}$	${\displaystyle (p\rightarrow q)\rightarrow (p\rightarrow (p\wedge q))}$	Assorbimento
${\displaystyle {\begin{allineato}p\vee q\\\neg p\\\quindi {\overline {q\quad \quad \quad}}\\\end{allineato}}}$	${\displaystyle ((p\vee q)\wedge \neg p)\rightarrow q}$	sillogismo disgiuntivo
${\displaystyle {\begin{allineato}p\\\quindi {\overline {p\vee q}}\\\end{allineato}}}$	${\ Displaystyle p \ rightarrow (p \ vee q)}$	aggiunta
${\displaystyle {\begin{allineato}p\cuneo q\\\quindi {\overline {p\quad \quad \quad}}\\\end{allineato}}}$	${\displaystyle (p\cuneo q)\rightarrow p}$	Semplificazione
${\displaystyle {\begin{allineato}p\\q\\\quindi {\overline {p\cuneo q}}\\\end{allineato}}}$	${\displaystyle ((p)\cuneo (q))\freccia destra (p\cuneo q)}$	Congiunzione
${\ displaystyle {\ begin {allineato} p \\\ quindi {\ overline {\ neg \ neg p}} \\\ end {allineato}}}$	${\ Displaystyle p \ rightarrow (\ neg \ neg p)}$	Doppia negazione
${\displaystyle {\begin{allineato}p\vee p\\\quindi {\overline {p\quad \quad \quad}}\\\end{allineato}}}$	${\displaystyle (p\vee p)\rightarrow p}$	Semplificazione disgiuntiva
${\displaystyle {\begin{allineato}p\vee q\\\neg p\vee r\\\quindi {\overline {q\vee r}}\\\end{allineato}}}$	${\displaystyle ((p\vee q)\wedge (\neg p\vee r))\rightarrow (q\vee r)}$	Risoluzione
${\displaystyle {\begin{allineato}p\rightarrow q\\r\rightarrow q\\p\vee r\\\quindi {\overline {q\quad \quad \quad}}\\\end{allineato}} }$	${\displaystyle ((p\rightarrow q)\wedge (r\rightarrow q)\wedge (p\vee r))\rightarrow q}$	Eliminazione della disgiunzione

Tutte le regole utilizzano gli operatori logici di base. Una tabella completa di "operatori logici" è rappresentata da una tabella di verità , che fornisce le definizioni di tutte le possibili (16) funzioni di verità di 2 variabili booleane ( p , q ):

p	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

dove T = vero e F = falso, e, le colonne sono gli operatori logici: 0 , falso, Contraddizione ; 1 , NOR, NOR logico (freccia di Peirce); 2 , Converse nonimplication ; 3 , ¬p , Negazione ; 4 , non implicazione materiale ; 5 , ¬q , Negazione; 6 , XOR, Disgiunzione esclusiva ; 7 , NAND, NAND logica (corsa di Sheffer); 8 , AND, Congiunzione logica ; 9 , XNOR, Se e solo se , Logico bicondizionale ; 10 , q , funzione di proiezione ; 11 , se / allora, Implicazione logica ; 12 , p , Funzione di proiezione; 13 , then / if, Implicazione Converse ; 14 , OR, Disgiunzione logica ; 15 , vero, Tautologia .

Ogni operatore logico può essere utilizzato in un'asserzione su variabili e operazioni, mostrando una regola di inferenza di base. Esempi:

• L'operatore della colonna 14 (OR) mostra la regola dell'addizione : quando p = T (l'ipotesi seleziona le prime due righe della tabella), vediamo (alla colonna 14) che p ∨ q = T.

  Si vede anche che, con la stessa premessa, sono valide altre conclusioni: le colonne 12, 14 e 15 sono T.

• L'operatore della colonna 8 (AND), mostra la regola di semplificazione : quando p ∧ q =T (prima riga della tabella), vediamo che p =T.

  Con questa premessa, concludiamo anche che q =T, p ∨ q =T, ecc. come mostrato dalle colonne 9-15.

• L'operatore della colonna 11 (IF/THEN), mostra la regola del Modus ponens : quando p → q =T ep =T solo una riga della tavola di verità (la prima) soddisfa queste due condizioni. Su questa linea, anche q è vero. Pertanto, ogni volta che p → q è vero e p è vero, anche q deve essere vero.

Le macchine e le persone ben addestrate usano questo approccio alla tabella per fare inferenze di base e per verificare se è possibile ottenere altre inferenze (per le stesse premesse).

Esempio 1

Considera le seguenti ipotesi: "Se piove oggi, allora non andremo in canoa oggi. Se non andiamo in canoa oggi, allora faremo un viaggio in canoa domani. Pertanto (Simbolo matematico per "quindi" è ), se oggi piove, domani faremo una gita in canoa". Per utilizzare le regole di inferenza nella tabella sopra, sia la proposizione "Se piove oggi", sia "Non andremo in canoa oggi" e sia "Domani andremo in canoa". Allora questo argomento è della forma: ${\ displaystyle \ quindi}$${\displaystyle p}$${\displaystyle q}$${\displaystyle r}$

${\displaystyle {\begin{allineato}p\rightarrow q\\q\rightarrow r\\\quindi {\overline {p\rightarrow r}}\\\end{allineato}}}$

Esempio 2

Consideriamo una serie di ipotesi più complesse: "Non c'è il sole oggi e fa più freddo di ieri". "Andremo a nuotare solo se c'è il sole", "Se non andiamo a nuotare, allora faremo un barbecue", e "Se faremo un barbecue, allora saremo a casa entro il tramonto" portano alla conclusione " Saremo a casa al tramonto". Dimostrazione mediante regole di inferenza: Sia la proposizione "Oggi c'è il sole", la proposizione "Fa più freddo di ieri", la proposizione "Andremo a nuotare", la proposizione "Faremo un barbecue" e la proposta " Saremo a casa al tramonto". Allora le ipotesi diventano e . Usando la nostra intuizione congetturiamo che la conclusione potrebbe essere . Usando la tabella delle regole di inferenza possiamo dimostrare facilmente la congettura: ${\displaystyle p}$${\displaystyle q}$${\displaystyle r}$${\ displaystyle s}$${\displaystyle}$${\displaystyle\neg p\wedge q,r\rightarrow p,\neg r\rightarrow s}$${\displaystyle s\rightarrow t}$${\displaystyle}$

Passo	Motivo
1.${\displaystyle\neg p\cuneo q}$	Ipotesi
2. ${\displaystyle \neg p}$	Semplificazione utilizzando il passaggio 1
3. ${\displaystyle r\rightarrow p}$	Ipotesi
4. ${\displaystyle \neg r}$	Modus tollens utilizzando i passaggi 2 e 3
5. ${\displaystyle \neg r\rightarrow s}$	Ipotesi
6. ${\ displaystyle s}$	Modus ponens utilizzando i passaggi 4 e 5
7. ${\displaystyle s\rightarrow t}$	Ipotesi
8. ${\displaystyle}$	Modus ponens utilizzando i passaggi 6 e 7

Riferimenti

Guarda anche

Elenco dei sistemi logici