Dimostrazione di una proposizione di logica matematica
Salve, sono una studentessa di matematica all'ultimo anno, mi mancano 8 esami.
Ben 3 volte sono stata rimandata nell'esame di Logica matematica perchè non sapevo rispondere alla domanda: "dimostrami che ogni formula ben formata logicamente valida è un teorema, usando lo schema di assiomi A1-A3 e il Modus Pones"
Il mio problema è, dove la applico l'induzione?
Comunque ho provato vari metodi, vorrei sapere almeno se l'impostazione è giusta:
Per ipotesi A è una f.b.f. logicamente valida allora A è vera per ogni interpretazione, segue che A è soddisfatta pertanto ogni successione soddisfa A.
Dobbiamo provare che esiste una sequenza B1,B2,...,Bn f.b.f. t.c. per ogni i=1,...,n Bi è un assioma, Bi è conseguenza diretta di f.b.f. precendenti per mezzo delle regole di inferenza o che Bi=A
Procediamo per induzione su i: I PASSO: n=1 B1 è una f.b.f. nell teoria del primo ordine, allora B1 è una formula atomica, allora esiste una successione s che soddisfa B1, ma tale successione soddisfa anche A allora per l'assioma A1 vale la tesi.
II PASSO: Supponiamo vera la tesi per Bn-1 e proviamo per Bn, Per il passo induttivo B1,B2,...,Bn-1 è un dimostrazione di A...Non riesco piu ad andare avanti
Non so se l'impostazione è giusta, per favore potreste aiutarmi?
Grazie mille
Ben 3 volte sono stata rimandata nell'esame di Logica matematica perchè non sapevo rispondere alla domanda: "dimostrami che ogni formula ben formata logicamente valida è un teorema, usando lo schema di assiomi A1-A3 e il Modus Pones"
Il mio problema è, dove la applico l'induzione?
Comunque ho provato vari metodi, vorrei sapere almeno se l'impostazione è giusta:
Per ipotesi A è una f.b.f. logicamente valida allora A è vera per ogni interpretazione, segue che A è soddisfatta pertanto ogni successione soddisfa A.
Dobbiamo provare che esiste una sequenza B1,B2,...,Bn f.b.f. t.c. per ogni i=1,...,n Bi è un assioma, Bi è conseguenza diretta di f.b.f. precendenti per mezzo delle regole di inferenza o che Bi=A
Procediamo per induzione su i: I PASSO: n=1 B1 è una f.b.f. nell teoria del primo ordine, allora B1 è una formula atomica, allora esiste una successione s che soddisfa B1, ma tale successione soddisfa anche A allora per l'assioma A1 vale la tesi.
II PASSO: Supponiamo vera la tesi per Bn-1 e proviamo per Bn, Per il passo induttivo B1,B2,...,Bn-1 è un dimostrazione di A...Non riesco piu ad andare avanti
Non so se l'impostazione è giusta, per favore potreste aiutarmi?
Grazie mille
Risposte
"PuPa!":
Ben 3 volte sono stata rimandata nell'esame di Logica matematica perchè non sapevo rispondere alla domanda: "dimostrami che ogni formula ben formata logicamente valida è un teorema, usando lo schema di assiomi A1-A3 e il Modus Pones"
Questo e' il famoso teorema di completezza, la cui dimostrazione si trova in quasi ogni libro di testo.
Ma chi sono gli assomi A1-A3? Cerca almeno di formulare il problema prima di postare
Comunque ho provato vari metodi, vorrei sapere almeno se l'impostazione è giusta:
Per ipotesi A è una f.b.f. logicamente valida allora A è vera per ogni interpretazione, segue che A è soddisfatta pertanto ogni successione soddisfa A.
Successione? Di cosa stai parlando, se vuoi un aiuto dovresti chiarire la terminologia che usi, io personalmente non l'ho mai incontrata.
Non so se l'impostazione è giusta, per favore potreste aiutarmi?
Temo che l'impostazione non sia giusta (ma mai dire mai!), il teorema che stai cercando e' un risultato classico della teoria, la cui dimostrazione non puo' essere improvvisata...
Intanto rispondo a tutti: Non è il teorema di completezza inquanto quello è nell teoria assiomatica, questo è l'analogo nell teoria del 1 ordine e la dimostrazione è diversa.
La successione che uso è quella dei criteri di soddisfacibilità, il teorema che dice: " Una successione soddisfa una f.b.f."
Sui libri non c'è la dimostrazione, in nessun libro è dimostrato pertanto sto cercando di farlo io nel modo piu giusto possibile visto che mi ha rimandato 3 volte.
Per quanto riguarda gli assiomi: A1: A implica(B implica A)
A2: (A implica(B implica C)) implica((A implica B) implica (A implica C))
Ora vi enuncio il nuovo tentativo sperando sia giusto:
Sia A una f.b.f. logicamente valida
Siano B1,B2,...,Bn f.b.f.
Proviamo che per ogni i Bi è un assioma, Bi è conseguenza logica di f.b.f. precedenti e Bn=A
Procediamo per induzione su i:
I PASSO: i=1
Sia s una successione che soddisfa B1, allora, siccome A è soddisfatta per ipotesi, s soddisfa anche A, allora ogni successione che soddisfa B1 soddisfa anche A, pertanto B1 implica logicamente A e dunque (B1 implica A) è logicamente valida. Allora per l'assioma A1 e il Modus Ponens B1 è un assioma.
Inoltre (B1 implica A) è logicamente valida, A è logicamente valida allora B1=A
II PASSO: Supponiamo vera la tesi per Bk per ogni k minore di i e proviamo per i
Per il passo induttivo Bk è un assioma e un conseguenza logica di f.b.f. allora Bk è logicmente valida, per ipotesi lo è anche A allora (A implica Bk) è logicamente valida, considerando l'assioma A2 e il Modus Ponens (A implica Bi) è logicamente valida inoltre A è vera per ogni interpretazione allora Bi è vera dunque la tesi.
La successione che uso è quella dei criteri di soddisfacibilità, il teorema che dice: " Una successione soddisfa una f.b.f."
Sui libri non c'è la dimostrazione, in nessun libro è dimostrato pertanto sto cercando di farlo io nel modo piu giusto possibile visto che mi ha rimandato 3 volte.
Per quanto riguarda gli assiomi: A1: A implica(B implica A)
A2: (A implica(B implica C)) implica((A implica B) implica (A implica C))
Ora vi enuncio il nuovo tentativo sperando sia giusto:
Sia A una f.b.f. logicamente valida
Siano B1,B2,...,Bn f.b.f.
Proviamo che per ogni i Bi è un assioma, Bi è conseguenza logica di f.b.f. precedenti e Bn=A
Procediamo per induzione su i:
I PASSO: i=1
Sia s una successione che soddisfa B1, allora, siccome A è soddisfatta per ipotesi, s soddisfa anche A, allora ogni successione che soddisfa B1 soddisfa anche A, pertanto B1 implica logicamente A e dunque (B1 implica A) è logicamente valida. Allora per l'assioma A1 e il Modus Ponens B1 è un assioma.
Inoltre (B1 implica A) è logicamente valida, A è logicamente valida allora B1=A
II PASSO: Supponiamo vera la tesi per Bk per ogni k minore di i e proviamo per i
Per il passo induttivo Bk è un assioma e un conseguenza logica di f.b.f. allora Bk è logicmente valida, per ipotesi lo è anche A allora (A implica Bk) è logicamente valida, considerando l'assioma A2 e il Modus Ponens (A implica Bi) è logicamente valida inoltre A è vera per ogni interpretazione allora Bi è vera dunque la tesi.
Posso consigliare di usa il MathML o il TeX: sarebbe più leggibile quello che scrivi.
PuPa!, francamente vorrei aiutarti, ma sei estremamente incompleta e imprecisa:
- Gli assiomi A1-A3 sono diventati solo 2, A1 e A2?
- Si tratta di logica proposizionale, quella senza quantificatori?
- Puoi dare una definizione rigorosa di "successione" come la intendi tu, credo che nessuno possa capirti altrimenti
- Puoi enunciare con precisione quello che intendi dimostrare? Nel tuo primo post hai enunciato il teorema di completezza, senza se e senza ma.
Se vuoi passare l'esame di logica, ti consiglio di impare il rigore che tale materia richiede.
- Gli assiomi A1-A3 sono diventati solo 2, A1 e A2?
- Si tratta di logica proposizionale, quella senza quantificatori?
- Puoi dare una definizione rigorosa di "successione" come la intendi tu, credo che nessuno possa capirti altrimenti
- Puoi enunciare con precisione quello che intendi dimostrare? Nel tuo primo post hai enunciato il teorema di completezza, senza se e senza ma.
Se vuoi passare l'esame di logica, ti consiglio di impare il rigore che tale materia richiede.
Allora, se potessi vi darei il libro ma nn posso...
Gli assiomi che ho usato sono solo A1 e A2, l'A3 nn sono riuscita ad inserirlo per questo sto chiedendo aiuto.
Per quanto rigurda la successione: CRITERI DI SODDISFACIBILITA è un teorema che mette questa successione, non la definisce, dice solo che una successione s=(b1,b2,..bn) soddisfa una formula ben formata.
Il Teorema di completezza dice: OGNI TAUTOLOGIA è UN TEOREMA e lo dimostra tramite il TEOREMA DI DEDUZIONE e un LEMMA.
Il teorema che serve a me è: OGNI FORMULA BEN FORMATA E' UN TEOREMA dove il mio professore vuole la dimostrazione per induzione e non come quella di completezza.
SONO STATA PIU CHIARA?
Gli assiomi che ho usato sono solo A1 e A2, l'A3 nn sono riuscita ad inserirlo per questo sto chiedendo aiuto.
Per quanto rigurda la successione: CRITERI DI SODDISFACIBILITA è un teorema che mette questa successione, non la definisce, dice solo che una successione s=(b1,b2,..bn) soddisfa una formula ben formata.
Il Teorema di completezza dice: OGNI TAUTOLOGIA è UN TEOREMA e lo dimostra tramite il TEOREMA DI DEDUZIONE e un LEMMA.
Il teorema che serve a me è: OGNI FORMULA BEN FORMATA E' UN TEOREMA dove il mio professore vuole la dimostrazione per induzione e non come quella di completezza.
SONO STATA PIU CHIARA?
"PuPa!":
Allora, se potessi vi darei il libro ma nn posso...
Gli assiomi che ho usato sono solo A1 e A2, l'A3 nn sono riuscita ad inserirlo per questo sto chiedendo aiuto.
Quindi gli assiomi non sono dati, sei tu che devi trovarii? Suona strano.
Per quanto rigurda la successione: CRITERI DI SODDISFACIBILITA è un teorema che mette questa successione, non la definisce, dice solo che una successione s=(b1,b2,..bn) soddisfa una formula ben formata.
Scusa, ma la tua frase non e' molta chiara nemmeno in italiano.
Il Teorema di completezza dice: OGNI TAUTOLOGIA è UN TEOREMA e lo dimostra tramite il TEOREMA DI DEDUZIONE e un LEMMA.
Qui ci siamo.
Il teorema che serve a me è: OGNI FORMULA BEN FORMATA E' UN TEOREMA dove il mio professore vuole la dimostrazione per induzione e non come quella di completezza.
Temo che non sia cosi'. Vuoi cercare di dimostrare che ogni formula ben formata e' dimostrabile?
Quindi il tuo sistema sarebbe inconsistente: data una formula ben formata $A$, anche $\neg A$ e' ben formata, quindi sia $A$ che $\neg A$ sarebbero teoremi...Non so se ti rendi conto, ma sei incomprensibile. Provo a tirare ad indovinare io: stai cercando di dimostrare che, per ogni successione di formule che rappresenta una dimostrazione di una formula $A$, $A$ e' logicamente valida, ovvero una tautologia, ovvero un teorema in senso semantico? Questo si dimostrarebbe per induzione, e si chiama talvolta teorema di correttezza.
"fields":
[quote="PuPa!"]Il teorema che serve a me è: OGNI FORMULA BEN FORMATA E' UN TEOREMA dove il mio professore vuole la dimostrazione per induzione e non come quella di completezza.
Temo che non sia cosi'. Vuoi cercare di dimostrare che ogni formula ben formata e' dimostrabile?
Quindi il tuo sistema sarebbe inconsistente: data una formula ben formata $A$, anche $\neg A$ e' ben formata, quindi sia $A$ che $\neg A$ sarebbero teoremi...Non so se ti rendi conto, ma sei incomprensibile. Provo a tirare ad indovinare io: stai cercando di dimostrare che, per ogni successione di formule che rappresenta una dimostrazione di una formula $A$, $A$ e' logicamente valida, ovvero una tautologia, ovvero un teorema in senso semantico? Questo si dimostrarebbe per induzione, e si chiama talvolta teorema di correttezza.[/quote]
L'enunciato non è "ogni fbf è un teorema" ma è invece "ogni fbf logicamente valida è un teorema"; PuPa! fai attenzione a quando scrivi
La dimostrazione non me la ricordo [c'è anche su un libro che avevo afaik] ma non credo sia difficile.
Allora, mi scuso pre aver scritto il teorema: "ogni formula ben formata è un teorema" in quanto quello giusto è: "ogni f.b.f. logicamente valida è un teorema".
Per quanto riguarda gli assiomi A1 A2 A3 sono dati non li ho trovati io, li devo usare nella dimostrazione, ma non riesco ad introdurre il l'A3.
Grazie per l'ultima risposta, effettivamente quello che mi serve è il teorema di correttezza, ma che purtroppo sul mio libro non lo dimostra e il mio professore si accanisce che lo vuole per induzione, sto cercando in tutti di i modi di dimostrarlo.
Comunque, grazie anche per il libro che mi avete consigliato, tra qualche minuto affronterò l'esame e se per la quarta volta mi rimanda provvedero di trovare tale libro.
SPERO IN BENE anche perchè mi sta bloccando il corso di studio (a luglio dovrei laurearmi)
GRAZIE COMUNQUE A TUTTI PER L'IMPEGNO MESSO
Per quanto riguarda gli assiomi A1 A2 A3 sono dati non li ho trovati io, li devo usare nella dimostrazione, ma non riesco ad introdurre il l'A3.
Grazie per l'ultima risposta, effettivamente quello che mi serve è il teorema di correttezza, ma che purtroppo sul mio libro non lo dimostra e il mio professore si accanisce che lo vuole per induzione, sto cercando in tutti di i modi di dimostrarlo.
Comunque, grazie anche per il libro che mi avete consigliato, tra qualche minuto affronterò l'esame e se per la quarta volta mi rimanda provvedero di trovare tale libro.
SPERO IN BENE anche perchè mi sta bloccando il corso di studio (a luglio dovrei laurearmi)
GRAZIE COMUNQUE A TUTTI PER L'IMPEGNO MESSO
HO SUPERATO L'ESAMEEEEEEEEEEEEEEEEEEEEEEEEEE 
QUEL TEOREMA NON ME L'HA CHIESTO. GRAZIE A TUTTI DAVVERO
QUEL TEOREMA NON ME L'HA CHIESTO. GRAZIE A TUTTI DAVVERO
"PuPa!":
HO SUPERATO L'ESAMEEEEEEEEEEEEEEEEEEEEEEEEEE
Congrats
Comunque mi è rimasto il tarlo... appena riprendo il libro in mano cercherò di colmare questa lacuna.
A chi interessasse...
Ho ritrovato la dimostrazione che cercava PuPa! su degli appunti di logica che avevo scaricato dalla rete per un esame. Non ho ritrovato gli stessi identici appunti in rete, ma l'autore ne ha di meglio
http://www.dmi.unisa.it/people/gerla/www/
Prof. Gerla, Università di SA, corso di Logica Matematica.
Ho ritrovato la dimostrazione che cercava PuPa! su degli appunti di logica che avevo scaricato dalla rete per un esame. Non ho ritrovato gli stessi identici appunti in rete, ma l'autore ne ha di meglio
http://www.dmi.unisa.it/people/gerla/www/
Prof. Gerla, Università di SA, corso di Logica Matematica.
Interessante. Grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo