Un'ultima domanda sulle dimostrazioni

[serafinon]

Ero convinto di aver postato pomeriggio, ma solo ora vedendo la notifica dell'intervento di un altro utente nel topic noto che non è rimasta, provvedo quindi a riscriverla brevemente.

Solo per tirare le somme, dato che ora mi sembra di esserci abbastanza.

1) Ok ho capito la tua scrittura e mi torna, quindi giusto per raicapitolare quando ho qualcosa tipo:
$$P =>$ ($forall x$ ($Q(x) => R(x)$))$ lo rendo con quella "generalizzazione" della I-E come: $AAx,[(P and Q(x))=> R(x)]$. Col caveat di dare i giusti "nomi" alle variabili mute (cosa che non avevo fatto).
Qui ora mi pare che ci siamo no?

Dato che qui non mi hai più bacchettato lo prendo come un eureka finalmente ho capito!

Quindi per rispondere alla tua domanda (D), in realtà non è vero che prendiamo un x che soddisfa P(x), prendiamo un x qualsiasi e poi dividiamo la dimostrazione in due casi, quello in cui P(x) è falsa e quello in cui P(x) è vera. Poi però ci accorgiamo che nel primo di questi due casi non c'è nulla da dimostrare, quindi passiamo direttamente al secondo caso.

Anche qui mi pare di esserci, prendo ancora in esame la nostra dimostrazione.
Quello che in effetti faccio è di prendere ogni x, [e ogni y (associato a quell'x) e valuto ϕ(x,y)].
Qui abbiamo i due casi che elenchi:
1) se non rispettano ϕ(x,y)=0 antecedente falso, conseguente vero (siamo a cavallo) perché l'implicazione è vera istantaneamente.
2) se rispettano ϕ(x,y)=0 e dimostro che (implica) x=0
se si verificano tali due punti ho dimostrato il teorema.

E' proprio in virtù del fatto che 1) posso darla per buona in automatico che dico: "assumo un x tale che ϕ(x,y)=0 per ogni y ecc ecc", cioè dei vari x che rendono e non rendono vera ϕ(x,y)=0 mi interessa valutare quelli che la rendono vera (unici degni di nota).

Quindi in effetti valuto tutti gli x e y, è solo che quando ϕ(x,y)=0 è vera mi "isola" (e questa è la dimostrazione) gli x=0

Spero di non aver detto troppe ca____ come mio solito, ma in testa ora mi sembra filare liscio.
Un mega-grazie Martino per la tua disponibilità e aiuto.

[Martino]

Dato che qui non mi hai più bacchettato lo prendo come un eureka finalmente ho capito!

Sì esatto, anche per il resto mi sembra OK

come dovrei gestire la riformulazione del teorema (che apprendo dal vostro scambio) in $AAx, ((P(x) and ¬Q(x))=>R(x))$, sempre sotto l'idea di R sempre falsa? Non riesco cioè a vedere, quando riscritta in tal modo, che sto dimostrando la solita $AAx, (P(x)=>(Q(x))$.

Beh semplicemente perché se $R(x)$ è sempre falsa allora $(P(x) and ¬Q(x))=>R(x)$ è equivalente a $¬ (P(x) and ¬Q(x))$ (per vederlo basta fare una tabella di verità).

In altre parole, se $B$ è falsa, allora $A=>B$ è equivalente a $¬A$.

E la mia domanda è, ma se io nel processo dimostrativo di solito dimostro che appunto se A vera allora B è vera, non dovrei far sparire la seconda riga? Infatti, quella non esiste più, perché so che se vera A per forza di cose B è vera. Il teorema quindi è una tavola di verità dell'implicazione in cui "elimino" la secodna riga grazie ai processi dimostrativi?
In altre parole: la seconda riga mi è possibile "levarla" proprio per via degli assiomi che agiscono sul mio universo delle x?

Qui stai andando un po' sul filosofico, in che senso levare la seconda riga? Ci sono 3 casi in cui l'implicazione è vera e un caso in cui è falsa (tre V e un F), e quello che fai è mostrare che il caso F non succede, ma non è che "levi" la seconda riga (cosa significa levare una riga?). La tabella di verità di una proposizione composta è una tabella che ti dà il valore di verità della proposizione in funzione del valore di verità delle sue parti. Siccome l'unico caso in cui $A => B$ è falsa è quando $A$ è vera e $B$ è falsa, quello che devi fare è dimostrare che questo non può accadere, cioè non succede mai che $A$ è vera e $B$ è falsa. Per fare questo, assumi $A$ vera e ne deduci (tramite passaggi logici) che $B$ è vera.

[matos]

Grazie mille, sono contentissimo di leggere una tua risposta

Beh semplicemente perché se $R(x)$ è sempre falsa allora $(P(x) and ¬Q(x))=>R(x)$ è equivalente a $¬ (P(x) and ¬Q(x))$ (per vederlo basta fare una tabella di verità).

In altre parole, se $B$ è falsa, allora $A=>B$ è equivalente a $¬A$.

Uhhhh
Perfetto, grazie mille! Cercavo proprio di capire questo.

Qui stai andando un po' sul filosofico, in che senso levare la seconda riga? Ci sono 3 casi in cui...

Faccio un esempietto per rendere più concreto il dilemma, che forse parlando per massimi sistemi non si capisce bene.

Il dubbio sorge perché solitamente si dice che un teorema, risolto con le tavole di verità, dovrebbe portare a una tautologia in ultima colonna (della tavola).

(metto in poiler per non creare una paginata di post)

Testo nascosto, fai click qui per vederlo

[Prendo in realtà in prestito da un dubbio altrui, ma che spiega bene il mio dubbio]
Vorrei ora dimostrare che una relazione simmetrica e antisimmetrica è una uguaglianza dati a e b in relazione R tra loro.
La dimostrazione segue la via:
aRb (ma essendo simmetrica) => aRb e bRa (ed essendo antisimmetrica) => a=b

Provo ad esplicitare il mio dubbio, siccome l'implicazione in logica ha una tavola di verità pensavo di risolvermela così: prendendo la tavola di verità notiamo che

aRb bRa aRb =>bRa


V-----V------V

V-----F------F

F-----V------V

F-----F------V


Poiché l'implicazione aRb =>bRa è sempre vera (dall'hp di R simmetrica) abbiamo che la seconda riga non vale mai, quindi ci riduciamo ai casi


aRb bRa

V-----V

F-----V

F-----F


Se studiamo aRb e bRa con i tre casi sopra garantiti dalla prima implicazione avremo


aRb e bRa

V

F

F


Infine


(aRb e bR a=> a=b)

V

V

V

Sempre vera poiché antisimmetrica, ho pensato.

In questo (maldestro) senso intendevo con eliminare una riga; perché sennò, mantenendo quella seconda riga, non riesco a ottenere la tautologia voluta. E non saperi come vederla in altro modo.
D'altra parte l'idea sovveniva perché come dici "assumi A vera e ne deduci (tramite passaggi logici) che B è vera", quindi proprio perché quella (con A vera e B falsa) riga ho dimostrato non capitare mai la posso "levare".

[Martino]

A mio modo di vedere il tuo procedimento non è pulitissimo. Quello che vuoi dimostrare è

[ (aRb => bRa) and ( (aRb and bRa) => a=b) ] => (aRb => a=b)

che può più semplicemente essere riformulata (rinominando opportunamente le parti) come

[ (X => Y) and ( (X and Y) => Z) ] => (X => Z)

Questa è una tautologia (dà tutti V senza eliminare niente), prova.

[matos]

Effettivamente scritta così è la tautologia cercata.

Ma a questo punto mi vengono giusto tre domande per capire meglio la situazione:

- la prima è:
dato che hai reso i predicati come P(a,b)=aRb come solo X, idem per Y=Q(a,b)=bRa e Z=R(a,b)=a=b, il che ci porta a descrivere il teorema come [ (X => Y) and ( (X and Y) => Z) ] => (X => Z).
Mi sembra di capire che qualunque teorema sia il dimostrare i legami tra i vari operatori logici piuttosto che i vari asserti, poiché a X,Y,Z potrei sostituire qualunque altro predicato non per forza "a in relazione con b", "b in relazione con a" e "a=b" rispettivamente, a patto che abbiano gli stessi legami tra loro.

Ma a questo punto se volessi rendere:
$AA x,{[(AA a,AA b, (phi(a,b)=0 => a=0 or b=0)) and (AA y,( phi(x,y)=0))] => x=0}$
svolgendo qualcosa di simile a quanto fatto da te scriverei:
$((P=> Q or R) and P)=>Q$
Con: P:=phi(a,b)=0, Q:=(a=0), R:=(b=0)
che però non mi dà una tautologia, come si ottiene in questo caso?

Se invece non posso renderla in qualcosa di simile, quando posso fare questa operazione e quando no?

[EDITO: forse questa funziona in effetti: ((P => Q or R)and S) => T è una tautologia.
WOW, come dicevo nel pre edit sopra sono allibito da questa cosa: Mi sembra di capire che qualunque teorema sia il dimostrare i legami tra i vari operatori logici piuttosto che i vari asserti, poiché a X,Y,Z potrei sostituire qualunque altro predicato non per forza "a in relazione con b", "b in relazione con a" e "a=b" rispettivamente, a patto che abbiano gli stessi legami tra loro. E non sto più a valutare i per ogni x,y,a,b. Non mi ero mai accorto della potenza di questo metodo...]

***

- la seconda cosa è:
se voglio fare la tavola di verita del teorema "se un individuo x è padre allora x maschio" (con passi logici mostro che se x padre => x maschio e non ho mai x padre (vera) e x maschio (falsa)), come scrivevo avrei redatto:
A....B....A=>B
V....V.......V
V....F.......F
F....V.......V
F....F.......V

che non è palesemente una tautologia, appurato quindi che eliminare una riga non ha senso... come si otterrebbe la voluta colonna finale tutta vera?

***
La terza per chiarire ancora:
Prendiamo in analisi un ultimo teorema tipo (invento banalmente) hp: $x=y$ => th: $x*y=x^2$
Se faccio la tavola di verità ho:
x=y....x*y=x^2....x=y=>x*y=x^2
V.............V.....................V
V.............F.....................F
F.............V.....................V
F.............F.....................V

E anche qui niente tautologia , quindi come si può ottenere?

Riuscissi a capire queste ultime tre cose sare l'uomo più felice del mondo
Ti ringrazio per avermi regalato la possibilità di approfondire questi concetti

[Martino]

Certo, la tabella di verità dell'implicazione logica è sempre la stessa, non cambia a seconda del problema. Ma quando dimostri un'implicazione logica non è che elimini la riga con F, semplicemente dimostri che quella riga non è mai verificata, cioè per mostrare che A implica B dimostri che non può accadere che A è vera e B è falsa. Ma questa dimostrazione la fai con le solite regole di deduzione. In particolare, per dedurre $x*y=x^2$ da $x=y$ quello che usi sono gli assiomi logici sull'uguaglianza e la sostituzione (vedi per esempio qui). Cioè, l'implicazione $x=y$ => $x*y=x^2$ è valida perché il simbolo $=$ significa una cosa ben precisa, le sue caratteristiche sono assiomatizzate. La tavola di verità di un'implicazione logica non la può dimostrare, sta solo dicendo come il valore di verità delle sue parti è collegato al valore di verità dell'implicazione.

Mi rendo conto però che la mia risposta possa lasciare a desiderare, d'altronde non sono un logico Se vuoi approfondire ti consiglio di rivolgerti a un logico.

[matos]

Beh guarda ti ringrazio moltissimo perché, non sarai un logico ma questa discussione è stata per me davvero molto interessante perché mi hai fatto notare cose che non avevo finora notato (anche nella parte precedente al mio intervento).

Solo per tirare le somme sulle tre domande sopra. Come dicevamo

1)Facendo il verso da quanto da te appreso

[ (aRb => bRa) and ( (aRb and bRa) => a=b) ] => (aRb => a=b)

che può più semplicemente essere riformulata (rinominando opportunamente le parti) come

[ (X => Y) and ( (X and Y) => Z) ] => (X => Z)

Il mio dubbio era rendere $AA x,{[(AA a,AA b, (phi(a,b)=0 => a=0 or b=0)) and (AA y,( phi(x,y)=0))] => x=0}$ e ottenere la tautologia (cioè la dimostrazione) usando solo le tavole.
Ebbene, sostituendo opportunamente ((P => Q or R)and S) => V è una tautologia quindi ci siamo e funziona, dimostra il teorema.

Quello che, a latere, mi interessava puntualizzare era che quando dimostravo io ho sempre sfruttato il metodo prendo per ogni x verifico l'ipotesi vera e bal bla che dievi nelle pagine precedenti, e non mi ero mai accorto che potevo invece dimostrare un teorema solo sfruttando queste tabelle. E mi ha molto colpito scoprirlo così dalla discussione, perché in effetti funziona, si ha proprio una tautologia senza passare dal ragionamento logico ma solo da una "meccanica" tabella. Non so se ho spiegato meglio quello che prima volevo dire.

2) Anche "preso x individuo, se x padre allora x maschio" posso renderlo come "teorema/tautologia" me ne sono accorto solo stanotte: infatti padre è un "maschio con figli" ossia "è maschio and ha figli".
Quindi se P="x maschio", Q="x ha figli" e (P and Q)="x maschio and x ha figli" allora: (P and Q)=>P

P.............Q..............(P and Q).........(P and Q)=>P
V.............V.....................V.....................V
V.............F.....................F......................V
F.............V.....................F......................V
F.............F.....................F......................V

Tautologia, quindi "teorema" vero.

3) A patto che i primi due punti siano ora corretti e chiedo a te per sicurezza se lo sono?

mi rimane però, per chiudere definitivamente contento la faccenda, il terzo dubbio sul hp: $x=y$ => th: $x⋅y=x^2$, devo ammettere che non capisco come ottenere la tautologia usando gli assiomi dell'uguaglianza.
O, se vogliamo, come integrare gli assiomi nella tabella così da ottenere tautologie similmente ai casi 1 e 2 da me qui scritto sopra.

Direi che capito anche il 3) potrei ritenermi più che soddisfatto ho imparato moltissimo su cose per cui non avevo mai speso molto tempo per pensarci. E mi ha affascinato.

[serafinon]

Non voglio sorpassare nessuno nella richiesta di un chiarimento e non voglio incasinare la discussione prima di una risposta alla domanda di mattos, ma la lascio qui avendo ora modo di scrivere tra una lezione e l'altra e casomai avessi tempo di rispondermi dopo l'utente sopra di me.

Volevo chiudere anche io con una ultima domanda riguardo queste ultime vostre considerazioni e sono contento siano state utili anche ad altri utenti del forum che sono intervenuti o hanno letto. Ma se capisco anche questa vi assicuro che mi dileguerò per sempre da questo thread XD.

Siccome mi hai insegnato quanto sia importante dimostrare contando sulla logica applicata al linguaggio naturale, mi piacerebbe capire come compiere la dimostrazione che hai scritto in formule:
[ (aRb => bRa) and ( (aRb and bRa) => a=b) ] => (aRb => a=b) a parole ma in modo rigorso.

Io l'ho sempre letta dimostrata come: assunto aRb poiché simmetrica ho che bRa, ora avendo dimostrato ciò ho che aRb e bRa è vera ed essendo antisimmetrica avrò che a=b (dalla definizione di antisimmetrica appunto (aRb and bRa) => a=b).

Però questo procedimento è un po' sbagliato, infatti sarebbe simile a dire dimostro prima (P=>Q) quindi Q è vera, se ora ho dimostrato che Q è vera e dimostro che data tale Q, Q=>R (cioè per Q vera ho R vera), mettendo assieme quello che ho scritto sopra sarebbe come asserire che (P=>Q)=>R che non è una "tautologia" come la chiamate. Quindi la dimostrazione "a parole" è direi sbagliata perché sarebbe [aRb=>(aRb and bRa)]=>a=b e non da tautologia, per quanto sembrasse inizialmente intuitivamente corretta. O forse sbaglio solo a riportare le parole della dimostrazione in fomule?

Dunque quel che mi chiedo è come si renda a parole correttamente la dimostrazione cercata? "aRb => a=b quando R è simmetrica e antisimmetrica"?

[Martino]

A patto che i primi due punti siano ora corretti e chiedo a te per sicurezza se lo sono?

Sì mi sembra tutto ok.

mi rimane però, per chiudere definitivamente contento la faccenda, il terzo dubbio sul hp: $x=y$ => th: $x⋅y=x^2$, devo ammettere che non capisco come ottenere la tautologia usando gli assiomi dell'uguaglianza.
O, se vogliamo, come integrare gli assiomi nella tabella così da ottenere tautologie similmente ai casi 1 e 2 da me qui scritto sopra.

Il punto è che per dimostrare che $x=y$ implica $x*y=x^2$ (dove ovviamente $x^2$ è uguale a $x*x$ per definizione) tu usi un assioma dell'uguaglianza che può essere sintetizzato come segue: variabili uguali sostituite nella stessa proposizione danno risultati uguali, o (*) "$a=b$ => $P(a)=P(b)$ per ogni proposizione $P$", che può essere chiamato assioma di sostituzione (andrebbe scritto meglio ma non riesco qui a fare un trattato di logica, per questo ti ho segnalato il link wiki sulla logica del primo ordine). Quindi l'implicazione (*) è una delle tue ipotesi (e vale ovviamente anche per proposizioni di più di una variabile). Inoltre questo non è l'unico degli assiomi che usi normalmente senza neanche accorgertene, per fare un altro esempio "$x=y$ => $y=x$" è un altro assioma (che puoi trovare ovvio ma non lo è). Insomma alla fine hai una lista di assiomi $A_1$, ..., $A_n$, che fanno parte della premessa di qualsiasi implicazione logica che vuoi dimostrare. Quindi quando scrivi che $x=y$ implica $x*y=x^2$ questo è un abuso di notazione (se vogliamo proprio essere rigorosissimi) perché l'ipotesi dell'implicazione non è solo $x=y$ ma è data dalla lista "$A_1$, ..., $A_n$, $x=y$". Quindi in questo senso sì, qualsiasi teorema è una tautologia, ma devi includere nella premessa gli assiomi che usi nel processo di deduzione logica. Vedi anche qui (regole di inferenza).

dimostro prima (P=>Q) quindi Q è vera, se ora ho dimostrato che Q è vera e dimostro che data tale Q, Q=>R (cioè per Q vera ho R vera), mettendo assieme quello che ho scritto sopra sarebbe come asserire che (P=>Q)=>R che non è una "tautologia" come la chiamate.

Non capisco bene, è ovvio che il linguaggio naturale ha dei difetti, ma il punto è che dietro al linguaggio naturale ci sono le tavole di verità e le cose sono determinate in maniera esatta. Riguardo quanto dici, la tua formulazione qui sopra non è equivalente a quello che vuoi dimostrare perché, come hai già osservato, le proposizioni

[(P => Q) and ((P and Q) => R)] => (P=>R)
(P=>Q)=>R

NON sono equivalenti. La prima è una tautologia, la seconda ovviamente non lo è. Purtroppo non ti so rispondere meglio di così, il fatto che le formulazioni qui sopra non sono equivalenti implica semplicemente che la tua riformulazione in linguaggio naturale non è corretta, oppure che non è corretta la riformulazione in formule della riformulazione in linguaggio naturale.

[serafinon]

Non capisco bene, è ovvio che il linguaggio naturale ha dei difetti, ma il punto è che dietro al linguaggio naturale ci sono le tavole di verità e le cose sono determinate in maniera esatta. Riguardo quanto dici, la tua formulazione qui sopra non è equivalente a quello che vuoi dimostrare perché, come hai già osservato, le proposizioni

[(P => Q) and ((P and Q) => R)] => (P=>R)
(P=>Q)=>R

NON sono equivalenti. La prima è una tautologia, la seconda ovviamente non lo è. Purtroppo non ti so rispondere meglio di così, il fatto che le formulazioni qui sopra non sono equivalenti implica semplicemente che la tua riformulazione in linguaggio naturale non è corretta, oppure che non è corretta la riformulazione in formule della riformulazione in linguaggio naturale.

In effetti mi scuso se sono risultato poco chiaro nella domanda.

Io l'ho sempre interpretata come: assunto aRb poiché simmetrica ho che bRa, ora avendo dimostrato ciò ho che aRb e bRa è vera ed essendo antisimmetrica avrò che a=b (dalla definizione di antisimmetrica appunto (aRb and bRa) => a=b).

che mi sembra essere: [aRb=>(aRb and bRa)]=>a=b

Senza risultare troppo arzigogolato nella domanda, capendo che questa nel quote è una resa errata "in linguaggio naturale", con il precedente post volevo semplicemente chiederti: come potrei renderla in modo corretto?