Deduzione Naturale per logica proposizionale
Salve ragazzi
Il mio problema tratta della Deduzione Naturale; non riesco a capire come si applicano le regole di inferenza.
Allora io ho imparato tutte le regole però data una frase gia formalizzata come faccio a capire quale è la prima regola da applicare?
tipo io ho questa frase
$not$(A$^^$B)=>(A$vv$B)
da dove devo cominciare?
Grazie a tutti
Il mio problema tratta della Deduzione Naturale; non riesco a capire come si applicano le regole di inferenza.
Allora io ho imparato tutte le regole però data una frase gia formalizzata come faccio a capire quale è la prima regola da applicare?
tipo io ho questa frase
$not$(A$^^$B)=>(A$vv$B)
da dove devo cominciare?
Grazie a tutti
Risposte
"NiCoLiNo":potrei sbagliarmi, ma non dovrebbe essere: $not$(A$^^$$B)=>(¬A) V (¬B)$; è la legge di De Morgan o non c'entra nulla?
tipo io ho questa frase
$not$(A$^^$B)=>(A$vv$B)
Si per quello hai ragione ma io stavo parlando di un'altro argomento
forse ti può tornare utile l'ultima pagina di questo pdf:
http://www.dsi.uniroma1.it/~lpara/LOGIC ... 211206.pdf
http://www.dsi.uniroma1.it/~lpara/LOGIC ... 211206.pdf
"NiCoLiNo":
Salve ragazzi
Il mio problema tratta della Deduzione Naturale; non riesco a capire come si applicano le regole di inferenza.
Allora io ho imparato tutte le regole però data una frase gia formalizzata come faccio a capire quale è la prima regola da applicare?
Sto sbattendo anch'io la testa contro la deduzione naturale in questi giorni. In generale non c'è un criterio per capire come eseguire una deduzione: si devono fare tanti, tanti, tanti esercizi in modo da sviluppare una certa sensibilità, come, ad esempio, nel caso dell'esecuzione degli integrali.
"NiCoLiNo":
tipo io ho questa frase
$not$(A$^^$B)=>(A$vv$B)
da dove devo cominciare?
Forse c'è qualche errore perché quella che hai indicato non è una deduzione valida...
Il link indicato da a.Smith è buono, anch'io ho utilizzato quel documento per impratichirmi. Piú utile di tutti è stato questo documento
www.cs.unibo.it/~corsi/FolderDidattica/ ... -dedud.pdf
dove ci sono una serie di esercizi svolti di varia difficoltà.
Anche se e' un post un poco datato.
In questo periodo sto preparando l'esame di Logica.
E devo dire che ci sono molti punti oscuri!
Per esempio. Se io ho una frase e devo dire se questa e' valida, soddisfacibile o non soddisfacibile.
Posso usare la tabella di verita'. Ma nel caso in cui i letterali siano troppi...cosa posso fare?
Che metodo usare? La deduzione naturale? E se si "come" ? A cosa devo arrivare?
Mi sento molto confusa
.
Ciau
In questo periodo sto preparando l'esame di Logica.
E devo dire che ci sono molti punti oscuri!
Per esempio. Se io ho una frase e devo dire se questa e' valida, soddisfacibile o non soddisfacibile.
Posso usare la tabella di verita'. Ma nel caso in cui i letterali siano troppi...cosa posso fare?
Che metodo usare? La deduzione naturale? E se si "come" ? A cosa devo arrivare?
Mi sento molto confusa
.Ciau
"acrobata":
Ma nel caso in cui i letterali siano troppi...cosa posso fare?
Che metodo usare?
Se i letterali sono troppi, non esiste un metodo che ti salvi. Devi vedere tu, di volta in volta, qual è quello che si adatta maggiormente alla tua formula.
Ah bene...
E allora deduzione naturale e risoluzione per clausole...a che servono? perche' le dovrei usare?
(sento che sto facendo domande che sanno un po' di bestemmia.)
E allora deduzione naturale e risoluzione per clausole...a che servono? perche' le dovrei usare?
(sento che sto facendo domande che sanno un po' di bestemmia.)
anche se avete parlato di "deduzione", la proposizione così scritta e qualche frase detta qua e là (come iniziare, tanti letterali, ...) mi fa pensare che il problema sia relativo alla logica proposizionale, e quindi dovresti studiare le tabelle logiche: per ogni proposizione di base (A, B, C, ...) esistono due possibili valori di verità (V, F). se hai due lettere, hai 4 casi da esaminare, se hai 3 lettere hai 8 casi, se hai n lettere hai $2^n$ casi. devi costruirti una tabella a partire dai singoli casi di base. sviluppi la proposizione composta come se fosse un'espressione algebrica, e potrai ottenere come risultato finale un vettore di $2^n$ valori in {V, F}. se hai tutti V, allora si tratta di una tautologia, se hai tutti F, si tratta di una contraddizione, se hai alcuni V ed alcuni F è una proposizione che può essere vera o falsa a seconda dei valori di verità delle proposizioni base. spero di essere stata chiara. facci sapere se è questo l'argomento da approfondire. ciao.
"acrobata":
E allora deduzione naturale e risoluzione per clausole...a che servono? perche' le dovrei usare?
Credo di non essere stato del tutto esauriente. Deduzione naturale e risoluzione, come il metodo delle tavole di verità, funzionano sempre. Tuttavia possono essere più o meno convenienti, a seconda del tipo di formula che hai.
Se ad esempio la tua formula è una congiunzione di disgiunzioni, allora puoi usare la risoluzione, perché la deduzione naturale è inefficiente.
Se invece la tua formula ha una struttura non facilmente riconducibile ad una congiunzione di disgiunzioni, e magari ha molte implicazioni e congiunzioni o è matematicamente intuitiva, puoi usare la deduzione naturale.
Il metodo delle tavole di verità è invece impraticabile quando ci sono molti letterali.
Allora, prima di tutto grazie. Sto cominciando a mettere qualche tassello al posto giusto!
E scusatemi se faccio domande sceme, mi sento una capra!
Prima di tutto. Si, sto parlando del Linguaggio Proposizionale!
Fino al punto delle tavole di verita'...ci sono arrivata e ho anche fatto qualche esercizio. Quindi ho fissato bene.
In poche parole capisco quando una frase e' una tautologia o soddisfacibile o insoddisfacibile.
Il problema e' quando "non posso" usare la tabella di verita'. O perche' l'esercizio mi dice chiaramente di non farlo o perche',appunto, ci sono troppi letterali.
Quindi "ripiego" sulla deduzione naturale o risoluzione per clausole. Valuto quale delle due mi converrebbe fare. E eseguo i vari passaggi.
Il punto e'...una volta che arrivo alla fine...come faccio a dire che ricado in uno di quei casi?
Per esempio...nel caso trovassi clausola vuota? tautologia?
Se per caso, voi che ne sapete sicuramente piu' di me, vi accorgete che mi manca qualcosa (quasi sicuro) dal punto di vista teorico...mi indichereste cosa? :'
grazie grazie!
E scusatemi se faccio domande sceme, mi sento una capra!
Prima di tutto. Si, sto parlando del Linguaggio Proposizionale!
Fino al punto delle tavole di verita'...ci sono arrivata e ho anche fatto qualche esercizio. Quindi ho fissato bene.
In poche parole capisco quando una frase e' una tautologia o soddisfacibile o insoddisfacibile.
Il problema e' quando "non posso" usare la tabella di verita'. O perche' l'esercizio mi dice chiaramente di non farlo o perche',appunto, ci sono troppi letterali.
Quindi "ripiego" sulla deduzione naturale o risoluzione per clausole. Valuto quale delle due mi converrebbe fare. E eseguo i vari passaggi.
Il punto e'...una volta che arrivo alla fine...come faccio a dire che ricado in uno di quei casi?
Per esempio...nel caso trovassi clausola vuota? tautologia?
Se per caso, voi che ne sapete sicuramente piu' di me, vi accorgete che mi manca qualcosa (quasi sicuro) dal punto di vista teorico...mi indichereste cosa? :'
grazie grazie!
prego. ... e benvenuta nel forum...
a partire dalla logica di base, sei passata alle principali regole di deduzione: modus ponens, modus tollens, sillogismo disgiuntivo, ... ?
cercando in internet, ho trovato questo file, non so se è di buon livello ma ho l'impressione che possa esserti utile: ti lascio il link
http://www.ing.unife.it/elettr/Intellig ... Logica.pdf
ciao.
a partire dalla logica di base, sei passata alle principali regole di deduzione: modus ponens, modus tollens, sillogismo disgiuntivo, ... ?
cercando in internet, ho trovato questo file, non so se è di buon livello ma ho l'impressione che possa esserti utile: ti lascio il link
http://www.ing.unife.it/elettr/Intellig ... Logica.pdf
ciao.
"acrobata":
Il punto e'...una volta che arrivo alla fine...come faccio a dire che ricado in uno di quei casi?
Per esempio...nel caso trovassi clausola vuota? tautologia?
Un insieme di clausole è non soddisfacibile se e solo se da esso è derivabile la clausola vuota tramite risoluzione.
Inoltre, se A è una formula, A è una tautologia se e solo se esiste una deduzione naturale di A senza premesse.
In altri termini, con la risoluzione cerchi di dimostrare che la tua formula è non soddisfacibile, mentre con la deduzione naturale cerchi di dimostrare che è una tautologia
"adaBTTLS":
prego. ... e benvenuta nel forum...
a partire dalla logica di base, sei passata alle principali regole di deduzione: modus ponens, modus tollens, sillogismo disgiuntivo, ... ?
Si, si...diciamo che quella parte di "esercizio" una volta che si applicano le regole e fatto l'occhio. Si fa in modo quasi meccanico.
Grazie per il link, adesso me lo guardo per bene!
e grazie per il benvenuta!"fields":
In altri termini, con la risoluzione cerchi di dimostrare che la tua formula è non soddisfacibile, mentre con la deduzione naturale cerchi di dimostrare che è una tautologia
Questo era un tassello importante che mi mancava!
Penso che ora l'unica cosa da fare e' dare un'ulteriore guardata alla teoria e buttarsi nella pratica!
Grazie :_)
E rieccomi qua! Oramai mi vengono dubbi anche sulla mia identita'!
Qualcuno ha la pazienza di vedere se il ragionamento che sto facendo e' corretto?
Siate cattivi!
Qualcuno ha la pazienza di vedere se il ragionamento che sto facendo e' corretto?
Siate cattivi!
"acrobata":
Qualcuno ha la pazienza di vedere se il ragionamento che sto facendo e' corretto?
Ok. Naturalmente, come ultimo passaggio (non lo hai scritto) devi applicare l'eliminazione dell'or, per ottenere $B\vee D$ da $A\vee C$
Ah si! Me lo sono dimenticata...!
E quindi dovrei dedurre che e' soddisfacibile (in teoria)..?
E quindi dovrei dedurre che e' soddisfacibile (in teoria)..?
"acrobata":
E quindi dovrei dedurre che e' soddisfacibile (in teoria)..?
...dunque la tua formula è una tautologia, poiché l'hai dimostrata senza premesse non scaricate.
Ok, si!
Se prendessi un minimo di dimestichezza e sicurezza potrei mettere online alcuni degli esercizi che sto svolgendo.
Magari fanno comodo a qualcuno...
Se prendessi un minimo di dimestichezza e sicurezza potrei mettere online alcuni degli esercizi che sto svolgendo.
Magari fanno comodo a qualcuno...
Cambiando il linguaggio a disposizione e passando a quelli del primo ordine...
Mi sono imbattuta in un esercizio del genere:
∀x(A(x) ∨ B(x)) |= ∃x¬A(x) → ∃xB(x)
e devo dire se vale la conseguenza logica.
Qualcuno me lo spiega? Perche' io ho fatto una cosa... Ma sinceramente penso di essere MOLTO lontana da uno svolgimento semi giusto.
Mi sono imbattuta in un esercizio del genere:
∀x(A(x) ∨ B(x)) |= ∃x¬A(x) → ∃xB(x)
e devo dire se vale la conseguenza logica.
Qualcuno me lo spiega? Perche' io ho fatto una cosa... Ma sinceramente penso di essere MOLTO lontana da uno svolgimento semi giusto.
se ho interpretato bene la frase, l'ultimo operatore esistenziale può non esserci (io non ce lo metterei, però se è solo una conseguenza logica può esserci).
ti dico come l'ho interpretata io, poi ti regoli:
se
per ogni x vale almeno una delle due A(x) o B(x)
allora
se esiste x tale che A(x) non vale, allora deve valere B(x) [come dice il testo per almeno un x, ma usa lo stesso parametro?]
N.B. come l'avrei scritta io senza "esiste", B(x) deve valere per lo stesso x, in maniera generica è garantito che B deve valere per almeno un x
non so se è più chiaro. ciao.
ti dico come l'ho interpretata io, poi ti regoli:
se
per ogni x vale almeno una delle due A(x) o B(x)
allora
se esiste x tale che A(x) non vale, allora deve valere B(x) [come dice il testo per almeno un x, ma usa lo stesso parametro?]
N.B. come l'avrei scritta io senza "esiste", B(x) deve valere per lo stesso x, in maniera generica è garantito che B deve valere per almeno un x
non so se è più chiaro. ciao.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo