Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Fondamenti di Informatica, 9 CFU => Topic started by: Franco Barbanera on 16-10-2018, 11:58:11



Title: Esercizio sistemi formali
Post by: Franco Barbanera on 16-10-2018, 11:58:11
Sia Numbers il sistema formale definito come segue:
S={0,s,(,),i,N}
W={xiN | x e' una stringa in S*}
Ax={ s(s(0))iN }
R = {pippo, pluto} dove

                  xiN
   (pippo) ----------   in cui x e' una qualsiasi stringa in S*
                 s(x)iN

                 s(0)iN
   (pluto) -------------
                   0iN

Definiamo la semantica di Numbers nel seguente modo:
una fbf xiN e' valida quando, interpretando il simbolo '0' come il numero 0 e 's' come la funzione 'incremento di uno', x rappresenta un numero naturale.
Dimostrare che rispetto a questa semantica Numbers e' un sistema corretto.
Numbers e' anche completo? Giustificare adeguatamente la risposta.
La regola (pluto) e' derivabile? Perche'?
E' ammissibile? Perche'?


Title: Re:Esercizio sistemi formali
Post by: InfernoMentale on 18-10-2018, 00:14:53
Il nostro sistema è Corretto in quanto il nostro assioma rispetta la Semantica infatti 2 è un numero appartenente a iN. la R"Pluto" invece è Derivabile tramite ragionamento Ipotetico usando la nostra Fbf contenuta in W (insieme delle fbf) xiN con la quale si giunge subito alla conclusione della nostra R:"Pluto".Data la sua derivazione tramite fbf possiamo dire che è anche Ammissibile e tramite le due R:(Pippo,Pluto) il nostro sistema è anche completo in quanto riusciamo a dedurre da quello che è il valore 0 tramite R:"Pluto", Al suo incremento tramite R:"Pippo" che coadiuvato all'assioma Ax riusciamo a dedurre tutti i nostri giudizi validi utilizzando la nostra semantica.

Spero che tutto questo sia corretto  |-O Attendo risposta


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 18-10-2018, 07:49:24
Quote
Il nostro sistema è Corretto in quanto il nostro assioma rispetta la Semantica infatti 2 è un numero appartenente a iN.

Non basta.
Devi far vedere che ogni teorema e' valido.



Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 18-10-2018, 07:52:24
l
Quote
a R"Pluto" invece è Derivabile tramite ragionamento Ipotetico usando la nostra Fbf contenuta in W (insieme delle fbf) xiN con la quale si giunge subito alla conclusione della nostra R:"Pluto".

Queste sono chiacchere.
Devi far vedere che per pluto vale la condizione della definizione di derivabilita'.
Devi cioe' far vedere, mostrando una derivazione, che  s(0)iN |-- 0iN
Oppure mostrare che cio' non e' possibile.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 18-10-2018, 07:53:47
Quote
Data la sua derivazione tramite fbf possiamo dire che è anche Ammissibile

Questo sarebbe vero se fosse derivabile (poiche' una regola derivabile e' anche ammissibile).


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 18-10-2018, 07:55:56
Quote
tramite le due R:(Pippo,Pluto) il nostro sistema è anche completo in quanto riusciamo a dedurre da quello che è il valore 0 tramite R:"Pluto", Al suo incremento tramite R:"Pippo" che coadiuvato all'assioma Ax riusciamo a dedurre tutti i nostri giudizi validi utilizzando la nostra semantica.

Prosa creativa.

Devi dimostrare, se possibile, che ogni fbf valida e' anche derivabile.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 18-10-2018, 08:00:27
Quote
Attendo risposta

Puoi terminare una lettera, sia essa in formato elettronico o cartaceo,
con "Cari saluti", "A presto", "Cordialita'", "saribbecamo" o in tanti altri modi, formali o colloquiali,
ma non con una esortazione cosi' categorica. Perche' rispondere e' cortesia, non obbligo. Non e' una cosa carina.

Grazie per la mail a nome anche dei tuoi colleghi, che spero si decideranno anche loro
ad interagire sul forum.
Son sicuro che con calma ora riuscirai a correggere la tua soluzione dell'esercizio.

Un caro saluto
FB


Title: Re:Esercizio sistemi formali
Post by: InfernoMentale on 18-10-2018, 09:41:38
Buongiorno Professore mi scusi non era in alcun modo mia Intenzione essere scortese me ne dispiaccio in ogni caso proverò a Correggere visto che non c'ho azzeccato niente ho usato per la Derivabilita la Definizione 2.5 del Testo di Martini cercherò qualche Esempio in merito. In ogni caso Grazie a lei per la risposta se beccamo alla prossima Lezione prof :-OK

-Distinti Saluti.

P. S. Se posso chiedere cosa Intende per Prosa Creativa?  :"-(


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 18-10-2018, 09:45:34
Quote
P. S. Se posso chiedere cosa Intende per Prosa Creativa?

Frasi prive di senso in un italiano approssimativo....  .smile

Salutoni
FB


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 19-10-2018, 09:48:14
Sono in attesa di una soluzione dell'esercizio...



Title: Re:Esercizio sistemi formali
Post by: Nirìa on 21-10-2018, 11:44:57
Provo a rispondere così:
CORRETTEZZA
Numbers secondo questa semantica è corretto perché:
-- l'unico assioma di cui dispone è valido (dato che 2 è naturale)
-- entrambe le Regole hanno premesse e conclusioni valide (perché se x è naturale il successore lo sarà; se il successore di 0 è naturale, 0 è naturale).
Quindi in poche parole tutti i possibili teoremi saranno validi.
COMPLETEZZA
Numbers è incompleto perché esistono fbf valide ma non derivabili come ad esempio s(0)iN, che tra l'altro, facendo parte della premessa della regola pluto, rende la regola inutilizzabile a meno che non si ponga come ipotesi la sua stessa premessa.
DERIVABILITÀ DI PLUTO
La regola pluto non è derivabile dato che ponendo come ipotesi la premessa s(0)iN non ho modo di arrivare alla sua conclusione 0iN senza utilizzare pluto.
AMMISSIBILITÀ DI PLUTO
La regola pluto non è ammissibile perché il suo utilizzo incrementa le possibili fbf derivabili.

N. B.
(su quest'ultimo punto sono particolarmente incerto, sia perché questa conclusione mi sembra un controsenso con ciò che ho detto per giustificare l'incompletezza di Numbers, sia perché non ci ha ancora spiegato la condizione di ammissibilità, perciò mi baso solo sul libro)

Grazie per l'esercizio!!


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 21-10-2018, 15:39:09
Quote
-- entrambe le Regole hanno premesse e conclusioni valide (perché se x è naturale il successore lo sarà; se il successore di 0 è naturale, 0 è naturale).

Detto cosi' va bene solo per la seconda regola.
Per la prima, occorre dire (e dimostrare) che se la premessa della regola e' valida
allora la conclusione e' valida.

In realta' da questo fatto e dalla validita' degli assiomi discende certamente la correttezza,
ma non e' una cosa veramente banale.
Occorre dimostrarlo per induzione sulla lunghezza della derivazione.
Se me lo ricordate, lo facciamo in aula.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 21-10-2018, 15:40:32
Quote
COMPLETEZZA
Numbers è incompleto perché esistono fbf valide ma non derivabili come ad esempio s(0)iN, che tra l'altro, facendo parte della premessa della regola pluto, rende la regola inutilizzabile a meno che non si ponga come ipotesi la sua stessa premessa.

E' vero, Numbers non e' completo.
Ma anche se e' abbastanza ovvio che s(0)iN non e' derivabile,
occorre farlo vedere in modo piu' preciso.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 21-10-2018, 15:41:45
Quote
DERIVABILITÀ DI PLUTO
La regola pluto non è derivabile dato che ponendo come ipotesi la premessa s(0)iN non ho modo di arrivare alla sua conclusione 0iN senza utilizzare pluto.

Perche'?
Hai ragione, ma hai detto una cosa senza neanche cercare di giustificarla in modo preciso.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 21-10-2018, 15:43:07
Quote
AMMISSIBILITÀ DI PLUTO
La regola pluto non è ammissibile perché il suo utilizzo incrementa le possibili fbf derivabili.

Cio' che affermi e' falso.
Pensaci, e fammi sapere.


Title: Re:Esercizio sistemi formali
Post by: Nirìa on 21-10-2018, 15:58:07
Grazie della risposta.
Per quanto riguarda la dimostrazione per induzione glie lo ricorderò.

Invece per quanto riguarda le dimostrazioni mancanti (anche se probabilmente banali) non riesco a capire come dovrei dimostrare la non derivabilità di una fbf.

Riguardo il suo ultimo messaggio: Va bene, ci penserò meglio su.
L'unica cosa che credo sia vera è che se una regola essendo derivabile è anche ammissibile, non è detto che non essendo derivabile non debba nemmeno essere ammissibile giusto? Perché giustamente se così non fosse allora mi basterebbe dimostrare che sia o meno derivabile per dimostrarne anche l'ammissibilità.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 21-10-2018, 20:12:03
Quote
Invece per quanto riguarda le dimostrazioni mancanti (anche se probabilmente banali) non riesco a capire come dovrei dimostrare la non derivabilità di una fbf.

Pensaci.
Spero qualche tuo collega intervenga per cercare una risposta.

ALtrimenti, converra' farlo insieme a lezione.



Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 21-10-2018, 20:12:53
Quote
L'unica cosa che credo sia vera è che se una regola essendo derivabile è anche ammissibile, non è detto che non essendo derivabile non debba nemmeno essere ammissibile giusto? Perché giustamente se così non fosse allora mi basterebbe dimostrare che sia o meno derivabile per dimostrarne anche l'ammissibilità.

Giusto.

Lo vedremo meglio auando parleremo di regole ammissibili.

FB


Title: Re:Esercizio sistemi formali
Post by: SeminaraLuigi on 23-10-2018, 15:54:24
- Correttezza:
Il sistema formale preso in considerazione e' corretto rispetto alla semantica stabilita perche' il suo unico assioma e' valido e le premesse delle regole di inferenza sono giudizi validi e quindi anche le conclusioni sono valide.  Dimostriamo che l'assioma Ax e' valido:

Ax = { s(s(0))iN }  quindi possiamo affermare che il successivo del successivo di 0 e' 2 quindi un numero appartenente a N, che e' un valore valido secondo la semantica stabilita.

Dimostriamo la validita' delle due regole di inferenza:

R = {pippo, pluto} dove

                  xiN
   (pippo) ----------
                 s(x)iN
 
Abbiamo letto tra le risposte che bisogna verificare la regola pluto utilizzando il principio di induzione ma non abbiamo capito come applicarlo.


                 s(0)iN
   (pluto) -------------
                   0iN

Per quanto riguarda la regola pluto sappiamo che il successivo di 0 e' un numero appartenente ad N e lo e' anche 0, quindi sia la premessa che la regola sono due giudizi validi.

-Completezza:
Il sistema formale proposto non e' completo rispetto alla semantica stabilita, perche' alcune formule valide come S(0)iN non possono mai essere derivate, infatti se volessimo dimostrare S(0)iN questo non sarebbe possibile perche' dovrebbe esistere una dimostrazione che abbia come conclusione S(0)iN.

Dimostriamo che preso un qualunque insieme Gamma di fbf  Gamma|/- S(0)iN

Esempio:

1. S(S(0))iN Ax
2. S(S(S(0)))iN pippo(1)

Se continuassimo ad applicare la regola pippo dalle sue stesse conclusioni, non riusciremo mai a dimostrare S(0)iN.


-Derivabilita' ed ammissibilita' di pluto:
Per definizione sappiamo che pluto e' derivabile se S(0)iN |-- 0iN cioe' deve esistere una dimostrazione che utilizzando come ipotesi la premessa della regola abbia come conclusione 0iN.
In questo caso 0iN non e' un assioma, ne una ipotesi, ne puo' essere la conclusione della regola pippo. Quindi la regola pluto non e' derivabile.
Pur non essendo derivabile la regola pluto e' ammissibile. Possiamo dimostrarlo attraverso la definizione di ammissibilita', ovvero se |--SU{pluto} alpha allora |--S alpha, cioè se esiste una dimostrazione di un teorema in SU{pluto} allora esiste una dimostrazione in D di quel teorema. Questo nel nostro caso e' vero, poiche' la regola pluto non puo' essere mai applicata, una dimostrazione di un teorema in SU{pluto} sara' uguale alla dimostrazione dello steso teorema in S.

-Conclusione raggiunta da Corrado e Luigi

-Cordiali saluti
 


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 23-10-2018, 17:24:18
Quote
Abbiamo letto tra le risposte che bisogna verificare la regola pluto utilizzando il principio di induzione ma non abbiamo capito come applicarlo.

No, il principio di induzione si utilizza per dimostrare la correttezza a partire
dalle proprieta' che hai mostrato tu.


Title: Re:Esercizio sistemi formali
Post by: Franco Barbanera on 23-10-2018, 17:26:30
Bravi Corrado e Luigi!
Ci sono alcune piccole imperfezioni nei vostri ragionamenti, ma complessivamente
e' un ottimo lavoro.