Pages: 1 [2]   Go Down
Print
Author Topic: Esercizio sistemi formali  (Read 519 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Nirìa
Matricola
*
Offline Offline

Posts: 11


« Reply #15 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à.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #16 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.

Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #17 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
Logged
SeminaraLuigi
Matricola
*
Offline Offline

Posts: 2


« Reply #18 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
 
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #19 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.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #20 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.
Logged
Pages: 1 [2]   Go Up
Print
Jump to: