Sapete tutti cos'è vero? Il teorema di deduzione nella logica matematica intendo.
Vorrei sapere il perchè, la spiegazione in parole povere , chiare.
Nel libro di Mendelson (introduzione alla logica matematica) non si riesce a capire molto bene (è scritto in maniera che uno che vuole introdursi alla logica matematica non ci si possa introdurre).
Grazie.
Teorema di deduzione?
-
Nonno Bassotto
- Site Admin
- Messaggi: 970
- Iscritto il: 14 mag 2006, 17:51
- Località: Paris
- Contatta:
No, non lo conosco, almeno con questo nome (magari è una banalità...)
Comunque mi sembra già un buon motivo per spostarlo in Matematica non elementare
Una breve occhiata a wikipedia mi conferma che non è niente di stravagante, ma non è una cattiva idea introdurre l'argomento di cui si parla invece di assumere che tutti sappiano cos'è. Ciao
Comunque mi sembra già un buon motivo per spostarlo in Matematica non elementare
Una breve occhiata a wikipedia mi conferma che non è niente di stravagante, ma non è una cattiva idea introdurre l'argomento di cui si parla invece di assumere che tutti sappiano cos'è. Ciao
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
http://it.wikipedia.org/wiki/Teorema_di_deduzione
per quel che ho capito io: se X è deducibile da Y, allora Y -> X (tautologia)
Questo è quello che ho capito.
per quel che ho capito io: se X è deducibile da Y, allora Y -> X (tautologia)
Questo è quello che ho capito.
Il teorema dice questo: sia X = {X1, X2, ..., Xn} un insieme finito di formule; se, prendendo X come insieme di assiomi, si può dimostrare Y, allora si può dimostrare, senza usare assiomi, la formula (X1 e X2 e ... e Xn) -> Y.
La dimostrazione di questo teorema cambia in base al tipo di logica del primo ordine che si sta usando (deduzione naturale, Hilbert, sequenti, ecc...).
Con la logica del primo ordine di Hilbert (molti assiomi base, ma una sola regola di deduzione, il modus ponens), il teorema non è facile da dimostrare (si dimostra per induzione sulla lunghezza della dimostrazione di Y).
Clamorosamente, con la deduzione naturale il teorema è immediato: la d.n. non ha assiomi base, ma ha molte regole di deduzione, tra le quali una che è praticamente il teorema in questione.
La dimostrazione di questo teorema cambia in base al tipo di logica del primo ordine che si sta usando (deduzione naturale, Hilbert, sequenti, ecc...).
Con la logica del primo ordine di Hilbert (molti assiomi base, ma una sola regola di deduzione, il modus ponens), il teorema non è facile da dimostrare (si dimostra per induzione sulla lunghezza della dimostrazione di Y).
Clamorosamente, con la deduzione naturale il teorema è immediato: la d.n. non ha assiomi base, ma ha molte regole di deduzione, tra le quali una che è praticamente il teorema in questione.
Bene, io dovrei dimostrare il teorema di deduzione nel sistema assiomatico L descritto in Mendelson (introduzione alla logica matematica) che si basa su 3 assiomi e sul modus ponens: (NON lo segnerò con lettere minuscole)
1) A->(B->A)
2) (A->(B->C))->((A->B)->(A->C)
3) (b->a)->((b->A)->B)
e nauralmente in modus ponens : A->B, A | B.
Come si può fare per dimostrare il teorema di deduzione con questi assiomi?
1) A->(B->A)
2) (A->(B->C))->((A->B)->(A->C)
3) (b->a)->((b->A)->B)
e nauralmente in modus ponens : A->B, A | B.
Come si può fare per dimostrare il teorema di deduzione con questi assiomi?
Il tuo sistema è il calcolo delle proposizioni di Hilbert, suppongo (io conoscevo un assioma 3 diverso...).
La dimostrazione è un po' complicata, così ti segnalo le "note di logica 3" di R. Ferro che puoi trovare qui: http://www.scienze.univr.it/fol/main?en ... d=&lang=it
La dimostrazione che cerchi è a pag. 40; fa uso degli assiomi 1 e 2 che coincidono (il terzo è diverso, ma se non viene usato...).
La dimostrazione è un po' complicata, così ti segnalo le "note di logica 3" di R. Ferro che puoi trovare qui: http://www.scienze.univr.it/fol/main?en ... d=&lang=it
La dimostrazione che cerchi è a pag. 40; fa uso degli assiomi 1 e 2 che coincidono (il terzo è diverso, ma se non viene usato...).
