Calcolo delle proposizioni - tautologie
Ho trovato su internet alcuni esempi di tautologie, e mi sono imbattuto nei due seguenti:
1.
|= ( $ A ^^ B $ ) -> A
che traduco come "la sentenza ( $ A ^^ B $ ) -> A è soddisfacibile sempre", poichè alla sinistra del simbolo di "soddisfacibilità" |= non c'è alcuna condizione
2.
A,B |= ( $ A ^^ B $ ) -> B
che traduco come "la sentenza ( $ A ^^ B $ ) -> B è soddisfacibile quando A e B sono vere", poichè alla sinistra del simbolo di "soddisfacibilità" |= c'è la condizione A,B
Utilizzando le tabelle di verità, mi ritrovo con il primo esempio, ma non con il secondo.
Direi infatti che anche la seconda è sempre soddisfacibile, indipendentemente dal valore di A, B, ovvero |= ( $ A ^^ B $ ) -> B
Ciò non toglie che comunque il secondo esempio risulta corretto, ma meno generale.
E' corretto il mio ragionamento?
Grazie
1.
|= ( $ A ^^ B $ ) -> A
che traduco come "la sentenza ( $ A ^^ B $ ) -> A è soddisfacibile sempre", poichè alla sinistra del simbolo di "soddisfacibilità" |= non c'è alcuna condizione
2.
A,B |= ( $ A ^^ B $ ) -> B
che traduco come "la sentenza ( $ A ^^ B $ ) -> B è soddisfacibile quando A e B sono vere", poichè alla sinistra del simbolo di "soddisfacibilità" |= c'è la condizione A,B
Utilizzando le tabelle di verità, mi ritrovo con il primo esempio, ma non con il secondo.
Direi infatti che anche la seconda è sempre soddisfacibile, indipendentemente dal valore di A, B, ovvero |= ( $ A ^^ B $ ) -> B
Ciò non toglie che comunque il secondo esempio risulta corretto, ma meno generale.
E' corretto il mio ragionamento?
Grazie
Risposte
Il tuo ragionamento è corretto. La seconda formula neanch'io la userei come esempio di tautologia, puoi leggerla infatti come "$(A^^B)->B$ è conseguenza logica dell'insieme di formule ${A,B}$", e può - come hai notato - creare un po' di perplessità. A proposito,
[ Io cambierei anche la terminologia: non dire che una formula è "sempre soddisfacibile" ma semmai che è sempre soddisfatta (è la definizione di tautologia). Sono un po' fissato.
]
"Matdan":dove l'hai trovata?
Ho trovato su internet alcuni esempi di tautologie...
[ Io cambierei anche la terminologia: non dire che una formula è "sempre soddisfacibile" ma semmai che è sempre soddisfatta (è la definizione di tautologia). Sono un po' fissato.
]
Molte grazie per la risposta.
In merito alla tua richiesta
gli esempi da me citati li ho trovati su un wikibook, al seguente link
http://it.wikibooks.org/wiki/Logica/Cal ... oposizioni
da cui ho tratto la terminologia che ho utilizzato nel post precedente.
Ciao e grazie
In merito alla tua richiesta
"Rggb":
dove l'hai trovata?
gli esempi da me citati li ho trovati su un wikibook, al seguente link
http://it.wikibooks.org/wiki/Logica/Cal ... oposizioni
da cui ho tratto la terminologia che ho utilizzato nel post precedente.
Ciao e grazie
Allora va bene: se infatti leggi il contesto capisci che gli esempi fatti non sono solo di tautologie.
Anche se effettivamente il tutto è sotto un capoverso titolato "Soddisfacibilità", il redattore non si è accorto di aver messo gli esempi (per le formule soddisfacibili ed il simbolo |= introdotto), subito dopo aver detto cosa è una tautologia, e questo crea confusione.
[ Magari puoi cambiarlo, che dici? ]
Anche se effettivamente il tutto è sotto un capoverso titolato "Soddisfacibilità", il redattore non si è accorto di aver messo gli esempi (per le formule soddisfacibili ed il simbolo |= introdotto), subito dopo aver detto cosa è una tautologia, e questo crea confusione.
[ Magari puoi cambiarlo, che dici? ]
Il secondo esempio è una tautologia: qualsiasi siano i valori delle variabili proposizionali A, B , la sequenza implicata (l'implicazione che ha come antecedente la congiunzione di A e B e come conseguente B) è sempre vera! Per definizione una tautologia è proprio questo: non interessano i valori di verità delle variabili, perchè la sequenza derivante da esse sarà SEMPRE vera. Verificarlo con le tavole di verità è semplice e ci dice proprio questo. Inoltre possiamo dire anche un'altra cosa interessante: ogni sequenza tautologica è derivabile come teorema. Ora che la prima formula sia derivabile si verifica facilmente tramite l'assunzione della congiunzione da cui deriva uno dei due congiunti, quindi è possibile concludere l'implicazione scaricando l'assunzione della congiunzione.
Per la seconda c'è da fare un altro tipo di ragionamento:
1) Entrambe le premesse non servono, infatti per giungere a quella conclusione, ovvero (P & Q) -> P (o Q) c'è un semplice teorema che ce lo dice sempre, dunque in verità non servono quelle premesse.
2) Quelle premesse servono invece se vogliamo provare la doppia implicazione, ovvero la congiunzione tra il teorema (prima formula) e l'implicazione inversa.
3) Eppure è un processo semplificato, inoltre una delle premesse verrà "scaricata" per deduzione naturale grazie al processo di introduzione dell'implicazione materiale.
Quindi:
- la seconda formula è una tautologia;
- la conclusione non ha bisogno delle premesse A,B per essere tautologica e descritta con un teorema, ovvero senza assunzioni;
- la conclusione derivabile dalle assunzioni della seconda formula è PIU' DEBOLE di quella effettivamente derivabile, ovvero la doppia implicazione;
- le premesse della seconda formula SONO PIU' di quelle utili effettivamente per derivare la doppia implicazione, infatti una delle due è scaricabile tramite l'introduzione del condizionale;
Probabilmente quel tipo di esempio era solo utile per sviluppare le tavole di verità, visto che per le tavole di verità ho bisogno di elencare sia A che B e vedere se siano vere o false e cosa accade alla formula successiva!
Oppure era solo per vedere che, tramite la deduzione naturale, non bastava assumere solo una delle due variabili, ma entrambe, anche se poi infine una delle due assunzioni non sarebbe servita a darci la conclusione voluta.
Esemplifico la deduzione: (formalizzo come segue: alla sinistra scrivo le assunzioni da cui dipendono, tra parentesi la riga dove siamo, a destra le righe utilizzate per la regola di derivazione descritta)
1 (1) A Assunzione
2 (2) B Assunzione
1,2 (3) (A && B) 1,2 Introduzione della congiunzione
(4) (A && B) -> B Introduzione di teorema (non necessita assunzioni per definizione)
1 (5) B -> (A && B) 2,3 Introduzione di condizionale (scarica le assunzioni da cui deriva l'antecedente)
1 (6) (B -> (A && B)) && ((A && B) -> B) 4,5 Introduzione di congiunzione
1 (7) B <----> (A && B) 6, Definizione di doppia implicazione
A questo punto dalla conclusione posso sicuramente dedurre sia l'una che l'altra implicazione e fortunatamente dipenderà solo da un'assunzione e non da entrambe... (eliminando la congiunzione, ma è sicuramente inutile farlo poichè se volevo dedurre la prima implicazione bastava il teorema senza assunzioni, e per l'altra implicazione bastavano meno righe di deduzione (togli righe 4, 6, 7)
EDIT: Ho letto ora il paragrafo dove fa quegli esempi e se vedete, quando scrive le premesse A,B per quella formula, A la lascia in grassetto, B no. Potrebbe stare a significare proprio che B è solo un'assunzione temporanea e scaricabile in seguito.
Per la seconda c'è da fare un altro tipo di ragionamento:
1) Entrambe le premesse non servono, infatti per giungere a quella conclusione, ovvero (P & Q) -> P (o Q) c'è un semplice teorema che ce lo dice sempre, dunque in verità non servono quelle premesse.
2) Quelle premesse servono invece se vogliamo provare la doppia implicazione, ovvero la congiunzione tra il teorema (prima formula) e l'implicazione inversa.
3) Eppure è un processo semplificato, inoltre una delle premesse verrà "scaricata" per deduzione naturale grazie al processo di introduzione dell'implicazione materiale.
Quindi:
- la seconda formula è una tautologia;
- la conclusione non ha bisogno delle premesse A,B per essere tautologica e descritta con un teorema, ovvero senza assunzioni;
- la conclusione derivabile dalle assunzioni della seconda formula è PIU' DEBOLE di quella effettivamente derivabile, ovvero la doppia implicazione;
- le premesse della seconda formula SONO PIU' di quelle utili effettivamente per derivare la doppia implicazione, infatti una delle due è scaricabile tramite l'introduzione del condizionale;
Probabilmente quel tipo di esempio era solo utile per sviluppare le tavole di verità, visto che per le tavole di verità ho bisogno di elencare sia A che B e vedere se siano vere o false e cosa accade alla formula successiva!
Oppure era solo per vedere che, tramite la deduzione naturale, non bastava assumere solo una delle due variabili, ma entrambe, anche se poi infine una delle due assunzioni non sarebbe servita a darci la conclusione voluta.
Esemplifico la deduzione: (formalizzo come segue: alla sinistra scrivo le assunzioni da cui dipendono, tra parentesi la riga dove siamo, a destra le righe utilizzate per la regola di derivazione descritta)
1 (1) A Assunzione
2 (2) B Assunzione
1,2 (3) (A && B) 1,2 Introduzione della congiunzione
(4) (A && B) -> B Introduzione di teorema (non necessita assunzioni per definizione)
1 (5) B -> (A && B) 2,3 Introduzione di condizionale (scarica le assunzioni da cui deriva l'antecedente)
1 (6) (B -> (A && B)) && ((A && B) -> B) 4,5 Introduzione di congiunzione
1 (7) B <----> (A && B) 6, Definizione di doppia implicazione
A questo punto dalla conclusione posso sicuramente dedurre sia l'una che l'altra implicazione e fortunatamente dipenderà solo da un'assunzione e non da entrambe... (eliminando la congiunzione, ma è sicuramente inutile farlo poichè se volevo dedurre la prima implicazione bastava il teorema senza assunzioni, e per l'altra implicazione bastavano meno righe di deduzione (togli righe 4, 6, 7)
EDIT: Ho letto ora il paragrafo dove fa quegli esempi e se vedete, quando scrive le premesse A,B per quella formula, A la lascia in grassetto, B no. Potrebbe stare a significare proprio che B è solo un'assunzione temporanea e scaricabile in seguito.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo