Cercasi esperto in logica matematica :)
Salve! mi son appena iscritto a questo forum! sono uno studente universitario ed a breve dovrei sostenere l'esame di logica matematica ma ho alcune preplessità su argomento come la soddisfacibilità etc. Cè qualcuno tra di voi che può darmi una mano ?
Risposte
guarda bemipefe non ricordo bene di cosa si tratta ha a che fare con anelli gruppi etc etc ???
Grazie puntovale!
La prima domanda era sulla "chiusura transitiva"....o meglio non so cosa sia quest'ultima.
PS: Con linux le lettere accentate vengono sostituite da strani codici........ non so perchè faccia così
Bemipefe
La prima domanda era sulla "chiusura transitiva"....o meglio non so cosa sia quest'ultima.
PS: Con linux le lettere accentate vengono sostituite da strani codici........ non so perchè faccia così
Bemipefe
Rispondo alla tua seconda domanda (la prima non la leggo bene appaiono caratteri strani)
Supponiamo di voler verificare che la somma dei primi n numeri è uguale a n*(n+1)/2 o meglio
0+1+....+n = n*(n+1)/2
hai due possibilità
1) verifichi che l'equazione di prima valga per qualunque n ossia
Se n = 0
0 = 0*(0+1)/2 ??? SI
se n= 1
0+1 = 1*(1+1)/2 ??? Si
se n = 2
0+1+2 = 2*(2+1)/2 ??? SI
e così via per tutti i possibili valori di n. Ovviamente tale soluzione è impraticabile data l'infinità di controlli che dovresti effettuare per cui non ti resta che adoperare il principio di induzione
2) per verificare la proprietà di prima applicando il P.I., devi verificare che tale proprietà valga per n= 0 e SUPPONENDO che tale proprietà valga per n (generico) cerchi di ottendere una dimostrazione che la stessa proprietà valga per n+1. Ora se riesci ad ottenere una tale dimostrazione puoi senz'altro concludere che la proprietà vale per ogni n intero.
Ritornando all'esempio di prima
a) la proprietà vale quando n = 0 ???? certamente si infatti è vero che 0 = 0*(0+1)/2
b) supponendo che tale proprietà valga per n (cioè che è vero che 0+1+...+n = n*(n+1)/2 ), cerco di ottenere una dimostrazione che tale proprietà valga anche per n+1 (e quindi devo ottenere una dimostrazione del fatto che 0+1+....+(n+1) = (n+1)*(n+1+1)/2 ) . Allora partendo dalla somma dei primi n+1 nuemri ho:
0+1+2+3+4+5+.....+n+(n+1) = (0+1+2+3+4+5+...+n) + (n+1)
Ma prima ho supposto che la proprietà vale per n e che quindi la somma dei primi n numeri è pari a n*(n+1)/2, per cui la somma di prima diventa:
0 +1+....+n+(n+1) = n*(n+1)/2 + (n+1)= [n*(n+1) + 2*(n+1)] /2 =
= [(n+1)*(n+2)] / 2 = [(n+1)*(n+1+1)]/2
ma è proprio quello che cercavo per cui posso concludere che la somma dei primi n numeri è pari a n*(n+1)/2 qualunque sia l'n considerato
In Logica il principio di induzione di formalizza così:
{ P(0) et Vn[ P(n) -> P(n+1) ] } -> VnP(n)
Spero di esserti stato utile ciao
Supponiamo di voler verificare che la somma dei primi n numeri è uguale a n*(n+1)/2 o meglio
0+1+....+n = n*(n+1)/2
hai due possibilità
1) verifichi che l'equazione di prima valga per qualunque n ossia
Se n = 0
0 = 0*(0+1)/2 ??? SI
se n= 1
0+1 = 1*(1+1)/2 ??? Si
se n = 2
0+1+2 = 2*(2+1)/2 ??? SI
e così via per tutti i possibili valori di n. Ovviamente tale soluzione è impraticabile data l'infinità di controlli che dovresti effettuare per cui non ti resta che adoperare il principio di induzione
2) per verificare la proprietà di prima applicando il P.I., devi verificare che tale proprietà valga per n= 0 e SUPPONENDO che tale proprietà valga per n (generico) cerchi di ottendere una dimostrazione che la stessa proprietà valga per n+1. Ora se riesci ad ottenere una tale dimostrazione puoi senz'altro concludere che la proprietà vale per ogni n intero.
Ritornando all'esempio di prima
a) la proprietà vale quando n = 0 ???? certamente si infatti è vero che 0 = 0*(0+1)/2
b) supponendo che tale proprietà valga per n (cioè che è vero che 0+1+...+n = n*(n+1)/2 ), cerco di ottenere una dimostrazione che tale proprietà valga anche per n+1 (e quindi devo ottenere una dimostrazione del fatto che 0+1+....+(n+1) = (n+1)*(n+1+1)/2 ) . Allora partendo dalla somma dei primi n+1 nuemri ho:
0+1+2+3+4+5+.....+n+(n+1) = (0+1+2+3+4+5+...+n) + (n+1)
Ma prima ho supposto che la proprietà vale per n e che quindi la somma dei primi n numeri è pari a n*(n+1)/2, per cui la somma di prima diventa:
0 +1+....+n+(n+1) = n*(n+1)/2 + (n+1)= [n*(n+1) + 2*(n+1)] /2 =
= [(n+1)*(n+2)] / 2 = [(n+1)*(n+1+1)]/2
ma è proprio quello che cercavo per cui posso concludere che la somma dei primi n numeri è pari a n*(n+1)/2 qualunque sia l'n considerato
In Logica il principio di induzione di formalizza così:
{ P(0) et Vn[ P(n) -> P(n+1) ] } -> VnP(n)
Spero di esserti stato utile ciao
.....altra domanda oltre a quella sopra fatta:
Vorrei sapere se qualcuno sà in che modo si debba partire nella dimostrazione per induzione........
.....bisogna fare uso esclusivamente delle variabili n +1 , n+2 ........oppure è meglio utilizzare il risultato , cioè il valore numerico diretto.
Ad esempio se parto (per la dimostrazione) dal valore 0 , e poi partendo da questo valore n estendo la dimostrazione ad n+1........
.....ad n+1 devo usare il valore 1 = (0+1) oppure devo usare (n+1)
.......in questo caso però diventa un casino gia rappresentare 2 cioè n+2 = [(n+1) +1]..........se poi voglio andare avanti?
Non avreste un esempio pratico e semplice per capire la tecnica di dimostrazione?
GRAZIE Ciao!
Bemipefe
Vorrei sapere se qualcuno sà in che modo si debba partire nella dimostrazione per induzione........
.....bisogna fare uso esclusivamente delle variabili n +1 , n+2 ........oppure è meglio utilizzare il risultato , cioè il valore numerico diretto.
Ad esempio se parto (per la dimostrazione) dal valore 0 , e poi partendo da questo valore n estendo la dimostrazione ad n+1........
.....ad n+1 devo usare il valore 1 = (0+1) oppure devo usare (n+1)
.......in questo caso però diventa un casino gia rappresentare 2 cioè n+2 = [(n+1) +1]..........se poi voglio andare avanti?
Non avreste un esempio pratico e semplice per capire la tecnica di dimostrazione?
GRAZIE Ciao!
Bemipefe
Qualcuno potrebbe spiegarmi cos#232; la Chiusura Transitiva?
.....PS: Conosco le proprit#224; delle relazioni , Riflessiva ......etc........
Bemipefe
.....PS: Conosco le proprit#224; delle relazioni , Riflessiva ......etc........
Bemipefe
Se posso puntualizzare: non si tratta di un confronto "letterario", cioè non si confrontano diverse opininioni, ma (in matematica) si ricerca una "verità" e le eventuali contraddizioni "oggettive"..
grazie bemipefe crepi il lupo ed in bocca al lupo anche a te
Cmq è vero mi avete aiutato tantissimo, è sempre utile conoscere diverse opinioni
Cmq è vero mi avete aiutato tantissimo, è sempre utile conoscere diverse opinioni
Grazie Infinito....quando ho un po di temp oci sò un occhiata.
E su quello che hai detto a proposito del dominio vuoto del predicato di puntovale concordo. Se non c'è nessun elemento il predicato è Falso.
Scusa puntovale, ma questo periodo stò preparando un altro esame e ho avuto poco tempo. Spero che la tua preparazione si stata aiutata da questo forum e comunque.....Imboccallupo!
Metticela Tutta! [:D]
CIAO!
Bemipefe
E su quello che hai detto a proposito del dominio vuoto del predicato di puntovale concordo. Se non c'è nessun elemento il predicato è Falso.
Scusa puntovale, ma questo periodo stò preparando un altro esame e ho avuto poco tempo. Spero che la tua preparazione si stata aiutata da questo forum e comunque.....Imboccallupo!
Metticela Tutta! [:D]
CIAO!
Bemipefe
ok infinito grazie per la conferma
Per Bemipefe
Per riposnderti su "l'infinito" ti invito a rileggerti il mio precedente post, e per l'induzione su altri insiemi infiniti (visto che il prinicipio di induzione si attua comunemente sull'insieme infinito dei naturali ...) ti invito a leggere la mi arisposta postata il 21/06/2005 alle 03:13:02 su «induzione.... » che si trova in questo stesso forum in «Giochi logico-matematici e gara»: credo che ti stupirai.
ripeto: sull'insieme vuoto Ø è vero qualunque predicato del tipo «per ogni elemento a del Ø è vera la proposizione p», perchè (in un certo senso) è falsa l'ipotesi, ma se tutto il predicato precedente è l'ipotesi allora l'ipotesi è vera.
Nel caso specifico l'identità in Ø è una relazione riflessiva, simmetrica, ecc., ma quella del testo era «Vxy[R(x,y) or R(y,x)] -> EyVx(R(y,x))», che ha evidente mente l'ipotesi vera e la tesi falsa, quindi è falsa.
Per puntovale
Anch'io non vi seguo più, comunque il to esempio di relazione "maggiore o uguale" sui naturali (o comunque su un dominio senza un massimo) andava bene.
Per riposnderti su "l'infinito" ti invito a rileggerti il mio precedente post, e per l'induzione su altri insiemi infiniti (visto che il prinicipio di induzione si attua comunemente sull'insieme infinito dei naturali ...) ti invito a leggere la mi arisposta postata il 21/06/2005 alle 03:13:02 su «induzione.... » che si trova in questo stesso forum in «Giochi logico-matematici e gara»: credo che ti stupirai.
ripeto: sull'insieme vuoto Ø è vero qualunque predicato del tipo «per ogni elemento a del Ø è vera la proposizione p», perchè (in un certo senso) è falsa l'ipotesi, ma se tutto il predicato precedente è l'ipotesi allora l'ipotesi è vera.
Nel caso specifico l'identità in Ø è una relazione riflessiva, simmetrica, ecc., ma quella del testo era «Vxy[R(x,y) or R(y,x)] -> EyVx(R(y,x))», che ha evidente mente l'ipotesi vera e la tesi falsa, quindi è falsa.
Per puntovale
Anch'io non vi seguo più, comunque il to esempio di relazione "maggiore o uguale" sui naturali (o comunque su un dominio senza un massimo) andava bene.
no aspetta non ti seguo. Io devo dimostare che in domini infiniti la formula non è valida e quindi devo fornire una interpretazione di controesempio che mi rende falsa l'implicazione qui sotto e quindi rende vere le premesse e falsa la conclusione EyVxR(y,x) ok ??
{VxR(x,x) et Vxyz[R(x,y) et R(y,z) -> R(x,z)] et Vxy[R(x,y) or R(y,x)]} -> EyVxR(y,x)
ora l'interpretazione che ho considerato è R(x,y) = " x maggiore o uguale a y". Perke ho considerato tale interpretazione ??? perke appunto rende vere le premesse e falsa la conslusione ed infatti:
Tale relazione è riflessiva (se non ci fosse l'uguale non sarebbe riflessiva), è transitiva e per ogni x e y o e R(x,y) o è R(y,x). Ma la conclusione è falsa infatti non esiste nessun numero y che è più grande di tutti gli altri.
Ora la relazione che consideri tu di "successore" non è un controesempio poichè non rende vere tutte le premesse in quanto non riflessiva. Quindi l'implicazione qui su sarebbe vera e quindi non è un controesempio.
{VxR(x,x) et Vxyz[R(x,y) et R(y,z) -> R(x,z)] et Vxy[R(x,y) or R(y,x)]} -> EyVxR(y,x)
ora l'interpretazione che ho considerato è R(x,y) = " x maggiore o uguale a y". Perke ho considerato tale interpretazione ??? perke appunto rende vere le premesse e falsa la conslusione ed infatti:
Tale relazione è riflessiva (se non ci fosse l'uguale non sarebbe riflessiva), è transitiva e per ogni x e y o e R(x,y) o è R(y,x). Ma la conclusione è falsa infatti non esiste nessun numero y che è più grande di tutti gli altri.
Ora la relazione che consideri tu di "successore" non è un controesempio poichè non rende vere tutte le premesse in quanto non riflessiva. Quindi l'implicazione qui su sarebbe vera e quindi non è un controesempio.
Scusa ma stmattina il caldo mi dà alla testa.... [xx(]
quello che ho scritto io è uguale a quello che hai scritto tu e quindi va bene anche "x è maggiore di y" chè è l'eqivalente (più o meno) di "x è successore di y"
Quindi a parte l'uguale che non sò a cosa possa servire è OK quello che dici
CIAO! Scusa di nuovo
Bemipefe
quello che ho scritto io è uguale a quello che hai scritto tu e quindi va bene anche "x è maggiore di y" chè è l'eqivalente (più o meno) di "x è successore di y"
Quindi a parte l'uguale che non sò a cosa possa servire è OK quello che dici
CIAO! Scusa di nuovo
Bemipefe
No no aspetta ho scritto una cavoalta...
la proprietà è << x è 'successore' di y >> quindi vale per tutte le xy di N ma non per lo zero che non è successore di nessuno.
Scusa ma come vedi il mio cervello tende molto a 'risparmiare' invece di lasciarmi pensare.
CIAO!
Bemipefe
la proprietà è << x è 'successore' di y >> quindi vale per tutte le xy di N ma non per lo zero che non è successore di nessuno.
Scusa ma come vedi il mio cervello tende molto a 'risparmiare' invece di lasciarmi pensare.
CIAO!
Bemipefe
Per quanto ne sò ti dico questo:
Il controesempio come dimostrazione è ok , però non mi sembra ok il tipo di controesempio.
Io sò che nell'insieme dei Naturali ci sono Infiniti successori e quindi si troverà sempre un 'x' maggiore di un 'y', ed è proprio questo che definisce N un insieme infinito. Il fatto che ci sia anche 'uguale' non credo cambi o influenzi "l'enunciato" ;
"i predicati" hanno i quantificatori, quindi potresti semmai scrivere così Vxy appartenente a N vale la propietà che hai detto tu. Ma questa come penso io, è valida.
Potresti usare invece questo esempio:
Vxy appartenente a N << x è 'minore' di y >> creando al coppia
R(x;y) .....questa se ti accorgi lavora su dominio infinito ma esiste un elemento che non è minore di nessuno; lo "zero".
Vedi se va bene e fammi sapere CIAO! Wink [;)]
Bemipefe
Il controesempio come dimostrazione è ok , però non mi sembra ok il tipo di controesempio.
Io sò che nell'insieme dei Naturali ci sono Infiniti successori e quindi si troverà sempre un 'x' maggiore di un 'y', ed è proprio questo che definisce N un insieme infinito. Il fatto che ci sia anche 'uguale' non credo cambi o influenzi "l'enunciato" ;
"i predicati" hanno i quantificatori, quindi potresti semmai scrivere così Vxy appartenente a N vale la propietà che hai detto tu. Ma questa come penso io, è valida.
Potresti usare invece questo esempio:
Vxy appartenente a N << x è 'minore' di y >> creando al coppia
R(x;y) .....questa se ti accorgi lavora su dominio infinito ma esiste un elemento che non è minore di nessuno; lo "zero".
Vedi se va bene e fammi sapere CIAO! Wink [;)]
Bemipefe
allora io devo dimostrare che la formula di prima è valida in tutti i domini finiti ma che non è valida nei domini infiniti.
Ora se ho capito bene dire che la formula non è valida in domini infiniti significa dire che esiste un controesempio (e quindi una interpretazione) su un dominio infinito che rende falsa la formula.
Ho quindi considerato come controesempio l'interpretazione che associa al preticato R(x,y) = " x è maggiore o uguale a y" che sul dominio dei naturali dovrebbe falsificare la formula.
Pertanto la formula su domini infiniti non può essere valida poichè esiste almeno una interpretazione che la falsifica. ti trovi?
Ora se ho capito bene dire che la formula non è valida in domini infiniti significa dire che esiste un controesempio (e quindi una interpretazione) su un dominio infinito che rende falsa la formula.
Ho quindi considerato come controesempio l'interpretazione che associa al preticato R(x,y) = " x è maggiore o uguale a y" che sul dominio dei naturali dovrebbe falsificare la formula.
Pertanto la formula su domini infiniti non può essere valida poichè esiste almeno una interpretazione che la falsifica. ti trovi?
Scusa puntovale ma non ti seguo.....sarà il caldo.......
a che sereve sostituire una relazione o meglio una coppia con ">=" ?
Bemipefe
a che sereve sostituire una relazione o meglio una coppia con ">=" ?
Bemipefe
si maggiore o uguale da sostituirsi alla relazione R(x,y) nella formula
Si ok il predicato ho capito che era quello da cui siamo partiti ma cos'è la relazione di maggioreuguale ">=" ?
Bemipefe
Bemipefe
bemipefe per la relazione >= mi riferisco alla formula {VxR(x,x) et VxVyVz[R(x,y)et R(y,z) -> R(x,z)] et VxVy[R(x,y) o R(y,x)]} -> EyVxR(y,x) da cui è pertita tutta la discussione sui domini infiniti e finiti
Vi trovate con me che tale relazione di >= è un controesempio che dimostri come non può essere valida tale formula in domini infiniti come i naturali ??
Vi trovate con me che tale relazione di >= è un controesempio che dimostri come non può essere valida tale formula in domini infiniti come i naturali ??
Scasate se ho spezzato il post in due ma mi è venuto in mente un altro controesempio sulla transitività sempre fatto dasl Prof.
dato R1 = { (1,2) } relazione sottoinsieme di A x A con A = {1,2}
e R2 = { (2,3) } relazione sottoinsieme di B x B con B = {2,3}
mi disse e mi spiegò che infatti gli insiemi disgiunti sono Transitivi mentre la loro unione non lo è perchè a questo punto esise (x;y) ed esite (y;z) quindi la premessa è vera ma l'implicazione è falsa.
Risultato l'intera formula della transitività è flasa per la logica V-->F = F
CIAO!
Bemipefe
dato R1 = { (1,2) } relazione sottoinsieme di A x A con A = {1,2}
e R2 = { (2,3) } relazione sottoinsieme di B x B con B = {2,3}
mi disse e mi spiegò che infatti gli insiemi disgiunti sono Transitivi mentre la loro unione non lo è perchè a questo punto esise (x;y) ed esite (y;z) quindi la premessa è vera ma l'implicazione è falsa.
Risultato l'intera formula della transitività è flasa per la logica V-->F = F
CIAO!
Bemipefe
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo