Logica matematica

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

ZioGiò
Livello 4
Livello 4
Messaggi: 156
Iscritto il: sab gen 14, 2006 4:30 pm
Località: Mailand (Milano)
Contatta:

Logica matematica

Messaggio da ZioGiò »

Ave basecinquini!

Per la serie "A volte ritornano (quando hanno bisogno di aiuto)" eccomi qui con alcuni quesiti di logica. Sto seguendo il corso in dialetto austriaco e ho trovato diversi libri in inglese perfettamente incomprensibili (o meglio la teoria fila via liscia, ma quando poi devo applicare le cose non so da che parte voltarmi). C'è qualche volenteroso che vuole darmi una mano? Sono ben accette anche spiegazioni prolisse e passo passo! :mrgreen:
Dovrebbero essere problemi banalissimi, ma se rimango ingolfato in questi figuriamoci all'esame.

Immagine

Grazie, vi leggo sempre con piacere!

Fabio
"Voi mi considerate un uomo sanza lettere, ma siete degli stolti perché le mie cose sono date dall'esperienza non dalle parole."
Leonardo Da Vinci

Immagine

Daniela
Livello 6
Livello 6
Messaggi: 456
Iscritto il: lun nov 21, 2005 9:40 am

Messaggio da Daniela »

ti do' un controesempio per la seconda

P(x)= x e' un elefante
Q(x)= x indossa una collana di perle

Esiste x t.c. (P(x) ET Q(x)) = esiste almeno un elefante con filo di perle al collo
(Esiste x t.c. P(x)) ET (Esiste x t.c. Q(x)) = esiste almeno un elefante ET esiste almeno un individuo con collana di perle
se esistono elefanti ed esistono appassionati di collane di perle, ma nessuna tra le signore eleganti e' un'elefantessa, il lato di destra e' valido ma non quello di sinistra, quindi il "se e solo se" non vale
Daniela
"L'essenza della libertà è la matematica"

ZioGiò
Livello 4
Livello 4
Messaggi: 156
Iscritto il: sab gen 14, 2006 4:30 pm
Località: Mailand (Milano)
Contatta:

Messaggio da ZioGiò »

Ciao Daniela!

Grazie del suggerimento.
Io avevo pensato a

P(x): x > 3
Q(x): x < 0

Il lato destro è soddisfatto ma quello sinistro no. E' corretto?

Sono anche riuscito (credo) a risolvere l'ultimo esercizio.
Ma provare per definizione mi è ancora ostico (in quanto non ho nemmeno capito di cosa si tratti)... Dove sono i formalisti di base5??? :mrgreen:

Saluti!
"Voi mi considerate un uomo sanza lettere, ma siete degli stolti perché le mie cose sono date dall'esperienza non dalle parole."
Leonardo Da Vinci

Immagine

Daniela
Livello 6
Livello 6
Messaggi: 456
Iscritto il: lun nov 21, 2005 9:40 am

Messaggio da Daniela »

Ciao Fabio!
"provare per definizione" significa per forza bruta con le tabelle di verita', oppure se preferisci, usando le regole della logica proposizionare ricavare una espressione dall'altra con frecce se-e-solo-se
buon divertimento
Daniela
"L'essenza della libertà è la matematica"

ZioGiò
Livello 4
Livello 4
Messaggi: 156
Iscritto il: sab gen 14, 2006 4:30 pm
Località: Mailand (Milano)
Contatta:

Messaggio da ZioGiò »

Ah, quante cose si imparano qui :mrgreen:
Come mi sbarazzo del quantificatore "esiste" per creare una tabella di verità?
Magari è pure una domanda senza senso ma non prendetemi in giro che davvero non ho capito niente di questa roba (e sono pure 7.5 ECTS!)!

Sono anche ben accetti consigli su libri italiani CON esercizi e numerosi esempi svolti. Così durante le vacanze di Natale mi rimeto in pari.

Tschüss!
"Voi mi considerate un uomo sanza lettere, ma siete degli stolti perché le mie cose sono date dall'esperienza non dalle parole."
Leonardo Da Vinci

Immagine

ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

Messaggio da ronfo »

Non sono molto ferrato in materia ma ho trovato questo sito vedi un po' se Ti è di aiuto.
http://progettomatematica.dm.unibo.it/l ... intro.html

CIAO

ZioGiò
Livello 4
Livello 4
Messaggi: 156
Iscritto il: sab gen 14, 2006 4:30 pm
Località: Mailand (Milano)
Contatta:

Messaggio da ZioGiò »

Ciao Ronfo!

Grazie per il link. Un po' entry-level ma ho trovato alcune spiegazioni interessanti (più che altro a livello di comprensione, poi gli esercizi sono sempre un'altra cosa)

Bye!
"Voi mi considerate un uomo sanza lettere, ma siete degli stolti perché le mie cose sono date dall'esperienza non dalle parole."
Leonardo Da Vinci

Immagine

Daniela
Livello 6
Livello 6
Messaggi: 456
Iscritto il: lun nov 21, 2005 9:40 am

Messaggio da Daniela »

Se hai in mente le regole per portare le espressioni in forma normale di skolem, il resto dovrebbe venire immediato. Dov'e' l'intoppo ;-)
Daniela
"L'essenza della libertà è la matematica"

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Messaggio da Gianfranco »

Ciao a tutti,

ZioGiò, credo che nel testo del primo esercizio, al posto di "per definizione" sia più corretto scrivere "per derivazione" o qualcosa del genere.

Se ben ricordo cose fatte oltre 30 anni fa, quando skolemizzavamo tutti perché non c'era ancora il sudoku, portare un'espressione in forma normale di Skolem significa trasportare tutti i quantificatori all'inizio (forma normale prenessa) ed eliminare i quantificatori esistenziali.

Non so se può esserti utile, ma per far ciò ricordo che utilizzavo le seguenti regole che applicavo all'espressione data, procedendo dalle parentesi più interne verso quelle più esterne:
(per comodità uso la seguente notazione:
Ux = quantificatore universale
Ex = quantificatore esistenziale
V = OR
& = AND
-> = implica
~ = NOT)

OR
1) Ux A(x) V B si può trasformare in Ux (A(x) V B)
2) Ex A(x) V B si può trasformare in Ex (A(x) V B)
1b) commutato di 1)
2b) commutato di 2)

AND
3) Ux A(x) & B si può trasformare in Ux (A(x) & B)
4) Ex A(x) & B si può trasformare in Ex (A(x) & B)
3b) commutato di 3
4b) commutato di 4

IMPLICA
5) Ux A(x) -> B si può trasformare in Ex (A(x) -> B)
6) Ex A(x) -> B si può trasformare in Ux (A(x) -> B)
7) B -> Ux A(x) si può trasformare in Ux (B -> A(x))
8) B -> Ex A(x) si può trasformare in Ex (B -> A(x))

NOT
9) ~Ux A(x) si può trasformare in Ex ~A(x)
10) ~Ex A(x) si può trasformare in Ux ~A(x)

PER ELIMINARE I QUANTIFICATORI Esistenziali SI USA LA SEGUENTE
12) Ux1 Ux2... Uxn Ey A(x1, x2, ..., xn, y) si può trasformare in
Ux1 Ux2... Uxn A(x1, x2, ..., xn, g(x1, x2, ..., xn))

---------------------------------
Provo a trasformare UNA PARTE dell'espressione proposta, e precisamente questa: (poiché ho solo dei vaghi ricordi, non garantisco nulla)

Ex P[x,y,z] & (Ex Q[x,u] -> Ev Q[y,v])

a) Lavoro sulla seconda parentesi, che contiene:
Ex Q[x,u] -> Ev Q[y,v]

Applico la 6):
Ux (Q[x,u] -> Ev Q[y,v])

Applico la 8) alla parentesi rimasta:
Ux Ev (Q[x,u] -> Q[y,v])

Sostituisco nell'espressione di partenza:
Ex P[x,y,z] & Ux Ev (Q[x,u] -> Q[y,v])

b) Lavoro sull'espressione ottenuta:
Ex P[x,y,z]) & Ux Ev (Q[x,u] -> Q[y,v]

Distinguo le variabili x
Ex1 P[x1,y,z] & Ux2 Ev (Q[x2,u] -> Q[y,v])

Applico la 4)
Ex1 (P[x1,y,z] & Ux2 Ev (Q[x2,u] -> Q[y,v]))

Applico la 3b)
Ex1 Ux2 (P[x1,y,z] & Ev (Q[x2,u] -> Q[y,v]))

Applico la 4b)
Ex1 Ux2 Ev (P[x1,y,z] & (Q[x2,u] -> Q[y,v]))

Così dovrebbe essere in forma normale prenessa.

c) Ora bisogna eliminare i quantificatori E

Ex1 Ux2 Ev (P[x1,y,z] & (Q[x2,u] -> Q[y,v]))

Elimino Ex1
Ux2 Ev (P[c,y,z] & (Q[x2,u] -> Q[y,v])) (dove c è una costante opportuna)

Elimino Ev
Ux2 (P[c,y,z] & (Q[x2,u] -> Q[y,d])) (dove d è una costante opportuna)
---------------------------------
P.S. Mi piacerebbe conoscere la soluzione esatta e completa.

Gianfranco

ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

Messaggio da ronfo »

Mi sa tanto che Gianfranco deve aver commesso qualche svista nell'elenco delle sue trasformazioni.
Comunque per ZioGiò e per quanti sono interessati un mio amico che frequenta..va l'università mi ha dato i documenti sotto allegati ...
non so quanto possano essere utili perchè io non ho tempo ( e poca voglia) per studiarli.
CIAO

ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

Messaggio da ronfo »

lo sapevo che facevo casino...
come faccio ad allegarvi documenti PDF???

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Messaggio da Gianfranco »

Ciao Ronfo,

Hai scritto:
Mi sa tanto che Gianfranco deve aver commesso qualche svista nell'elenco delle sue trasformazioni.
Per quel che riguarda la parte di esercizio che ho svolto, io stesso ho detto che non garantisco, perché sono argomenti che ho studiato molti molti anni fa...

Ma per quel che riguarda le formule, sono SERIAMENTE interessato a sapere quali sono le sviste (a parte le pedanti precisazioni sulle varibili libere etc. che non ho riportato per non appesantire il discorso)

Credo che il pdf puoi inserirlo nello spazio dove mettiamo le immagini e creare un link.

Ciao
Gianfranco

ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

Messaggio da ronfo »

Premetto che sono un Ignorante in materia ( notare la i maiuscola) e che tutto ciò che so di logica l'ho imparato come autodidatta...
Ciò che mi ha lasciato perplesso è che Tu hai scritto ad esempio:
OR
1) Ux A(x) V B si può trasformare in Ux (A(x) V B)
2) Ex A(x) V B si può trasformare in Ex (A(x) V B)

ma dov'è la trasformazione ? Oppure in questo caso non si trasforma ?
Penso ( ma questa è una mia opinione) che Tu volessi scrivere:

OR
1) Ux A(x) V B si può trasformare in Ux (A(x) & B)
2) Ex A(x) V B si può trasformare in Ex (A(x) & B)
Ripeto credo sia così ma non ho i razionali per confermarlo.
Per quanto riguarda i documenti PDF mi puoi spiegare meglio cosa devo fare?
CIAO

ronfo
Livello 5
Livello 5
Messaggi: 211
Iscritto il: dom mag 14, 2006 8:27 pm

Messaggio da ronfo »

Aspetta che forse ho capito.
No è andata buca , l'estensione del pdf non è prevista !!!
Hai altri suggerimenti

ZioGiò
Livello 4
Livello 4
Messaggi: 156
Iscritto il: sab gen 14, 2006 4:30 pm
Località: Mailand (Milano)
Contatta:

Messaggio da ZioGiò »

Ciao Gianfranco!
Grazie dell'aiuto!
ZioGiò, credo che nel testo del primo esercizio, al posto di "per definizione" sia più corretto scrivere "per derivazione" o qualcosa del genere.
Hai ragione. Per definizione è fuorviante...

Fortunatamente sono riuscito, grazie alla complicità di un collega ceco (nel senso di abitante della Repubblica Ceca), a risolvere l'esercizio :mrgreen:
Ovviamente ora siamo già al capitolo successivo e non sappiamo che pesci pigliare. Magari incontriamo qualche altro studente (o studentessa :mrgreen:) internazionale con cui risolvere il nuovo compito! E dire che il sequent calculus è davvero facile!

Immagine
1) Ux A(x) V B si può trasformare in Ux (A(x) V B)
2) Ex A(x) V B si può trasformare in Ex (A(x) V B)

ma dov'è la trasformazione ? Oppure in questo caso non si trasforma ?
Penso ( ma questa è una mia opinione) che Tu volessi scrivere:

OR
1) Ux A(x) V B si può trasformare in Ux (A(x) & B)
2) Ex A(x) V B si può trasformare in Ex (A(x) & B)
E' quella roba strana per cui non si usano gli stessi simboli di AND ma bisogna distinguerli, eh?

Saluti!
"Voi mi considerate un uomo sanza lettere, ma siete degli stolti perché le mie cose sono date dall'esperienza non dalle parole."
Leonardo Da Vinci

Immagine

Rispondi