Domanda dimostrazione teorema P=>Q V R
Salve, è il mio primo messaggio e vorrei aprire la mia presenza sul forum con una domanda piuttosto semplice ma su cui mi sono incastrato sul "come dimostrare" un asserto. Sto leggendo le prime pagine del mio libro di analisi in cui si introduce la logica e ho un dubbio amletico.
Vorrei ad esempio capire una cosa in generale, se io devo dimostrare un $P=>Q or R$ se riesco a dimostrare con vari passi logici che: partendo da P ipotesi giungo a dimostrare che Q è sempre vera, allora il teorema è corretto.
Però in teoria R potrebbe anche sempre essere falsa giusto? Cioè in altre parole voglio dire, il fatto che io ho dimostrato in buona sostanza che: $P=>Q$ ciò rende $P=>Q or R$ dimostrato essendo un "or", però in realtà non assicuro che R si presenti partendo da una P (ipotesi), per quanto ne so R potrebbe non verificarsi mai pur avendo P, giusto? Un ringraziamento a tutti.
Il motivo del dubbio è che questo mi sembra cozzare con il fatto che dimostrare $P=>Q or R$ equivale a dimostrare $P=>(\notQ => R)$ e questo sembra suggerire che R debba essere anche esso vero, poiché negando Q devo ottenere R. ma dimostrare le due cose è uguale quindi qualcosa non mi torna.
Qualcuno potrebbe darmi una manina
? Grazie.
Vorrei ad esempio capire una cosa in generale, se io devo dimostrare un $P=>Q or R$ se riesco a dimostrare con vari passi logici che: partendo da P ipotesi giungo a dimostrare che Q è sempre vera, allora il teorema è corretto.
Però in teoria R potrebbe anche sempre essere falsa giusto? Cioè in altre parole voglio dire, il fatto che io ho dimostrato in buona sostanza che: $P=>Q$ ciò rende $P=>Q or R$ dimostrato essendo un "or", però in realtà non assicuro che R si presenti partendo da una P (ipotesi), per quanto ne so R potrebbe non verificarsi mai pur avendo P, giusto? Un ringraziamento a tutti.
Il motivo del dubbio è che questo mi sembra cozzare con il fatto che dimostrare $P=>Q or R$ equivale a dimostrare $P=>(\notQ => R)$ e questo sembra suggerire che R debba essere anche esso vero, poiché negando Q devo ottenere R. ma dimostrare le due cose è uguale quindi qualcosa non mi torna.
Qualcuno potrebbe darmi una manina
? Grazie.
Risposte
Abbastanza evidente è che $(P => Q) => (P => Q vv R)$ è una tautologia indipendentemente dalla verità di $R$ (basta farsi un po' di tavole di verità), il che formalizza quello che dici in apertura del post:
Il punto di molti teoremi del tipo $P => Q vv R$ è proprio che l'implicazione $P => Q$ non è sempre vera (il che accade perché, pur essendo vera l'ipotesi $P$, ciò non basta a garantire la verità della tesi $Q$); ma quando $P$ fallisce nell'implicare $Q$, allora essa implica un'altra alternativa $R$ (la cui verità può o meno dipendere dalla verità di $Q$[nota]Nel senso che $R$ può essere vera sia solo quando $Q$ è falsa, sia anche quando $Q$ è vera... Chiaramente, in quest'ultimo caso, il teorema potrebbe essere semplificato scrivendo semplicemente $P => R$.[/nota]).
Se la vedi da un punto di vista insiemistico, piuttosto che puramente logico, la cosa torna.
Infatti, se chiami $mathcal(P)$, $mathcal(Q)$ e $mathcal(R)$ gli insiemi di oggetti individuati da $P$, $Q$ ed $R$ rispettivamente, affermare che $P => (Q vv R)$ equivale ad affermare che $mathcal(P) sube mathcal(Q) uu mathcal(R)$; mentre $P => (not Q => R)$ equivale ad asserire che gli elementi di $mathcal(P)$ (appartenenti all'universo $mathcal(Q) uu overline(mathcal(Q))$) che stanno in $overline(mathcal(Q))$ stanno necessariamente in $mathcal(R)$, sicché $mathcal(P) sube mathcal(Q) uu mathcal(R)$.
"Altismo":
Vorrei ad esempio capire una cosa in generale, se io devo dimostrare un $ P=>Q or R $ se riesco a dimostrare con vari passi logici che: partendo da P ipotesi giungo a dimostrare che Q è sempre vera, allora il teorema è corretto.
Però in teoria R potrebbe anche sempre essere falsa giusto? Cioè in altre parole voglio dire, il fatto che io ho dimostrato in buona sostanza che: $ P=>Q $ ciò rende $ P=>Q or R $ dimostrato essendo un "or", però in realtà non assicuro che R si presenti partendo da una P (ipotesi), per quanto ne so R potrebbe non verificarsi mai pur avendo P, giusto? Un ringraziamento a tutti.
Il punto di molti teoremi del tipo $P => Q vv R$ è proprio che l'implicazione $P => Q$ non è sempre vera (il che accade perché, pur essendo vera l'ipotesi $P$, ciò non basta a garantire la verità della tesi $Q$); ma quando $P$ fallisce nell'implicare $Q$, allora essa implica un'altra alternativa $R$ (la cui verità può o meno dipendere dalla verità di $Q$[nota]Nel senso che $R$ può essere vera sia solo quando $Q$ è falsa, sia anche quando $Q$ è vera... Chiaramente, in quest'ultimo caso, il teorema potrebbe essere semplificato scrivendo semplicemente $P => R$.[/nota]).
"Altismo":
Il motivo del dubbio è che questo mi sembra cozzare con il fatto che dimostrare $P=>Q or R$ equivale a dimostrare $P=>(\notQ => R)$ e questo sembra suggerire che R debba essere anche esso vero, poiché negando Q devo ottenere R. ma dimostrare le due cose è uguale quindi qualcosa non mi torna.
Se la vedi da un punto di vista insiemistico, piuttosto che puramente logico, la cosa torna.
Infatti, se chiami $mathcal(P)$, $mathcal(Q)$ e $mathcal(R)$ gli insiemi di oggetti individuati da $P$, $Q$ ed $R$ rispettivamente, affermare che $P => (Q vv R)$ equivale ad affermare che $mathcal(P) sube mathcal(Q) uu mathcal(R)$; mentre $P => (not Q => R)$ equivale ad asserire che gli elementi di $mathcal(P)$ (appartenenti all'universo $mathcal(Q) uu overline(mathcal(Q))$) che stanno in $overline(mathcal(Q))$ stanno necessariamente in $mathcal(R)$, sicché $mathcal(P) sube mathcal(Q) uu mathcal(R)$.
Ciao @gugo82, vorrei ringraziarti per il tuo aiuto.
Ho capito il senso delle dimostrazioni con or e l'interpretazione insiemistica non l'avevo proprio pensata, molto interessante.
Ovviamente come dici tu $(P⇒Q)⇒(P⇒Q∨R)$ indipendentemente da R, però mi chiedo una cosa, se volessi appunto fare una cosa strampalata e voler dimostrare un "teoremino" P=>Q v R con R sempre falsa, in teoria è sciocco ma fattibile e facciamolo solo per esercizio ora e per capire.
Adesso, come dicevo data la sovrapponibilità delle tavole logiche $P=>Q or R$ (**) coincide evidentemente a dover dimostrare $P⇒(¬Q⇒R)$: per ogni P, Q R per cui vale la prima vale la seconda.
Ebbene, ora pero viene il brutto, se R è sempre falsa e Q sempre vera, mi pare che $P⇒(¬Q⇒R)$ non sia fattibile, ma logicamente deve esserlo invece.
Mi verrebbe da dire che essendo $Q$ sempre vera in effetti $not Q$ sarà sempre falsa e dal falso qualsiasi cosa ne consegue, quindi ¬Q⇒R è sempre vera? Il che funzionerebbe e mi farebbe ottenere la tatuologica che ottenevo con (**). Però non riesco a immaginare come dimostrarlo in tal modo, perché dovrei dimostrare ¬Q sempre falsa e mi sembra assai difficile farlo.
Ma secondo te sto dicendo cavolate o è corretto? Spero avrai ancora voglia di aiutarmi per giungere a corretta interpretazione della cosa e... grazie mille
Ho capito il senso delle dimostrazioni con or e l'interpretazione insiemistica non l'avevo proprio pensata, molto interessante.
Ovviamente come dici tu $(P⇒Q)⇒(P⇒Q∨R)$ indipendentemente da R, però mi chiedo una cosa, se volessi appunto fare una cosa strampalata e voler dimostrare un "teoremino" P=>Q v R con R sempre falsa, in teoria è sciocco ma fattibile e facciamolo solo per esercizio ora e per capire.
Adesso, come dicevo data la sovrapponibilità delle tavole logiche $P=>Q or R$ (**) coincide evidentemente a dover dimostrare $P⇒(¬Q⇒R)$: per ogni P, Q R per cui vale la prima vale la seconda.
Ebbene, ora pero viene il brutto, se R è sempre falsa e Q sempre vera, mi pare che $P⇒(¬Q⇒R)$ non sia fattibile, ma logicamente deve esserlo invece.
Mi verrebbe da dire che essendo $Q$ sempre vera in effetti $not Q$ sarà sempre falsa e dal falso qualsiasi cosa ne consegue, quindi ¬Q⇒R è sempre vera? Il che funzionerebbe e mi farebbe ottenere la tatuologica che ottenevo con (**). Però non riesco a immaginare come dimostrarlo in tal modo, perché dovrei dimostrare ¬Q sempre falsa e mi sembra assai difficile farlo.
Ma secondo te sto dicendo cavolate o è corretto? Spero avrai ancora voglia di aiutarmi per giungere a corretta interpretazione della cosa e... grazie mille
Abbastanza evidente è che
La parola "tautologia" andrebbe usata con cautela se si vuole fare un discorso formale: è sempre pericolosa, perché per esempio nel sistema di Hilbert (HK) una tautologia è semplicemente una formula valida ([1, Lemma 1.1] (e allora, cosa la distingue semplicemente da "ciò di cui voglio parlare"?); per questo, è invalso il costume di chiamare "tautologia" semplicemente una formula "sempre valida".
Questo abuso di notazione però confonde le cose, specie a una mente giovane, perché confonde dimostrabilità (che è una nozione di raggiungibilità sintattica) e validità (che è una nozione semantica). La confusione è poco pericolosa, perché ad esempio in HK una formula è valida se e solo se è dimostrabile. Diventa pericolosa quando uno fa la domanda che ha fatto OP, "cosa sta succedendo, qui, davvero?".
Già sistemi deduttivi un po' più raffinati di HK (l'LK di Gentzen basta) introducono una nozione di validità più generale, mediante una semantica funtoriale: dato un sistema deduttivo (per esempio LK) se ne interpretano i connettivi di base come operazioni in un'algebra di Heyting $H$, mediante un omomorfismo dall'insieme \( {\bf LK}_0\) delle variabili proposizionali di LK verso $H$. Una formula \(\varphi \in \mathbf{LK}\) allora è "valida" se la sua interpretazione è uguale a \(\top\in H\) per ogni \(h : {\bf LK}_0 \to H\).
A queso punto vale questo teorema, detto "completezza algebrica" del calcolo proposizionale classico [1, Teorema 6.6]: per ogni formula \(\varphi\) di LK, \(\varphi\) è dimostrabile in logica classica se e solo se è valida in ogni $H$, se e solo se è valida in \(H=\{0 < 1\}\).
E' solo a questo punto e solo in questo senso che si può confondere validità con dimostrabilità. Questo teorema tuttavia non elimina la sottigliezza di cui prima (che la dimostrabilità è una nozione sintattica, mentre la validità una nozione semantica; in effetti il teorema di completezza è il motivo che permette di affermare che "Se la vedi da un punto di vista insiemistico, piuttosto che puramente logico, la cosa torna": stai affermando che è sufficiente considerare un'interpretazione del linguaggio in un'algebra di Boole atomica, che realizza congiunzioni disgiunzioni implicazioni e costanti come operazioni insiemistiche. Ma da un lato, le formule di per sé stesse non hanno significato, gli hai attribuito questa interpretazione. Dall'altro, non è affatto ovvio che ciò sia possibile).
Venendo al problema in esame, e alla luce di quel che ho detto, il fatto che \(p \to q \vdash p\to q \lor r\) sia una "tautologia" significa semplicemente che esiste una derivazione (in LK, giusto perché ne ho parlato finora) che la dimostra: questa derivazione è la seguente
\[\frac{
\displaystyle\frac{
\displaystyle\frac{}{p \vdash p} \qquad \frac{\displaystyle\frac{}{q \vdash q}}{q \vdash q\lor r}
}{p, p\to q \vdash p\to q\lor r}
}{p \vdash (p\to q) \to (p\to q\lor r)}\] Non eccessivamente difficile... ma nemmeno una "tautologia" nel senso informale del termine!
Due osservazioni che questo argomento genera quasi automaticamente:
1. Lo stile di dimostrazione in calcolo dei sequenti svela ciò che effettivamente volevi dire quando scrivevi che : assumendo $p$, per ogni $q,r$, il giudizio \(p\vdash (p\to q)\to(p\to q\lor r)\) è derivabile.
2. Tu scrivi "\((p\to q) \mathrel{\color{red}\to} p \to q\lor r\)", confondendo l'implicazione in blu (che è un connettivo logico) con quella in rosso, che formalmente è un entailment: \(\vdash\) sta nel metalinguaggio, è solo un simbolo che serve a separare antecedente da successore in un sequente \((\Gamma, \Delta)\), e semmai ha significato in una semantica (ma ha significati diversi in semantiche diverse, perché date diverse logiche substrutturali, sono diverse le scelte di semantica che si fanno --un esempio è la logica lineare alla Girard: non ha interpretazioni classiche ma ne ha -ad esempio- in termini di certi reticoli di sottospazi vettoriali... è una storia lunga).
In estrema sintesi il calcolo dei sequenti serve proprio a notare problemi analoghi a questi due, e purtroppo quello che succede nella didattica è questo: si inizia a studiare le cose aumm aumm e non c'è mai tempo per seguire un corso di logica (o ancor piu importante sarebbe avere almeno una base di teoria della dimostrazione), e i pochi che lo fanno finiscono per togliere tempo a cose altrettanto importanti, quindi si crea una frattura: studenti che sanno la fisica matematica, ma a cui non sono chiari dei fatti di logica elementare (dimostrabilità, validità, la nozione di modello di una teoria, il teorema di compattezza, cos'è una "tautologia" in un calcolo dei sequenti), e gente a cui queste ultime cose sono chiare, ma che non sanno "dove usarle" perché non hanno fatto altra matematica.
Poi arriva una povera anima in pena, confusa dal modo effettivamente insapore con cui questi argomenti sono presentati come "ovvi" e "immediati" (senza dar credito allo sforzo intellettuale che ci è voluto per formalizzarli davvero), e succede un casino, per ovvi -stavolta per davvero- motivi (perché dimostrare veramente delle cose ritenute "ovvie" può essere a volte un po' complicato).
"megas_archon":
Tu scrivi...
Caro, grazie per l'esegesi non richiesta. Fortunatamente, so quel che scrivo e perché lo scrivo; e se confondo i livelli è solo per comodità di lettura del lettore alle prime armi, non per ignoranza.
Grazie per aver approfondito la parte formale della deduzione: ogni tanto serve un po' di pedanteria.
Mi spiace aver generato codesta diatriba per una domanda banalotta non volevo.
Ad ogni modo, anche su un semplice piano, qualcuno potrebbe aiutarmi riguardo l'ultima domanda?
Grazie ancora:
Ad ogni modo, anche su un semplice piano, qualcuno potrebbe aiutarmi riguardo l'ultima domanda?
Grazie ancora:
"Altismo":
Ciao @gugo82, vorrei ringraziarti per il tuo aiuto.
Ho capito il senso delle dimostrazioni con or e l'interpretazione insiemistica non l'avevo proprio pensata, molto interessante.
Ovviamente come dici tu $(P⇒Q)⇒(P⇒Q∨R)$ indipendentemente da R, però mi chiedo una cosa, se volessi appunto fare una cosa strampalata e voler dimostrare un "teoremino" P=>Q v R con R sempre falsa, in teoria è sciocco ma fattibile e facciamolo solo per esercizio ora e per capire.
Adesso, come dicevo data la sovrapponibilità delle tavole logiche $P=>Q or R$ (**) coincide evidentemente a dover dimostrare $P⇒(¬Q⇒R)$: per ogni P, Q R per cui vale la prima vale la seconda.
Ebbene, ora pero viene il brutto, se R è sempre falsa e Q sempre vera, mi pare che $P⇒(¬Q⇒R)$ non sia fattibile, ma logicamente deve esserlo invece.
Mi verrebbe da dire che essendo $Q$ sempre vera in effetti $not Q$ sarà sempre falsa e dal falso qualsiasi cosa ne consegue, quindi ¬Q⇒R è sempre vera? Il che funzionerebbe e mi farebbe ottenere la tatuologica che ottenevo con (**). Però non riesco a immaginare come dimostrarlo in tal modo, perché dovrei dimostrare ¬Q sempre falsa e mi sembra assai difficile farlo.
Ma secondo te sto dicendo cavolate o è corretto? Spero avrai ancora voglia di aiutarmi per giungere a corretta interpretazione della cosa e... grazie mille
La derivazione che ho scritto si può ottenere anche da
\[p \to (q\to r)\vdash (p\to q)\to (p\to r)\] C'è modo di includere proof.sty e disegnare quel tipo di diagrammi in un messaggio? Farlo con le frazioni è una pena...
Il libro di Ono leggilo, se non lo conoscevi, è molto breve e contiene tutto (molto più di quello di cui ho parlato).
\[p \to (q\to r)\vdash (p\to q)\to (p\to r)\] C'è modo di includere proof.sty e disegnare quel tipo di diagrammi in un messaggio? Farlo con le frazioni è una pena...
Il libro di Ono leggilo, se non lo conoscevi, è molto breve e contiene tutto (molto più di quello di cui ho parlato).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo