Logica formale: sostituzione di una sottoformula per equivalenza
Rodolfo Medina
A quanto pare, è un principio universalmente accettato nella logica formale il
fatto che, sostituendo una sottoformula di una formula con una sottoformula
equivalente, si ottiene una formula equivalente.
Però non ho potuto trovare la dimostrazione di questo prinicpio.
Qualcuno sa darmi un'indicazione in proposito?
Gazie di eventuali risposte.
Rodolfo
Radicale
Questa e' facile, posso aiutarti :
Tu prendi una formula logica qualunque
f(p1,p2,p3, ...pn) dove pj sono proposizioni.
Allora la f( ) assumera' 0 o 1 per ogni
assegnazione (0 o 1) fatto alle pj.
Ok ?
Quindi se al posto di una pj metti
a sua volta una formula g(h1,h2, ...hm)
dove hj sono proprosizioni qualunque che
accade ?
Accade che per ogni assegnazione delle hj,
pj = g( ) avra' valore 0 o 1.
E quindi f(p1,p2, ... g(h1,h2,...hm), ...pn)
assumera' gli stessi identici valori che
assumeva prima di effettuare la sostituzione.
E percio' la f( ) con la sostituzione e'
equivalente alla f( ) senza sostituzione.
Rodolfo Medina
>> A quanto pare, è un principio universalmente accettato nella logica formale
>> il fatto che, sostituendo una sottoformula di una formula con una
>> sottoformula equivalente, si ottiene una formula equivalente.
>>
>> Però non ho potuto trovare la dimostrazione di questo prinicpio.
>>
>> Qualcuno sa darmi un'indicazione in proposito?
Radicale <mcat...@bancafideuram.it> writes:
> Questa e' facile, posso aiutarti :
>
> Tu prendi una formula logica qualunque
> f(p1,p2,p3, ...pn) dove pj sono proposizioni.
>
> Allora la f( ) assumera' 0 o 1 per ogni
> assegnazione (0 o 1) fatto alle pj.
> Ok ?
>
> Quindi se al posto di una pj metti
> a sua volta una formula g(h1,h2, ...hm)
> dove hj sono proprosizioni qualunque che
> accade ?
>
> Accade che per ogni assegnazione delle hj,
> pj = g( ) avra' valore 0 o 1.
>
> E quindi f(p1,p2, ... g(h1,h2,...hm), ...pn)
> assumera' gli stessi identici valori che
> assumeva prima di effettuare la sostituzione.
>
> E percio' la f( ) con la sostituzione e'
> equivalente alla f( ) senza sostituzione.
Ok, grazie, il ragionamento mi sembra valido.
Però esso, facendo uso delle tavole di verità, mi sembra che valga solo per le
proposizioni e quindi nell'ambito del calcolo proposizionale.
Io vorrei una dimostrazione che valga, più in generale, anche nel calcolo dei
predicati, dove le tavole di verità non bastano. Qui:
http://en.wikibooks.org/wiki/Formal_Logic/Sentential_Logic/Substitution_and_Interchange
si afferma infatti che una tale dimostrazione non è affatto semplice.
Ciao
Rodolfo
Radicale
> On 10 Ago, 13:08, Rodolfo Medina <rodolfo.med...@gmail.com> wrote:
>
>
>
>
>
> >> A quanto pare, è un principio universalmente accettato nella logica formale
> >> il fatto che, sostituendo una sottoformula di una formula con una
> >> sottoformula equivalente, si ottiene una formula equivalente.
>
> >> Però non ho potuto trovare la dimostrazione di questo prinicpio.
>
> >> Qualcuno sa darmi un'indicazione in proposito?
> > Questa e' facile, posso aiutarti :
>
> > Tu prendi una formula logica qualunque
> > f(p1,p2,p3, ...pn) dove pj sono proposizioni.
>
> > Allora la f( ) assumera' 0 o 1 per ogni
> > assegnazione (0 o 1) fatto alle pj.
> > Ok ?
>
> > Quindi se al posto di una pj metti
> > a sua volta una formula g(h1,h2, ...hm)
> > dove hj sono proprosizioni qualunque che
> > accade ?
>
> > Accade che per ogni assegnazione delle hj,
> > pj = g( ) avra' valore 0 o 1.
>
> > E quindi f(p1,p2, ... g(h1,h2,...hm), ...pn)
> > assumera' gli stessi identici valori che
> > assumeva prima di effettuare la sostituzione.
>
> > E percio' la f( ) con la sostituzione e'
> > equivalente alla f( ) senza sostituzione.
>
> Ok, grazie, il ragionamento mi sembra valido.
>
> Però esso, facendo uso delle tavole di verità, mi sembra che valga solo per le
> proposizioni e quindi nell'ambito del calcolo proposizionale.
>
> Io vorrei una dimostrazione che valga, più in generale, anche nel calcolo dei
> predicati, dove le tavole di verità non bastano. Qui:
>
>
> si afferma infatti che una tale dimostrazione non è affatto semplice.
Ah beh ... Mi dispiace, ma fino a la non ci arrivo.
Attendiamo l' intervento di qualcuno competente.
Barone Barolo
> Ok, grazie, il ragionamento mi sembra valido.
>
> Però esso, facendo uso delle tavole di verità, mi sembra che valga solo per le
> proposizioni e quindi nell'ambito del calcolo proposizionale.
>
> Io vorrei una dimostrazione che valga, più in generale, anche nel calcolo dei
> predicati, dove le tavole di verità non bastano. Qui:
>
> http://en.wikibooks.org/wiki/Formal_Logic/Sentential_Logic/Substitution_and_Interchange
>
> si afferma infatti che una tale dimostrazione non è affatto semplice.
Il problema più grosso è quello della cattura di variabile. Invece di
perdere anni di vita con la definizione di sostituzione
capture-avoiding, assumi che tutte le variabili legate siano distinte e
diverse dalle variabili libere (convenzione di Barendregt).
A quel punto definisci per bene l'enunciato del teorema:
Ipotesi:
P e Q fbf del primo ordine
tali che per ogni modello M, M |= P <=> M |= Q
R fbf del primo ordine
Tesi:
Per ogni modello M, M |= R <=> M |= R[Q/P]
La dimostrazione dovrebbe venire per induzione strutturale su R. Tieni
conto che se S è una sottoformula di R, ti troverai con una ipotesi
induttiva del tipo
Per ogni modello M, M |= S <=> M |= S[Q/P]
Il fatto che l'ipotesi induttiva sia quantificata su ogni modello è
cruciale nel caso dei quantificatori.
-- bb
fm2766
> Però non ho potuto trovare la dimostrazione di questo prinicpio.
Un *principio* non si *dimostra* !
Rodolfo Medina
> >> A quanto pare, è un principio universalmente accettato nella logica
> >> formale il fatto che, sostituendo una sottoformula di una formula con una
> >> sottoformula equivalente, si ottiene una formula equivalente.
>
> >> Però non ho potuto trovare la dimostrazione di questo prinicpio.
>
> >> Qualcuno sa darmi un'indicazione in proposito?
Barone Barolo <xelloss.met...@gmail.com> writes:
> Il problema più grosso è quello della cattura di variabile. Invece di perdere
> anni di vita con la definizione di sostituzione capture-avoiding, assumi che
> tutte le variabili legate siano distinte e diverse dalle variabili libere
> (convenzione di Barendregt).
>
> A quel punto definisci per bene l'enunciato del teorema:
>
> Ipotesi:
> P e Q fbf del primo ordine
> tali che per ogni modello M, M |= P <=> M |= Q
> R fbf del primo ordine
>
> Tesi:
> Per ogni modello M, M |= R <=> M |= R[Q/P]
>
> La dimostrazione dovrebbe venire per induzione strutturale su R.
Grazie del tuo aiuto. Ma:
1) cosa intendi per `induzione strutturale' su R?
2) conosci qualche fonte accessibile in internet (o qualche testo) dove tale
dimostrazione sia svolta?
Ciao
Rodolfo
Peter11
"Rodolfo Medina" <rodolfo...@gmail.com> ha scritto nel messaggio
news:87ljlqe...@gmail.com...
>
> 1) cosa intendi per `induzione strutturale' su R?
http://www.dsi.unive.it/~lf/2008/handouts/rule-induction.pdf.
Radicale
> http://www.dsi.unive.it/~lf/2008/handouts/rule-induction.pdf.
Ahhh ! *quella* si chiama "pomposamente" induzione
strutturale ? La conoscevo, ma mica lo sapevo che
si chiamava accussi' ! :D
E' un concetto semplicissimo. E bello.
Barone Barolo
> 1) cosa intendi per `induzione strutturale' su R?
principio di induzione strutturale sulle fbf del primo ordine:
Sia P(...) una qualunque asserzione su fbf del primo ordine e scriviamo
P(p) se P è valida per la fbf p.
Se valgono le seguenti condizioni:
1) P(A) è valida per ogni atomo A (compresi predicati n-ari del tipo
A(t1,..,tn))
2) P(bottom) è valida
3) Se P(p) e P(q) sono valide (ipotesi induttive), lo sono anche P(p ->
q), P(p /\ q), P(p \/ q)
4) Se P(p) è valida (ipotesi induttiva), lo sono anche P(\forall x.p) e
P(\exists x.p), per ogni scelta della variabile x.
allora P(p) è valida per ogni fbf p.
> 2) conosci qualche fonte accessibile in internet (o qualche testo) dove tale
> dimostrazione sia svolta?
No, e in effetti non ne ho mai studiato la dimostrazione (poi magari su
qualche mio libro c'è, ma ora sono in vacanza e non li ho dietro :-));
ma con lo schema che ti ho dato non dovrebbe essere molto difficile.
Utilizzi il principio di induzione suddetto, dove P è la proprietà
scritta nel mio precedente messaggio: a quel punto si tratta di
applicare ipotesi e definizioni.
-- bb
radicale
wrote:
>principio di induzione strutturale sulle fbf del primo >ordine:
Non ho mai capito una cosa :
(scusa se mi intrometto, poi so che non ti sono
nemmeno simpatico quindi ... )
che differenza c'e' tra :
logica proposizionale
logica proposizionale + quantificatori
logica del primo ordine
logica del secondo ordine
Inoltre :
... Ce ne sono di ordini successivi ?
Infine :
il linguaggio sufficiente e necessario
per far matematica qual' e' tra quelli
elencati ? Se e' tra quelli elencati.
Grazie.
Rodolfo Medina
> che differenza c'e' tra :
> logica proposizionale
> logica proposizionale + quantificatori
> logica del primo ordine
> logica del secondo ordine
>
> Inoltre :
> ... Ce ne sono di ordini successivi ?
>
> Infine :
> il linguaggio sufficiente e necessario
> per far matematica qual' e' tra quelli
> elencati ? Se e' tra quelli elencati.
Non sono esperto a riguardo, mi sto appena orientando sulla materia, che però
trovo estremamante affascinante, sorprendente.
La logica proposizionale si occupa di proposizioni, cioè affermazioni prive di
variabili: es.: quando il tempo brutto mi annoio; oggi il tempo è brutto;
quindi oggi mi annoio;
la logica del primo ordine, cioè la logica predicazionale, presuppone la prima
ma la estende allo studio dei predicati, cioè delle affermazioni riferite a
variabili: es.: x è un uomo, quindi x è mortale;
le logiche di ordine successivo non sono importanti e possono essere trascurate
(almeno da me in questo momento! :)).
Una buona trattazione la trovi qui:
http://www.sapere.it/tca/minisite/scienza/tuttomatematica/id100002.html
. Ma il sito internet che ho trovato veramente strabiliante sull'argomento è:
http://www.qedeq.org/mathematics.html
, solo che il tizio non risponde alla mia mail. Ciò che ho trovato in quel
sito è quasi incredibile per me.
Rodolfo
Rodolfo Medina
> che differenza c'e' tra :
> logica proposizionale
> logica proposizionale + quantificatori
> logica del primo ordine
> logica del secondo ordine
>
> Inoltre :
> ... Ce ne sono di ordini successivi ?
>
> Infine :
> il linguaggio sufficiente e necessario
> per far matematica qual' e' tra quelli
> elencati ? Se e' tra quelli elencati.
Il linguaggio sufficiente e necessario per far matematica è quello del primo
ordine, su cui si basano le varie formulazioni della teoria assiomatica degli
insiemi.
Rodolfo
Peter11
> radicale <radic...@gmail.com> writes:
>
>
> Il linguaggio sufficiente e necessario per far matematica � quello del
> primo
> ordine, su cui si basano le varie formulazioni della teoria assiomatica
> degli
> insiemi.
>
> Rodolfo
E per descrivere la struttura dei numeri naturali va bene?
Barone Barolo
> le logiche di ordine successivo non sono importanti e possono essere trascurate
> (almeno da me in questo momento! :)).
Sono molto importanti a dire il vero, ma probabilmente solo per chi
studia logica nello specifico e non matematica in generale.
La logica del secondo ordine è quella in cui è possibile quantificare su
intere proposizioni. In questa logica il falso diventa un connettivo
definito: infatti \forall P.P = "ogni proposizione P è vera" è
un'asserzione autocontraddittoria.
Nelle logiche di ordine superiore è possibile quantificare sui
connettivi logici. Per esempio potrei dire che esiste un connettivo *
tale che se A*B è vero, anche A è vero (un connettivo di questo tipo è
la congiunzione /\). Si dice "ordine superiore" perché questa
quantificazione sui connettivi può essere generalizzata a operazioni che
manipolano connettivi e così via fino all'infinito.
-- bb