Dubbio sui quantificatori

[Martino]

Ti rispondo solo alle cose che mi suonano strane.

In generale quindi quando troverò qualcosa tipo: $((A(a,b)=>B(a,b)) and (C(a,b)=>D(a,b))=>(E(a,b)=>D(a,b))$ se viene poi riscritto così: $((A=>B)and(C=>D))=>(E=>D)$ devo immaginarlo come:
$(foralla,b,(A(a,b)=>B(a,b)) and (foralla,b(C(a,b)=>D(a,b))))=>(foralla,b(E(a,b)=>D(a,b)))$
io invece lo leggevo come un $forall$ davanti a tutto. Ecco perché non mi tornavano le cose.

Sinceramente mi sono perso, non so di cosa stai parlando. Non puoi mettere i quantificatori così a caso. Se hai una proposizione che dipende da $a,b$ quella dipende da $a,b$ e basta, se poi quantifichi $a,b$ dappertutto (o solo in alcune parti) quello che ottieni sarà un'altra proposizione. Il tuo "devo immaginarlo come" non ha senso.

$(forallx(A(x)=>B(x))=>(forally(C(y)=>D(y))$ se non ricordo male l'ho trovato scritto come (cioè <=>)
$forally{[forallx,(A(x)=>B(x)and(C(y)]=>[D(y)]}$

Sì mi pare corretto (ma bisogna sistemare le parentesi).

Cioè il mio trucchetto funziona per puro caso?

Non capisco di che trucchetto parli. Inoltre la domanda "funziona per puro caso?" non la capisco, è come se io ti chiedessi "2+2=4 per puro caso?".

Infine qui
$∀c∈A,[(∃a,b∈A:c=ab)⇒(c=ab=1)] => ∀a,∀b,[(a∈A,b∈A)⇒(ab=1)]$
mi hai fatto accorgere che non ho quantificato a,b ma mi chiedo come farlo in modo sensato, forse così?
$∀c∈A,[∃a,b∈A:((c=ab)⇒(c=ab=1))] => ∀a,∀b,[(a∈A,b∈A)⇒(ab=1)]$
ho cambiato le parentesi.

No non va bene, la prima formulazione è quella giusta, io la scriverei così però:
$∀c∈A,[(∃a,b∈A:c=ab)⇒(c=1)] => ∀a,∀b,[(a∈A,b∈A)⇒(ab=1)]$
Comunque tieni conto che la verità di questa implicazione dipende da una proprietà ben specifica dell'insieme $A$, cioè che sia chiuso per moltiplicazione.

[pistacios]

Direi che grazie alle tue risposte ormai i dubbi si sono ridotti all'osso. Infatti si riducono tutti alla considerazione che ora ho afferrato $(∀x,P(x))⇒(∀x,Q(x))$ è l'unica che posso tradurre nella semplice $P=>Q$ (detto male "senza x e quantificatore").

Sinceramente mi sono perso, non so di cosa stai parlando. Non puoi mettere i quantificatori così a caso.

mi sono spiegato male ma intendevo dire semplicemente che rileggendo degli appunti che avevo ricordo che il professore avesse scritto una frase del genere:

$((A(a,b)⇒B(a,b))and(C(a,b)⇒D(a,b))⇒(E(a,b)⇒D(a,b))$ e reso poi come $((A⇒B)and(C⇒D))⇒(E⇒D)$(*) da qui erano sorte le mie domande perché l'avevo interpretata come$foralla,b,((A(a,b)⇒B(a,b))and(C(a,b)⇒D(a,b))⇒(E(a,b)⇒D(a,b))$
ma credo che avendola potuta scrivere come (*) il prof sottointendesse il per ogni in ogni parentesi $(∀a,b,(A(a,b)⇒B(a,b))and(∀a,b(C(a,b)⇒D(a,b))))⇒(∀a,b(E(a,b)⇒D(a,b)))$ da qui erano originati i dubbi, perché sembrava aver fatto sparire i quantificatori.

Non capisco di che trucchetto parli. Inoltre la domanda "funziona per puro caso?" non la capisco, è come se io ti chiedessi "2+2=4 per puro caso?".

intendevo dire che se parto da $(∀x,(A(x)⇒B(x))⇒(∀y,(C(y)⇒D(y))$ e uso il mio "trucchetto" di scopettare sotto al tappeto i quantificatori trovo $(A⇒B)⇒(C⇒D)$ che è facilmente possibile riscrivere con $[(A⇒B)and]⇒D$ molto simile a $∀y{[∀x,(A(x)⇒B(x))andC(y)]⇒[D(y)]}$. Cioè in poche parole, sbagliando viene giusto. Ma era solo una osservazione senza grande profondità e mi chiedevo chissà come mai pur sbagliando approccio funziona.

Esattamente come $¬∀x,(P(x)=>Q(x))$ che equivale a $∃x,(P(x)and¬Q(x))$ se uno togliesse i quantificatori noterebbe che funziona $¬(P=>Q)$ <=> $P and ¬Q$, questo è come quantificavo prima e funziona, ma per mero caso dato che abbiamo detto che procedere così è errato. Sbaglio? Che funzioni nonostante l'errore non è curioso?

Sì mi pare corretto (ma bisogna sistemare le parentesi).

Per quanto riguarda le parentesi mi sono imbrogliato: ∀y,{[∀x,(A(x)⇒B(x))andC(y)]⇒[D(y)]} dovrebbe essere corretta.
In realtà comunque la domanda voleva essere banale: perché il "per ogni y" finisce davanti a tutto è una regola che non ho capito appieno qui: ∀y,{[∀x,(A(x)⇒B(x))andC(y)]⇒[D(y)]} partendo da (∀x,(A(x)⇒B(x))⇒(∀y,(C(y)⇒D(y))

No non va bene, la prima formulazione è quella giusta, io la scriverei così però:

Ho capito la correzione del caso in esame. Però mi chiedevo, se io ho:
$P(x) => Q(x)$ devo quantificare x sia a dx che a sx per dare un senso e ho le ormai note: ∀x,P(x) => ∀x,Q(x) oppure ∀x,[P(x) => Q(x)].

Se invece ho un esiste ad esempio $(∃x:P(x))=>Q(x)$ questa è sicuramente errata e crea problemi perché non ho quantificato a dx e sx, posso allora avere due scritture come nel caso del per ogni? $(∃x:P(x))=>(∃x:Q(x))$ e $∃x:[P(x)=>Q(x)]$, sono entrambe possibili come scritture no?

[Martino]

da qui erano originati i dubbi, perché sembrava aver fatto sparire i quantificatori.

Non è possibile sapere quale delle diverse versioni che hai scritto intendesse il tuo prof o chi per lui, l'unico modo per saperlo con certezza è chiederglielo.

Che funzioni nonostante l'errore non è curioso?

Hai scritto una proposizione vera, l'hai manipolata un po' e ne è uscita un'altra proposizione vera. Può capitare. Ma le manipolazioni sono fatte sostanzialmente a caso e la verità si è mantenuta per caso.

perché il "per ogni y" finisce davanti a tutto è una regola che non ho capito appieno

Non è una regola, è un fatto ovvio e sinceramente non ritengo che meriti molta spiegazione. Inoltre il "per ogni y" non è obbligato a finire davanti, nella versione equivalente che hai scritto tu è comparso il $AA y$ davanti, ma non eri obbligato a scegliere quella versione.

$(∃x:P(x))=>(∃x:Q(x))$ e $∃x:[P(x)=>Q(x)]$, sono entrambe possibili come scritture no?

Certo che sono entrambe possibili. Perché una scrittura sia possibile basta che abbia una corretta struttura sintattica (sto comunque cercando di interpretare cosa intendi con "scrittura possibile").

[pistacios]

Ti ringrazio tanto per la risposta.
Stanotte ho fatto un lavoraccio e ho cercato di riordinare il più possibile le idee, tanto che sono andato a letto solo 3 ore fa e risvegliato ora bello rinco . In particolare ho drenato con cerca tutte le discussioni sul forum che avessero a che fare con la logica, ho letto diverse dispense da varie università e anche su stackexchange per domande correlate a mie (devo dire che ne ho trovati molti di dubbi simili su quel sito). Ad ora credo proprio di aver individuato il dubbio principale ma non ho trovato risposte che mi permettano di non fare più l'errore, perché in tutta onestà non capisco bene quando posso trasformare in una tavola logica (quindi proposizionale) e quando no i vari predicati quantificati.

Riprendo il tuo esempio:
(1) $(∀x,P(x))⇒(∀x,Q(x))$
(2) $∀x,(P(x)⇒Q(x))$
e dicevi che in effetti qui si può rendere la prima come tavola logica $P=>Q$, mentre la seconda no.
mi sembrava quindi semplice poter dire: se trovo (∀x,P(x))⇒(∀x,Q(x)) è equivalente a P=>Q e basta.

Tuttavia, siano le:
(1') Se ogni x è un gatto allora ogni x è nero.
(2') Per ogni x, se x è un gatto allora x è nero.

Ripensandoci in quest'opera di riorganizzazione mentale che ho cercato di fare credo però di avere già un primo dubbio, infatti se l'insieme universo da cui pesco le x è quello da te proposto {3 gatti bianchi, 1 cane bianco} allora mi accorgo che redigendo la tavola logica non troverei mai quella tipica dell'implicazione, perché la 1' è sempre vera. Quindi in generale non è vero che (∀x,P(x))⇒(∀x,Q(x)) è equivalente a P=>Q.

Ma allora quand'è che si può fare il passaggio di identificare (1) con P=>Q? Non riesco a capirlo e ci ho ragionato con mille esempi per ore.


In secondo luogo mi sono fatto questo esempio: $P(x)=x$ è pari, $D(x)=x$ è dispari
∀x,P(x) = P = "tutti i numeri naturali sono pari" (falso)
∀x,D(x) = D = "tutti i numeri naturali sono dispari" (falso)
uno dice potrei scriverla come $P or D$, niente di più falso perché $[∀x,P(x) or ∀x,D(x)]$ è falsa e basta, non c'è nessuna tavola di verità.

Leggendo nel forum ho trovato alcuni esempi che fanno al caso mio:

Il primo è questo:
Si chiedeva come rielaborare $∀x,((P(x)and¬Q(x))⇒R(x))$ (assumendo però che R(x) sia sempre falsa) e trovare che equivale a $∀x,(P(x)⇒(Q(x))$, il suggerimento è stato: "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à)".
Ecco, questo è un ottimo esempio che esemplifica il punto che non comprendo: perché qua posso usare la tavola di verità e rendere (P and Q)=>False e mostro che è equivalente a $¬P and ¬Q$? E il quantificatore $forallx$?.
Questo caso mi sembra totalmente simile a dire $∀x,((P(x)and¬Q(x))⇒R(x))$ lo rendo (P and Q)=>False ma questo è sbagliato perché è proprio identico all'esempio (2) $∀x,(P(x)⇒Q(x))$ e sappiamo che è sbagliatissimo rendere come P=>Q. (Dicevamo che si può fare così solo se ho la scrittura (1)).

Il secondo è un bell'esempio, chiedeva l'OP:

Vorrei dimostrare che una relazione simmetrica e antisimmetrica è una uguaglianza dati a e b in relazione R tra loro. Cioè questo: [ (aRb => bRa) and ( (aRb and bRa) => a=b) ] => (aRb => a=b)

tramite logica proposizionale/tavola.
In effetti in tal caso, come scritto nella risposta, si può fare una tavola di verità tramite:
"la tua può più semplicemente essere riformulata (rinominando opportunamente le parti) come

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

Questa è una tautologia"

Ecco, anche qui si è potuto sostituire il $(foralla,b, aRb => forall a,b, bRa)$ con $X => Y$ così come $(foralla,b, ((aRb and bRa) => a=b))$ lo scrivo come $(X and Y) => Z)$ ecc.. per gli altri termini. E questo è un caso in cui $(∀x,P(x))⇒(∀x,Q(x))$ diventa $P=>Q$. Ma per me è una magia qui ad esempio funziona, con la questione dei gatti no. Perché?


Come penso sia chiaro dai vari esempi il mio dubbio è centrato attorno allo stesso problema che, di fatto, avevi già evidenziato tu nel penultimo post, non riesco ad afferrare pienamente quando posso rendere una frase logica scritta con quantificatori come una tavola di verità: mi sembra in certi casi si possa fare e in altri casi no proprio come indicavo negli esempi qui sopra. Ma non afferro quando funzioni e quando no. Io credo che capito questo, come mostrato nei vari esempi qui, forse non avrei più dubbi. Il punto è che ho letto davvero centinaia di fonti e continuo a non vedere la chiave di lettura corretta.


Per rispondere al tuo precedente intervento nell'unica parte che mi crea dubbi:

Hai scritto una proposizione vera, l'hai manipolata un po' e ne è uscita un'altra proposizione vera.

Certo, in effetti può capitare, però volevo dire: è sbagliato dire che $¬∀x,(P(x)⇒Q(x))$ equivale $∃x,(P(x)and¬Q(x))$ per via del fatto che $¬(P⇒Q) <=> P and ¬Q$. Infatti la prima usa quantificatori e la seconda no, sono quindi due piani ben diversi se ho capito qualcosa di quanto finora detto.

[Martino]

[...] se l'insieme universo da cui pesco le x è quello da te proposto {3 gatti bianchi, 1 cane bianco} allora mi accorgo che redigendo la tavola logica non troverei mai quella tipica dell'implicazione, perché la 1' è sempre vera. Quindi in generale non è vero che (∀x,P(x))⇒(∀x,Q(x)) è equivalente a P=>Q.

Se da un lato hai "(∀x,P(x))⇒(∀x,Q(x))" e decidi di chiamare $P$ la proposizione (∀x,P(x)) e di chiamare Q la proposizione (∀x,Q(x)), è ovvio che $P => Q$, stai solo dando un nome diverso alle singole proposizioni. Fine.

A me sembra che invece tu, quando scrivi $P$, intenda $P(x)$. Questo lo puoi fare ma quando lo fai stai solo dando per sottinteso il fatto che $P$ significa $P(x)$. Se una proposizione dipende da $x$ allora dipende da $x$ e basta, non è che chiamandola $P$ improvvisamente la dipendenza da $x$ sparisce. Per esempio se $P(x)$ è "$x$ è un gatto" allora cosa sarebbe $P$ secondo te? E' esattamente la stessa frase, ma hai effettuato un cosiddetto abuso di notazione chiamandola $P$. Ripeto, se tu invece di $P(x)$ scrivi $P$ stai solo dando per sottinteso il fatto che $P$ dipende da $x$, e questo non è un problema. Diventa un problema quando ti dimentichi di questo sottinteso e inserisci $P$ dentro una proposizione più complessa in cui riappare $x$.

Un punto di fondamentale importanza è che quando scrivi $P$ devi decidere cosa significa, e lo decidi tu cosa significa, non un'entità superiore. Per esempio se hai $(EE x P(x)) => (EE x Q(x))$ e lo vuoi scrivere come $P => Q$, dovrai definire $P$ uguale a $EE x P(x)$ e $Q$ uguale a $EE x Q(x)$. Ok?

Questa stessa confusione si trova per esempio quando dici:

uno dice potrei scriverla come $P or D$, niente di più falso perché $[∀x,P(x) or ∀x,D(x)]$ è falsa e basta, non c'è nessuna tavola di verità.

Questo tuo "niente di più falso" è stranissimo perché sembra che tu stia attribuendo a $P$ il significato di $AA x P(x)$ quando invece il significato di $P$ lo decidi tu, non è obbligato da un'entità superiore. Inoltre la proposizione "ogni numero naturale è pari oppure ogni numero naturale è dispari" è ovviamente falsa, e quindi?

Poi focalizzati su una cosa: tu scrivi "uno dice potrei scriverla come $P or D$" ma nota che la parola "scriverla" non si riferisce a niente (sopra hai scritto due cose distinte) e mi sembra che "scriverla" nella tua testa si riferisca ad un'ipotetica proposizione che "corregga" le due sopra, posso solo intuire che sia "per ogni numero naturale $x$, abbiamo che $x$ è pari oppure $x$ è dispari". Questo si scrive (ovviamente) $AA x (P(x) or D(x))$ e (forse è bene chiarire questo punto) non si può rendere come $A or B$ (qualsiasi significato tu dia ad $A$ e $B$). Tuttavia osserva che quest'ultima frase che ho scritto (cioè che quella pappardella non si può rendere come un unico OR) è "metalogica" perché è ovvio che, siccome la frase $AA x (P(x) or D(x))$ è vera, qualsiasi proposizione vera sarà equivalente ad essa, quindi per esempio quella frase vera sarà equivalente a $A or A$ data una qualsiasi proposizione vera $A$ (e in questo senso "astratto" sono riuscito a renderla come OR unico, ma questo non è il senso che hai in testa tu).

Ecco, questo è un ottimo esempio che esemplifica il punto che non comprendo: perché qua posso usare la tavola di verità e rendere (P and Q)=>False e mostro che è equivalente a $¬P and ¬Q$? E il quantificatore $forallx$?.

Ti stai perdendo in un bicchier d'acqua. Si può rendere come tabella di verità perché prima hai fissato un (qualsiasi) $x$ e hai scritto la tabella relativa ad $x$. Cioè tu hai una cosa tipo $AA x U(x)$, dove $U(x)$ è la proposizione "$((P(x) and not Q(x)) => R(x)$". E' ovvio che puoi fissare un qualsiasi $x$ e scrivere la tabella della proposizione $U(x)$. Poi mostri che $U(x)$ è equivalente a $not (P(x) and not Q(x))$ (che possiamo chiamare $W(x)$) facendo una tabella di verità (qui non ci sono quantificatori). Hai così dimostrato che $U(x)$ è equivalente a $W(x)$. Siccome questo vale per ogni $x$ ottieni che $(AA x U(x)) <=> (AA x W(x))$.

Ora, questo vale perché abbiamo scelto proposizioni $U(x)$, $W(x)$ che sono equivalenti per ogni $x$. Ora, come ti ho già fatto osservare, se $U(x)$, $W(x)$ sono due proposizioni qualsiasi (cioè su cui non sai niente) allora le due proposizioni
$(AA x U(x)) <=> (AA x W(x))$
$AA x (U(x) <=> W(x))$
NON sono equivalenti.

Ecco, anche qui si è potuto sostituire il $(foralla,b, aRb => forall a,b, bRa)$ con $X => Y$ così come $(foralla,b, ((aRb and bRa) => a=b))$ lo scrivo come $(X and Y) => Z)$ ecc.. per gli altri termini. E questo è un caso in cui $(∀x,P(x))⇒(∀x,Q(x))$ diventa $P=>Q$. Ma per me è una magia qui ad esempio funziona, con la questione dei gatti no. Perché?

Te lo spiego subito: perché se tu sai che
(1) $AA x (P(x) => Q(x))$
è vera allora puoi dedurre che
(2) $(AA x P(x)) => (AA x Q(x))$
è vera. In altre parole (1) implica (2) (cioè $(1) => (2)$). Ci siamo fino a qui?

Il punto su cui devi ragionare è che se INVECE sai che (2) è vera (e questa è l'unica cosa che sai), da qui non puoi dedurre che (1) è vera (cioè (2) non implica (1)). Ma questo non è un problema, perché nell'esempio che hai riportato non si vuole dimostrare che (2) implica (1), si vuole dimostrare che (1) implica (2). Riassumendo, (1) implica (2) ma (2) non implica (1). Se vuoi dimostrare (2), basta dimostrare (1) e hai finito. Quindi (2) non "diventa" (1) (questa è la parola che usi tu), semplicemente invece di dimostrare (2) decidi di dimostrare (1) (che è un'affermazione più forte) sfruttando il fatto che (1) implica (2) (e anche il fatto che dimostrare (1) è più comodo).

è sbagliato dire che $¬∀x,(P(x)⇒Q(x))$ equivale $∃x,(P(x)and¬Q(x))$ per via del fatto che $¬(P⇒Q) <=> P and ¬Q$. Infatti la prima usa quantificatori e la seconda no, sono quindi due piani ben diversi se ho capito qualcosa di quanto finora detto.

Ma non è un problema, però devi trattare i quantificatori $AA$, $EE$ come connaturati nella struttura logica delle dimostrazioni e non come qualcosa che dovrebbe saltar fuori da solo dalle tavole di verità. Il motivo per cui $¬∀x,(P(x)⇒Q(x))$ equivale $∃x,(P(x)and¬Q(x))$ è connaturato nel significato dei simboli $AA$, $EE$, che appunto sono legati dal fatto che in generale dire $not AA x (P(x))$ equivale a dire $EE x (not P(x))$.

Come ripeto, le tabelle di verità non bastano da sole a fare dimostrazioni. I quantificatori e il loro utilizzo stanno alla base delle dimostrazioni logiche come le lettere dell'alfabeto stanno alla base dell'espressione di parole e frasi. Hai già pensato di seguire un corso ben fatto di logica?

[Martino]

Mi è venuta in mente una cosa che probabilmente ti sarà utile, in aggiunta al mio intervento precedente qui sopra.

Per vedere in modo facile e intuitivo perché le due proposizioni

(1) $AA x (P(x) => Q(x))$
(2) $(AA x P(x)) => (AA x Q(x))$

NON sono equivalenti, puoi fare la cosa seguente. Per ogni $x$ scegli un insieme $A_x$ e un altro insieme $B_x$. Prendi un elemento $t$ e chiama $P(x)$ la proposizione "$t in A_x$", chiama $Q(x)$ la proposizione "$t in B_x$". Allora scrivere $AA x P(x)$ significa scrivere $t in bigcap_x A_x$, cioè che $t$ appartiene all'intersezione di tutti gli $A_x$. Analogamente, scrivere $AA x Q(x)$ significa scrivere $t in bigcap_x B_x$, cioè che $t$ appartiene all'intersezione di tutti i $B_x$. Quindi scrivere (1) (quantificata $AA t$) significa scrivere che $A_x subseteq B_x$ per ogni $x$ (cioè che $A_x$ è contenuto in $B_x$ per ogni $x$). Invece scrivere (2) (quantificata $AA t$) significa scrivere che $bigcap_x A_x$ è contenuto in $bigcap_x B_x$. Cioè

(1') $A_x subseteq B_x$ per ogni $x$.
(2') $bigcap_x A_x subseteq bigcap_x B_x$.

Ora dovrebbe risultarti più facile vedere perché (1') non è equivalente a (2'). Se hai due famiglie di insiemi, e gli insiemi della prima sono ordinatamente (in qualche ordine) contenuti in quelli della seconda, allora è chiaro che l'intersezione della prima famiglia sarà contenuta nell'intersezione della seconda famiglia. D'altra parte, se sai solo che l'intersezione della prima famiglia è contenuta nell'intersezione della seconda, non puoi assolutamente dedurre niente sulle mutue inclusioni tra gli insiemi delle due famiglie. In altre parole (1') implica (2') ma (2') non implica (1').

[pistacios]

Volevo cercare di correggere un punto che mi sono accorto di aver spiegato male ma credo proprio sia quello fondamentale dato che in realtà tutti gli esempi che riportavo partono da quel fraintendimento.

Per prima cosa premetto che ho del tutto capito l'errore che facevo, effettivamente scambiavo l'abuso di notazione di scrivere $P$ al posto di $P(x)$ con il rendere effettivamente P(x) una proposizione P vera e propria (che quindi potesse assumere valore vero o falso) e quindi da questo errore poi costruivo tavole di verità su qualcosa che non erano proposizioni, bensì predicati e quindi portava a immancabili errori.

Tuttavia c'è un ultimo concetto che mi stona e mi rendo conto di non averlo espresso bene e volevo vedere se spiegandomi meglio fosse più comprensibile.
Come hai evidenziato fin dall'inizio l'errore più clamoroso era che (1) $∀x(P(x)⇒Q(x))$ io andavo a leggerla come $P=>Q$ e questo errore lo facevo perché pensavo che quantificando la x automaticamente P(x) diventassse una proposizione P e identicamente Q, ma non mi ero accorto che fosse insensato.
Ho quindi poi capito grazie al tuo insegnamento che (2) $(∀xP(x))⇒(∀xQ(x))$ è invece correttamente riespressa come P=>Q, qui senza abuso di notazione e proprio nel senso che P è la proposizione ∀xP(x) e identicamente per ∀xQ(x)=Q.

Fin qui direi che non ci sono più dubbi!

Detto questo c'erano solo alcuni esempi che mi turbavano assai:

Prima categoria
A) il primo a turbarmi è che come detto in via generale vale che: $(∀xP(x))⇒(∀xQ(x))$ lo posso vedere come un $P=>Q$ nominando P=∀xP(x) e Q=∀xQ(x). Quindi in generale mi aspetto che abbia una sua tavola di verità con i tipici 4 valori di verità che può assumere.
Tuttavia mi sembra che non funzioni sempre, infatti se poniamo P(x)="x è un gatto" e Q(x)="x è nero" e prendiamo l'insieme universo {3 gatti bianchi, 1 cane bianco} allora in questo caso specifico P=∀x,P(x)="ogni x è un gatto" e Q=∀x,Q(x)="ogni x è nero", ci accorgiamo che P=>Q non ha una tavola di verità dell'implicazione logica: è solo falsa e basta. E questo mi lasciava perplesso perché mi dicevo "ma come non abbiamo detto che in generale di (∀xP(x))⇒(∀xQ(x)) posso fare una tavola di verità identica all'implicazione? Perché non funziona invece qui?". Se io scrivo P=>Q non riesco a immaginare casi in cui non possa esistere la sua tavola, perché P assume valori veri e falsi e così Q e li vado a intersecare, coi gatti non quaglia.

B) Il caso dei numeri era identico, volevo mettere in mostra qualcosa di simile.

Testo nascosto, fai click qui per vederlo

P(x)=x è pari, D(x)=x è dispari
∀x,P(x) = P = "tutti i numeri naturali sono pari" (falso)
∀x,D(x) = D = "tutti i numeri naturali sono dispari" (falso)

A questo punto non volevo dire che in generale $[∀x,P(x)or∀x,D(x)]$ è falsa e basta, volevo dire che da [∀x,P(x)or∀x,D(x)]mi aspettavo la stessa tavola di verità di $P or D$ dato che ho identificato con P la proposizione ∀x,P(x) e con D=∀x,D(x), però in questo caso specifico non è così, perché facendo P or D ho "tutti i numeri naturali sono pari" OR "tutti i numeri naturali sono dispari" che è appunto falso e basta. Queste cose mi lasciavano un attimo perplesso.

seconda categoria
La seconda categoria di dubbi, accomunati dallo stesso concetto era che in certi casi, l'errore che compivo all'inizio, ossia di intendere [(1) $∀x(P(x)⇒Q(x))$ come esprimibile dalla semplice tavola dell'implicazione: $P=>Q$] (*) sembra funzionare (sia chiaro, so ora che è sbagliato proprio grazie alla conversazione avuta, tuttavia dai singoli semplici esempi non capisco allora come vadano letti non potendo più operare questa "semplificazione" che ho compreso essere sbagliata). Cioè in altre parole detto, quello che chiedo è: prima mi funzionavano perché operavo questa sostituzione errata (*) e funzionava, ma ora che so che questo processo è sbagliato, come è corretto invece vederle?

C) Prendiamo la [$∀x,((P(x)and¬Q(x))⇒R(x))$ con R(x) sempre falsa]=[$∀x,(P(x)⇒(Q(x))$]. Nel mio modo errato di procedere l'avrei giustificata così: ∀x,((P(x)and¬Q(x))⇒R(x)) diviene $(P and ¬Q)=>F$ (con F false), quindi:
$(P and Q)=>F <=> ¬(P and Q) or F <=> ¬P or Q or F <=> ¬P or Q <=> P=>Q$. Funzionerebbe però peccato che parta dall'assunto errato che $∀x,((P(x)and¬Q(x))⇒R(x))$ l'ho scritto come $(P and ¬Q)=>F$ e che $∀x,(P(x)⇒(Q(x))$ lo identifico con $P=>Q$ che abbiamo detto che non si fa perché ho brutalmente tolto il quantificatore e ciao .
Quindi questa spiegazione che mi ero dato ed ero convinto fosse alla base di questo discorso è invece sbagliata.

Tu dici

E' ovvio che puoi fissare un qualsiasi x e scrivere la tabella della proposizione U(x). Poi mostri che U(x) è equivalente a

ed è quindi qui che mi incasino, perché se prima abbiamo detto che non è corretta quella "semplificazione" del quantificatore, perché ora si può fare? Credo semplicemente che quello che ho scritto non sia la giustificazione che cercavo, ma non so quale sia allora.

D)

Te lo spiego subito: perché se tu sai che

qui non sono sicuro di aver capito appieno, quindi vedo di ri-esporre per esser sicuro di averti compreso.

io voglio mostrare che [ (∀a,b,(aRb => bRa)) and ( ∀a,b,((aRb and bRa) => a=b)) ] => ∀a,b,(aRb => a=b) che schematizzo con [ I and II ] => III

a questo punto sfruttando il tuo suggerimento che ∀x(P(x)⇒Q(x)) implica (∀xP(x))⇒(∀xQ(x)), noto che:
I = $(∀a,b,(aRb => bRa))$ => $(∀a,b,(aRb)) => (∀a,b,(bRa))$
identicamente:
II = $( ∀a,b,((aRb and bRa) => a=b))$ => $(∀a,b,(aRb and bRa)) => (∀a,b,(a=b))$

III = stesso ragionamento dei primi due

Quindi posso riscrivere nel complesso I II e III:
[(∀a,b,(aRb)) => (∀a,b,(bRa))] and [(∀a,b,(aRb and bRa)) => (∀a,b,(a=b))] => [∀a,b,(aRb) => ∀a,b,(a=b)]
oss: ora dato dato il quantificatore presente in ogni punto mi riduco al caso $(∀xP(x))⇒(∀xQ(x))$ che posso scrivere "incorporando il quantificatore": $P=>Q$
E quindi semplicemente: [ (X => Y) and ( (X and Y) => Z) ] => (X => Z)
Se ho ben capito è questa l'idea.
Io invece erroneamente pensavo che si dicesse: ∀a,b,(aRb => bRa) diventa X=>Y e quindi quel per ogni "levato" mi disturbava perché sembrava avvallare il mio errore

E) infine qui compio di nuovo lo stesso errore:

è sbagliato dire che $¬∀x,(P(x)⇒Q(x))$ equivale $∃x,(P(x)and¬Q(x))$ per via del fatto che $¬(P⇒Q) <=> P and ¬Q$. Infatti la prima usa quantificatori e la seconda no, sono quindi due piani ben diversi se ho capito qualcosa di quanto finora detto.

anche qui il mio errore era sempre quello:
partivo da: $¬∀x,(P(x)⇒Q(x))$ e dicevo me la riscrivo (ERRORE) come $¬(P⇒Q)$ che è evidentmente uguale logicamente a $P and ¬Q$ e quindi (ERRORE) deducevo che $∃x,(P(x)and¬Q(x))$. Si ok, ma sbaglio con i quantificatori per il solito motivo suddetto. E quindi la domanda è: come si giustifica? Io sbagliavo. ma non capisco come tenere "connaturati" i quantificatori.

Spero ora si capisca meglio le due "categorie" di misunderstanding che compivo coi quantificatori: sembravano funzionare, pur essendo errati, per puro "sedere", ma facevo magheggi errati che nella mia testa funzionavano... senza di te avrei vissuto una vita di menzogna con loro

Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.

Io purtroppo sono iscritto a fisica e sicuramente un matematico (più sveglio) non avrebbe 'sti dubbi, però questo discorso con te mi ha intrigato a tal punto che penso con certezza che vorrò dedicare parte dei miei cfu liberi a un corso di logica al dip. di matematica. Mi accorgo che oltre ad averne bisogno, mi incuriosiscono moltissimo e mi hai dato così tanti concetti che ne sono rimasto affascinato di quanto non sapessi. Purtroppo potrò farlo solo tra 2 anni (al terzo anno abbiamo cfu liberi), nel frattempo mi accontento di quel che sono riuscito a racimolare e quel che sicuramente leggerò nel prossimo/breve futuro.

[Martino]

scambiavo l'abuso di notazione di scrivere $P$ al posto di $P(x)$ con il rendere effettivamente P(x) una proposizione P vera e propria (che quindi potesse assumere valore vero o falso) e quindi da questo errore poi costruivo tavole di verità su qualcosa che non erano proposizioni, bensì predicati e quindi portava a immancabili errori.

Qui comunque vedo una confusione: non si capisce cosa intendi quando dici "una proposizione vera e propria". Se io dico "2+2=4" questa è una proposizione vera e propria? Direi proprio di sì. Sembri pensare che una proposizione vera e propria debba non avere un valore di verità assegnato, invece potrebbe averlo.

La cosa si ripete qui:

A) il primo a turbarmi è che come detto in via generale vale che: $(∀xP(x))⇒(∀xQ(x))$ lo posso vedere come un $P=>Q$ nominando P=∀xP(x) e Q=∀xQ(x). Quindi in generale mi aspetto che abbia una sua tavola di verità con i tipici 4 valori di verità che può assumere.

Tuttavia mi sembra che non funzioni sempre, infatti se poniamo P(x)="x è un gatto" e Q(x)="x è nero" e prendiamo l'insieme universo {3 gatti bianchi, 1 cane bianco} allora in questo caso specifico P=∀x,P(x)="ogni x è un gatto" e Q=∀x,Q(x)="ogni x è nero", ci accorgiamo che P=>Q non ha una tavola di verità dell'implicazione logica: è solo falsa e basta.

Ma certo, e quindi? Fai un esempio più semplice: la proposizione "2+2=5" è falsa e basta, non ha senso scrivere la sua tabella di verità. La tabella di verità va scritta solo quando hai una proposizione composta da varie parti ognuna delle quali può potenzialmente assumere ciascuno dei due valori di verità possibili. Per esempio posso voler dimostrare che "$((P => Q) and P) => Q$ (modus ponens) per qualsiasi scelta di $P,Q$, e qui devo fare una tabella di verità perché $P$ e $Q$ sono qualsiasi. Se invece voglio mostrare che $P => Q$ qui la tabella di verità mi dirà che questo non è sempre vero, tuttavia se scelgo $P$ uguale alla proposizione (falsa) "2+2=5" allora improvvisamente $P => Q$ diventa vera. Ridotta all'osso, la tua confusione è dovuta al fatto che pensi che una "proposizione" sia un enunciato a cui puoi attribuire ciascuno dei due valori di verità, cosicché "2+2=4" per te non sarebbe una proposizione (invece lo è). Se io voglio dimostrare il modus ponens di cui sopra, è sottinteso che lo voglio dimostrare per ogni scelta delle due proposizioni $P$ e $Q$ (e non solo per alcune). Questo "per ogni $P,Q$" si traduce nel fatto che sia $P$ che $Q$ potranno assumere tutti i valori di verità possibili e questo si traduce nella necessità di una tabella di verità.

prima mi funzionavano perché operavo questa sostituzione errata (*) e funzionava, ma ora che so che questo processo è sbagliato, come è corretto invece vederle?

Te l'ho già spiegato (rileggi il mio intervento precedente): tu vuoi dimostrare che
(*) $(AA x P(x)) => (AA x Q(x))$
e INVECE di dimostrare questo, scegli di dimostrare la seguente
(**) $AA x (P(x) => Q(x))$
che è una proposizione più forte e implica (*) (cioè (**) implica (*)). Quindi (*) non diventa (**), semplicemente scegli di dimostrare un'altra cosa che però implica la cosa che vuoi dimostrare. Pensaci bene. In ogni caso, anche se la cosa non ti è del tutto chiara, ricordati che queste cose richiedono tempo, le devi sedimentare, rielaborare. Quanto ho scritto qui risponde anche al tuo punto (C). Continui a scrivere cose tipo "A diventa B" (dove A e B sono proposizioni) ma la verità, in generale, è che A non diventa B, semplicemente invece di dimostrare A scegli di dimostrare B.

Si ok, ma sbaglio con i quantificatori per il solito motivo suddetto. E quindi la domanda è: come si giustifica? Io sbagliavo. ma non capisco come tenere "connaturati" i quantificatori.

Te l'ho già detto: ti devi ricordare che $not AA x P(x)$ è equivalente a $EE x (not P(x))$.

Ripeto di nuovo: per fare dimostrazioni le tavole logiche non bastano. I quantificatori sono parte integrante del processo. Per esempio se io dico "per ogni intero dispari $x$ si ha che $8$ divide $x^2-1$", questo lo posso rendere come $AA x (P(x) => Q(x))$ dove $P(x)$ è "$x$ è un intero dispari" e $Q(x)$ è "$8$ divide $x^2-1$". Come si dimostra? Facendo una tabella di verità? No. Si dimostra così:

Per prima cosa, siccome c'è il quantificatore $AA x$, dobbiamo fissare un qualsiasi intero $x$. Poi siccome dobbiamo dimostrare che $P(x) => Q(x)$ assumiamo $P(x)$ vera (perché se $P(x)$ è falsa l'implicazione $P(x) => Q(x)$ è automaticamente vera). Quindi adesso abbiamo un intero dispari $x$. Siccome $x$ è dispari possiamo scrivere $x=2m+1$ dove $m$ è un intero. Abbiamo quindi $x^2-1 = (2m+1)^2-1 = 4m^2+4m=4m(m+1)$. Questo numero è divisibile per $8$ perché uno tra $m$ e $m+1$ è pari. Quindi $x^2-1$ è divisibile per $8$. Fine.

Ti ho fatto questo semplice esempio per mostrarti che quando dimostri qualcosa devi certamente usare le tabelle di verità ma queste da sole non bastano assolutamente.

Comunque leggere quello che scrivi è molto difficile perché hai delle costruzioni mentali imprecise e attribuisci alle parole significati imprecisi. Per questo ti dico che devi rielaborare queste cose e non ti diventeranno chiare da un semplice scambio su un forum.

[Martino]

Complementando il mio intervento precedente,

tu vuoi dimostrare che
(*) $(AA x P(x)) => (AA x Q(x))$
e INVECE di dimostrare questo, scegli di dimostrare la seguente
(**) $AA x (P(x) => Q(x))$
che è una proposizione più forte e implica (*) (cioè (**) implica (*)).

Potresti provare a dimostrare che (**) implica (*). E' molto facile ma allo stesso tempo vale la pena farlo.

[pistacios]

So che ti sembrerà strano dopo tutte le caSSatone che ho detto finora, ma in realtà molte cose ora le ho capite. Perché a ogni risposta tua ci ragiono per molto e molto tempo integrando con quanto ho letto (anche se non sembra proprio per le stupidaggini, ma ho letto molti documenti e dispense). Quindi questi dubbi erano già frutto di una elaborazione personale, seppur sbagliata.

Però insomma, per ricapitolare:

Ridotta all'osso, la tua confusione è dovuta al fatto che pensi che una "proposizione" sia un enunciato a cui puoi attribuire ciascuno dei due valori di verità

hai capito benissimo e questa era una cosa che in effetti non capito e la "prima categoria" di errori nasceva da questo mio malinteso. Io immaginavo che P=>Q dovesse avere sempre 4 valori perché partivo proprio da quel presupposto errato che menzioni.

Continui a scrivere cose tipo "A diventa B" (dove A e B sono proposizioni) ma la verità, in generale, è che A non diventa B, semplicemente invece di dimostrare A scegli di dimostrare B.

a scanso di equivoci, questo in realtà l'avevo già capito nel messaggio prima del tuo ultimo (non per merito mio, ma perché semplicemente me l'hai spiegato molto chiaramente), ma era un errore che facevo in principio. Nell'ultimo messaggio l'avevo riscritto solo per dire "prima pensavo funzionasse per questo motivo ma ora ho capito che non è così ma in certi punti non capisco il reale ragionamento"




Detto ciò per riuscire a chiudere gli ultimi argomenti rimasti (ma che di fatto sono figli dello stesso) dei tanti aperti inizialmente:

Questa cosa è chiarissima in me:

Testo nascosto, fai click qui per vederlo

tu vuoi dimostrare che
(*) (∀xP(x))⇒(∀xQ(x))
e INVECE di dimostrare questo, scegli di dimostrare la seguente
(**) ∀x(P(x)⇒Q(x))

ma vorrei riuscire ad applicarla

1) nel punto D) io voglio mostrare logicamente (ho capito che di solito non funziona ma qui in effetti anche solo con la tavola di verità dovrebbe riuscire) che
$[ (∀a,b,(aRb => bRa)) and ( ∀a,b,((aRb and bRa) => a=b)) ] => ∀a,b,(aRb => a=b)$ che schematizzo con $[ I and II ] => III$ e il suggerimento è di sfruttare la tavola di verità di
[ (X => Y) and ( (X and Y) => Z) ] => (X => Z) e mostrare che è una tautologia. Mio dubbio: come mi porto allora a quella tabella? Il fatto è che se la tautologia di quella proposizione dimostra il teorema iniziale allora vuol dire che devo dimostrare che ci sia un legame tra le due, no? Proviamo:

sfruttando il tuo suggerimento che ∀x(P(x)⇒Q(x)) implica (∀xP(x))⇒(∀xQ(x)), noto che:
I = $(∀a,b,(aRb => bRa))$ => $(∀a,b,(aRb)) => (∀a,b,(bRa))$
identicamente:
II = $( ∀a,b,((aRb and bRa) => a=b))$ => $(∀a,b,(aRb and bRa)) => (∀a,b,(a=b))$

Quindi l'antecedente di quella di partenza composta da I e II implica:
=>$[(∀a,b,(aRb)) => (∀a,b,(bRa))] and [(∀a,b,(aRb and bRa)) => (∀a,b,(a=b))]$ (**)
oss: ora, dato il quantificatore presente in ogni punto sono in un caso simile a $(∀xP(x))⇒(∀xQ(x))$ che posso scrivere "incorporando il quantificatore": $P=>Q$

E quindi semplicemente: (**)=>[ (X => Y) and ( (X and Y) => Z) ] ma questa implica a sua volta (X => Z).
Però questo non conclude ancora perché (X => Z) vuol dire $[∀a,b,(aRb)] =>[∀a,b,(a=b)]$ e quindi come arrivo a $∀a,b,(aRb => a=b)$? Perché è quello il risultato che io voglio.

Quello che di fatto vorrei capire è il passaggio per cui [ (aRb => bRa) and ( (aRb and bRa) => a=b) ] => (aRb => a=b) portandomi a

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

[ (X => Y) and ( (X and Y) => Z) ] => (X => Z) che è una tautologia

Dimostra l'asserto. Perché io mi blocco in quel punto che dicevo.


2) Per il punto C

C) Prendiamo la [∀x,((P(x)and¬Q(x))⇒R(x)) con R(x) sempre falsa]=[∀x,(P(x)⇒(Q(x))] (k). Nel mio modo errato di procedere l'avrei giustificata così: ∀x,((P(x)and¬Q(x))⇒R(x)) diviene (Pand¬Q)⇒F (con F false), quindi:

quando ho detto "diviene" intendevo (come spiegavo sopra) che evidenziavo il mio ragionamento errato (conscio ora che fosse errato) ma chiedevo: come si fa allora in modo corretto?

Il fatto che non riesco a sfruttare il suggerimento:

Testo nascosto, fai click qui per vederlo

tu vuoi dimostrare che
(*) (∀xP(x))⇒(∀xQ(x))
e INVECE di dimostrare questo, scegli di dimostrare la seguente
(**) ∀x(P(x)⇒Q(x))

Provo a spiegare dove mi incastro:

Il suggerimento dice:
"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à)".

Io voglio mostrarmi che posso portarmi a quella tabellaa di verità. Quindi devo riuscire a riscrivere la parte quantificata in modo che mi crei delle proposizioni.

-$∀x,((P(x) and ¬Q(x))=>R$ (per quanto in spoiler)=> $∀x,(P(x) and ¬Q(x)) => ∀x,R(x)$ <=> (qui posso fare il giochetto di "incorporare"¹ il quantificatore nella proposizione) $P and ¬Q => R$ <=> (dato che R è sempre falsa) $P=>Q$

- Prendo ora il conseguente di (k): $∀x,(P(x)⇒(Q(x))$ => $[forallx,P(x)] => [forall x, Q(X)]$ <=> $P=>Q$

Ora se confronto le due ho che:
$∀x,((P(x) and ¬Q(x))=>R$ =>$∀x,(P(x) and ¬Q(x)) => ∀x,R(x)$ <=> $P=>Q$ <=> $[forallx,P(x)] => [forall x, Q(X)]$
e qua mi fermo perché l'implicazione in grassetto che discende da quanto in spoiler non mi permette di tornare a $∀x,(P(x)⇒(Q(x))$ e invece ho bisogno di riuscirci per chiudere la dimostrazione. Non capisco quindi come fare.


3) Qualcosa di analogo è per il caso E): "si dimostri che ¬∀x,(P(x)⇒Q(x)) equivale ∃x,(P(x)and¬Q(x))".
$¬∀x,(P(x)⇒Q(x))$ per quanto in spoiler implica $[¬∀x,(P(x))]⇒[¬∀x,Q(x))]$ seguendo il tuo suggerimento sui quantificatori e negazione, questo equivale a <=> $∃x,(¬P(x))=>∃x(¬Q(x))$.
ma come mi porto poi alla: $∃x,(P(x)and¬Q(x))$


Credo che per i 3 esempi l'errore non si più di concetto, ma che non ho ben capito come sfruttare i tuoi dettami per dimostrare le varie cose.


Come dicevo inizialmente il mio errore era quello che dicevi tu, cioè che sbagliavo a considerare

(*) (cioè (**) implica (*)). Quindi (*) non diventa (**)

dove precisamente io pensavo "diventassero". Ora il mio dubbio è molto più pragmaticamente che non so come concludere le due avendo capito i tuoi suggerimenti

Ripeto di nuovo: per fare dimostrazioni le tavole logiche non bastano.

Questo è un altro errore che facevo in effetti, cioè pensavo che tutto si potesse ridurre a una tavola (stile esempio D dove si riesce di fatto a ridurre a una tavola), ma quello è un caso molto raro: di solito non si usano le tavole. Però lì in effetti funziona da quanto leggevo.


Siccome ti ho fatto molte domande mi sembra giusto anche rispondere alla tua (che mi fai per aiutarmi a ragionare e imparare quindi eccola):

Testo nascosto, fai click qui per vederlo

Sembrerà strano ma appena ho letto il tuo suggerimento sopra, ieri, questa dimostrazione è la prima cosa che ho provato a svolgere e pensandola corretta non mi sono posto ulteriori dubbi, procediamo...

si vuole mostrare $∀x,(A(x)=>B(x))$=>$(∀x,A(x))=>(∀x,B(x))$

Ho pensato di procedere per assurdo e ipotizzando che questa affermazione sia falsa.
Quando una implicazione è falsa? beh quando antecedente è vero e conseguente falso. Quindi: $(∀x,A(x))$ vera ma $(∀x,B(x))$ falsa.

Ora, $(∀x,B(x))$ falsa vuol dire $(∃x,¬B(x))$ vera. Quindi esiste un $x'$ tale per cui $¬B(x')$ vera. Teniamolo da parte.

Ora mi concentro sull'antecedente $∀x,(A(x)=>B(x))$, mi accorgo che vale per ogni x, quindi vale anche specificatamente per x' scelto. Quindi: A(x')=>B(x') vera, ossia A(x') vera e B(x') vera.

Giungo così a un assurdo perché B(x') è vera, ma prima ho anche detto che ¬B(x') è vera: ASSURDO.

Fine.

Non so se ho solo fatto un casino ma mi sembra funzionare

---

Note

1. scusa la bruta spiegazione ma è solo per spiegare a parole ciè che ho fatto ↑