Formule proposizionali

Zeldic
Salve. Non riesco a svolgere il seguente esercizio :

"Senza usare le tavole di verità, ma solo le regole della logica, provare che le due formule proposizionali $ not (p vv not q) vv not (q -> not r) vv p $ e $ r ^^ (p vv q) $ sono logicamente equivalenti."

Ho cominciato scrivendo :

$ not((p vv not q) ^^ (q -> not r)) vv p hArr r ^^ (p vv q) $

$ (p vv not q) ^^ (q -> not r) -> p hArr r ^^ (p vv q) $

.. e poi non saprei procedere.. Che regola dovrei utilizzare ? :( Qualche aiutino ?

Risposte
Doakes
Eh, io invece le ho usate le tavole di verità e così facendo ho scoperto che le due forumule non sono logicamente equivalenti.. :)

perplesso1
$ not (p vv not q) vv not (q -> not r) vv p $
$ (not p ^^ q) vv not (q -> not r) vv p $ (De Morgan)
$ (not p ^^ q) vv not (not q vv not r) vv p $ (elimino $ -> $ )
$ (not p ^^ q) vv ( q ^^ r) vv p $ (ancora De Morgan)
$ (not p ^^ q) vv p vv ( q ^^ r) $ (proprietà commutativa)
$ ((not p vv p) ^^ (q vv p)) vv ( q ^^ r) $ (proprietà distributiva)
$ (1 ^^ (q vv p)) vv ( q ^^ r) $ (terzo escluso)
$ (q vv p) vv ( q ^^ r) $
$ p vv (q vv ( q ^^ r)) $ (proprietà commutativa e associativa di $ vv $)
$ p vv q $ (legge di assorbimento)

Spero di non aver sbagliato nulla, cmq sono daccordo con Doakes.

xunil1987
Non ho controllato i calcoli di perplesso ma sono sicuro che non li ha sbagliati :D

Ad ogni modo, un metodo per la verifica di una formula senza l'uso delle tavole di verità è quello dei tableaux che sono trattati, per esempio, in http://cialdea.dia.uniroma3.it/teaching/pf/logica.pdf*

Chiaramente, verificare l'equivalenza logica di due formule $\alpha$ e $\beta$ significa verificare che la formula $\alpha \leftrightarrow \beta$ è una tautologia.

-------
*non ho avuto il tempo di controllare le dispense, ho dato solo uno sguardo veloce alla parte sui tableaux e mi sembrano spiegati abbastanza bene.

perplesso1
"xunil1987":
Non ho controllato i calcoli di perplesso ma sono sicuro che non li ha sbagliati

Grazie per la fiducia. :-D

"xunil1987":
un metodo per la verifica di una formula senza l'uso delle tavole di verità è quello dei tableaux

Belli belli non li conoscevo, anche se mi sembrano un pò scomodi. Ci voglio provare :-D Allora per far vedere che quelle due formule non sono equivalenti dobbiamo mostrare che è soddisfacibile $not (A \leftrightarrow B)$ che equivale a $not (A -> B) vv not (B -> A)$ quindi ci basta provare che si può soddisfare $not (A -> B)$ e siamo a posto.



Ho scritto molte fesserie ??

Zeldic
"perplesso":


$ not (p vv not q) vv not (q -> not r) vv p $
$ (not p ^^ q) vv not (q -> not r) vv p $ (De Morgan)
$ (not p ^^ q) vv not (not q vv not r) vv p $ (elimino $ -> $ )
$ (not p ^^ q) vv ( q ^^ r) vv p $ (ancora De Morgan)
$ (not p ^^ q) vv p vv ( q ^^ r) $ (proprietà commutativa)
$ ((not p vv p) ^^ (q vv p)) vv ( q ^^ r) $ (proprietà distributiva)
$ (1 ^^ (q vv p)) vv ( q ^^ r) $ (terzo escluso)
$ (q vv p) vv ( q ^^ r) $
$ p vv (q vv ( q ^^ r)) $ (proprietà commutativa e associativa di $ vv $)
$ p vv q $ (legge di assorbimento)

Spero di non aver sbagliato nulla, cmq sono daccordo con Doakes.




Scusate se rispondo un po' in ritardo, ma non riuscivo e tuttora non riesco a comprendere tutti i vostri passaggi. Grazie innanzitutto delle risposte.. Perplesso, ad esempio, non ho ancora capito che cosa hai voluto dimostrare sino all'ultimo passaggio con $ p vv q $ , che è vera ? E dove dimostri l'equivalenza delle 2 formule proposizionali ?

"xunil1987":


Chiaramente, verificare l'equivalenza logica di due formule α e β significa verificare che la formula α↔β è una tautologia.




In base all'affermazione di xunil1987, quindi, ho provato semplicemente ad attribuire a ciascuna singola proposizione un valore V o F, affinché le 2 formule proposizionali risultino entrambe vere, perché rappresentano una tautologia, ma non saprei se è giusto fare così o se sia un metodo troppo naїv. Così sono riuscito facilmente a dimostrare che entrambe le formule proposizionali sono vere, a partire dalla seconda $ r ^^ (p vv q) $ : sapendo che una congiunzione è vera soltanto se entrambe le espressioni sono vere, ho imposto subito $ r $ V e $ p vv q $ V ; quindi la disgiunzione è V quando una delle due proposizioni $ p $ o $ q $ è V.. Ed ho proceduto in questa maniera, però non so, a me sembrerebbe troppo banale.. :-k
Non abbiamo mai usato le tavole di tableaux, non credo che la prof voglia che si facciano così, però grazie comunque, non si sa mai dovesse cambiar idea, vi ho trovato anche molte tautologie importanti che mi possono essere utili.

perplesso1
"Zeldic":
non ho ancora capito che cosa hai voluto dimostrare sino all'ultimo passaggio con p∨q , che è vera ?


Le formule che ho scritto sono tutte quante equivalenti. Con quei passaggi ho dimostrato che $not (p vv not q) vv not (q -> not r) vv p$ è equivalente a $p vv q$ e quindi non può essere equivalente a $r ^^ (p vv q)$

"Zeldic":
E dove dimostri l'equivalenza delle 2 formule proposizionali ?

Di fianco a ogni passaggio ho scritto la proprietà o la legge che mi permette di operare quella trasformazione nella formula precedente. Per esempio nell'ultimo passaggio la legge di assorbimento mi permette di dire che $(q vv (q ^^ r))$ equivale a $q$.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.