Forum Informatica Unict

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



Title: Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 03-10-2018, 15:14:30
La regola di inferenza "pippo" dell'esempio di sistema formale fatta oggi a lezione l'abbiamo rappresentata
informalmente nel seguente modo:

                                          x in N
                       pippo   ---------------------
                                      s(x) in N

dove con x intendiamo qualsiasi stringa sull'alfabeto del nostro sistema formale, cioe' {0,s,(,),in,N}}

Questa e' una rappresentazione informale della regola pippo.
Fornirne una matematicamente piu' precisa.

(ovviamente poi e' meglio usare quella informale, che si capisce meglio....)

--------------------------------------
Dimostrare le due osservazioni alla fine di pagina 6 del Martini  (una di queste e' l'esercizio 51 tra quelli di Logica)
--------------------------------------
Prendere il sistema formale dell'esercizio 35.3 tra quelli di logica e mostrare che e' consistente.
Quali sono i teoremi di D?
Qual e' l'insieme delle conseguenze dell'insieme di ipotesi {a, aa}?


Title: Re:Esercizi su lezione 3 Ott M-Z
Post by: Franco Barbanera on 03-10-2018, 15:26:29
Dimostrare che in un sistema formale
un teorema ha infinite prove (deduzioni)


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 28-10-2018, 18:26:18
Quote
barcollare nel buio
Nel buio si "brancola" non si "barcolla" (anche se in realta' nulla ce lo vieterebbe....)  .smile

P.S. Mi ha moglie mi ha fatto notare che ci sono studi che dimostrano che chi corregge
sempre gli errori grammaticali degli altri e' una persona sgradevole.
(Ora avete anche una conferma dalla scienza!  .rido)
E poi ora non ho corretto un errore grammaticale...


Title: Re:Esercizi lezione I A-L e M-Z
Post by: maujeri on 28-10-2018, 18:27:23
Buona sera professore, ho provato a svolgere l'esercizio di dimostrare la seconda osservazione a pagina 6 del Martini, anche se non sono sicuro sia giusto.
Ho considerato il seguente sistema formale A:
S = {a,z,k,s,≠,∈,=}
W= {P=Q | P,Q ∈ Γ,Γ'} tale che:
     1.  a ∈ Γ,Γ'  ,  z ∈ Γ,Γ'  ,  k ∈ Γ,Γ'  ,  s ∈ Γ,Γ'
     2.  se P,Q ∈ Γ,Γ' allora (PQ) ∈ Γ,Γ'
     3. nient'altro è un termine
R = {incons} dove
                 Γ≠ Γ'
(incons) ----------
                 PQ

La mia deduzione è la seguente
1. Γ≠ Γ' (ipotesi)
2. PQ (incons)
2.Con(Γ) = {PQ ∈ W | Γ |--PQ} = W
3.Con(Γ') = {PQ ∈ W | Γ' |--PQ} = W
4.Con(Γ) = Con(Γ') (transitività 2. 3.) .


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 28-10-2018, 18:56:08
Dobbiamo fare attenzione. Il termine "dimostrazione" lo utilizziamo in due modi differenti.
Lo usiamo sia nel senso di dimostrazione formale, deduzione in un sistema formale,
sia nel senso di dimostrazione matematica informale.
In questo caso, quando si chiede di dimostrare l'osservazione
non intendiamo dimostrazione formale, ma una dimostrazione informale, come quelle
che fate a matematica discreta.

Ovviamente confondendo il senso di "dimostrazione" nell'esercizio, uno finisce necessariamente
per incartarsi in ragionamenti astrusi.
Il risultato e' terrificante, ma lo sforzo e' lodevole  .applausi


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 28-10-2018, 22:24:55
Devo riformulare quel che avevo scritto


Title: Re:Esercizi lezione I A-L e M-Z
Post by: maujeri on 29-10-2018, 01:44:33
Dobbiamo fare attenzione. Il termine "dimostrazione" lo utilizziamo in due modi differenti.
Lo usiamo sia nel senso di dimostrazione formale, deduzione in un sistema formale,
sia nel senso di dimostrazione matematica informale.
In questo caso, quando si chiede di dimostrare l'osservazione
non intendiamo dimostrazione formale, ma una dimostrazione informale, come quelle
che fate a matematica discreta.

Ovviamente confondendo il senso di "dimostrazione" nell'esercizio, uno finisce necessariamente
per incartarsi in ragionamenti astrusi.
Il risultato e' terrificante, ma lo sforzo e' lodevole  .applausi

Ma é proprio sbagliato utilizzare una dimostrazione formale?
Potrebbe aiutarmi a correggere la mia dimostrazione? Grazie mille e buona serata   .camberman


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 29-10-2018, 21:56:40
Dimostrare le due osservazioni alla fine di pagina 6 del Martini

Possiamo prendere il sistema formale Numbers definito in
http://forum.informatica.unict.it/index.php?topic=24779.0

E poi prendere
Gamma = {0iN}
e
Gamma' = {0iN, s(0)iN}

Gamma e Gamma' sono diversi, ma si puo' far vedere
che Con(Gamma) = Con(Gamma')

Esercizio: farlo vedere.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 30-10-2018, 22:29:12
Dimostrare le due osservazioni alla fine di pagina 6 del Martini

Possiamo prendere il sistema formale Numbers definito in
http://forum.informatica.unict.it/index.php?topic=24779.0

E poi prendere
Gamma = {0iN}
e
Gamma' = {0iN, s(0)iN}

Gamma e Gamma' sono diversi, ma si puo' far vedere
che Con(Gamma) = Con(Gamma')

Esercizio: farlo vedere.
Buona sera professore.

Questo è un tentativo di rispondere almeno alla prima osservazione, nella speranza di non aver fatto altre scempiaggini.

Una teoria pura è una teoria dal momento che da definizione questa è l’insieme di teoremi di un sistema formale e che per mezzo dell’uso di essi non possiamo fare altre che ottenere altri teoremi.
1.   S(S(0))iN        Ax
2.   S(S(S(0)))iN   Pippo(1)

Dunque, tutto quel che potremo ottenere spingendoci oltre non saranno altro che teoremi derivanti da altri teoremi per mezzo delle regole d’inferenza.
Ciò dovrebbe essere dimostrato per induzione prendendo fi come assioma, n il numero di passaggi deduttivi (facenti uso delle regola d'inferenza,  considerando che ad un certo punto saremo comunque obbligati ad usare la regola pippo non potendo più "decrementare" con la regola pluto), m la lunghezza della deduzione, k l’indice minore di m di un passaggio deduttivo che riporta sempre un teorema. (Penso d’aver capito la logica dietro la dimostrazione per induzione, ma non ho capito bene come applicarla) 

 Fi (n0) per ogni m     per ogni k<m Fi(k) --> Fi(m)              Dunque per ogni Fi(n) avremo un teorema
----------------------------------------------------------   
Per ogni n>n0 Fi(n)


Invece per quanto riguarda la seconda osservazione (che devo ancora cercare di dimostrare)

con(gamma)=con(gamma’) si ha quando i due insiemi di ipotesi, gamma != gamma’, sono inconsistenti, in quanto: con(gamma)=W, con(gamma’)=W e dunque con(gamma)=con(gamma’).
Prese due fbf, una di gamma e una di gamma', dovremmo comunque poter derivare tutte le fbf del sistema.


Spero d’aver compreso l’esercizio e l'effettivo significato di dimostrazione questa volta.

Ancora buona serata professore.

P.S. non so per quale dubbia associazione di idee, quando si parla di buio io confonda sempre barcollare con brancolare, forse merito delle esperienze passate. Alla fine, come ha detto lei, nessuno ci impedisce di fare entrambi  :[Emoticon] Asd:


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 31-10-2018, 09:51:55
Quote
Una teoria pura è una teoria dal momento che da definizione questa è l’insieme di teoremi di un sistema formale e che per mezzo dell’uso di essi non possiamo fare altre che ottenere altri teoremi.

Questo e' vero, ma va detto in modo piu' preciso.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 31-10-2018, 09:55:23
Quote
1.   S(S(0))iN        Ax
2.   S(S(S(0)))iN   Pippo(1)

Non e' chiaro perche'scrivi questa cosa.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 31-10-2018, 09:56:45
Quote
Dunque, tutto quel che potremo ottenere spingendoci oltre non saranno altro che teoremi derivanti da altri teoremi per mezzo delle regole d’inferenza.

OK, ma vogliamo essere molto precisi, e mi devi dire perche'.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 31-10-2018, 09:58:26
Quote
con(gamma)=con(gamma’) si ha quando i due insiemi di ipotesi, gamma != gamma’, sono inconsistenti, in quanto: con(gamma)=W, con(gamma’)=W e dunque con(gamma)=con(gamma’).
Prese due fbf, una di gamma e una di gamma', dovremmo comunque poter derivare tutte le fbf del sistema.

Rileggi con calma. Confronta le nozioni che usi con la loro definizione nel testo,
e cerca di capire il senso di cio' che hai scritto.
Vedrai che hai scritto cose prive di senso,



Title: Re:Esercizi lezione I A-L e M-Z
Post by: why? on 03-11-2018, 11:36:57
La regola di inferenza "pippo" dell'esempio di sistema formale fatta oggi a lezione l'abbiamo rappresentata
informalmente nel seguente modo:

                                          x in N
                       pippo   ---------------------
                                      s(x) in N

dove con x intendiamo qualsiasi stringa sull'alfabeto del nostro sistema formale, cioe' {0,s,(,),in,N}}

Questa e' una rappresentazione informale della regola pippo.
Fornirne una matematicamente piu' precisa.

(ovviamente poi e' meglio usare quella informale, che si capisce meglio....)

Buongiorno professore,
proverò a rispondere al primo esercizio.

Dato il sistema formale D con S={0,s,(,),in,N}

1. x in N
2. s(x) in N         pippo (1)

Sappiamo che è possibile, nella relazione pippo, sostituire la ''x'' con simboli dell'insieme S ed è possibile applicare questa relazione ricorsivamente. Difatti, è possibile dimostrare quanto detto con un'induzione.

 φ(x0)          ∀(φ(x)  --->   φ(x+1))
________________________________
                 ∀x.φ(x)

Dove con ''x0'' intendo 1. e con ''x+1'' intendo 2.

Mi scusi per eventuali pasticci  :boh


Title: Re:Esercizi lezione I A-L e M-Z
Post by: why? on 03-11-2018, 12:41:40
Prendere il sistema formale dell'esercizio 35.3 tra quelli di logica e mostrare che e' consistente.
Quali sono i teoremi di D?
Qual e' l'insieme delle conseguenze dell'insieme di ipotesi {a, aa}?

Il sistema formale dell'esercizio è consistente perché non è possibile derivare le fbf ''a'', ''aa'' e tutte quelle con il solo simbolo ''b'' nella stringa.
Qualunque fbf derivata da D senza utilizzare ipotesi sarà un teorema.
L'insieme delle conseguenze dell'insieme di ipotesi {a, aa}= {aaa, aaaa} perché è possibile derivare ''a'' e ''aa'' solo tramite la regola di inferenza
               w
  (R)    ------------
              waa



...credo .penso


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 12:13:20
Quote
Buongiorno professore,
proverò a rispondere al primo esercizio.

Hai scritto cose prive di senso.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 12:14:30
Quote
Il sistema formale dell'esercizio è consistente perché non è possibile derivare le fbf ''a'', ''aa'' e tutte quelle con il solo simbolo ''b'' nella stringa.

Dovresti fornire una giustificazione di questo che affermi.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 12:15:16
Quote
Qualunque fbf derivata da D senza utilizzare ipotesi sarà un teorema.

Ovvio, ma in questo caso  quali sono queste fbf??


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 12:17:58
Quote
L'insieme delle conseguenze dell'insieme di ipotesi {a, aa}= {aaa, aaaa} perché è possibile derivare ''a'' e ''aa'' solo tramite la regola di inferenza
               w
  (R)    ------------
              waa


Le conseguenze sono un insieme ben piu' grande di {aaa, aaaa}.



Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 04-11-2018, 16:46:19
Quote
Una teoria pura è una teoria dal momento che da definizione questa è l’insieme di teoremi di un sistema formale e che per mezzo dell’uso di essi non possiamo fare altre che ottenere altri teoremi.

Questo e' vero, ma va detto in modo piu' preciso.

Buongiorno professore, mi scusi se la mia risposta si è fatta attendere.

Provo a riformulare.
Una teoria pura è l’insieme di Ax chiuso rispetto alla relazione |-D , ovvero se da |-D alpha, abbiamo che alpha appartiene a Ax, cioè se in un sistema formale D riusciamo a derivare una fbf senza l’uso di ipotesi, ciò ci garantisce la costante veridicità della fbf che abbiamo derivato.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 04-11-2018, 16:48:47
Quote
Dunque, tutto quel che potremo ottenere spingendoci oltre non saranno altro che teoremi derivanti da altri teoremi per mezzo delle regole d’inferenza.

OK, ma vogliamo essere molto precisi, e mi devi dire perche'.

Non potremo ottenere altro all'infuori di teoremi in quanto non facciamo uso d’ipotesi e dunque, per definizione, abbiamo con(insieme vuoto)=con(Ax) (con entrambe nel sistema formale D); con(insieme vuoto) è l’insieme delle fbf derivabili senza l’uso d’ipotesi, il quale coincide all'insieme delle fbf derivabili col solo uso degli assiomi.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 04-11-2018, 16:51:19
Quote
1.   S(S(0))iN        Ax
2.   S(S(S(0)))iN   Pippo(1)

Non e' chiaro perche'scrivi questa cosa.

Volevo far vedere velocemente che non essendoci l’uso di ipotesi avremo potuto derivare solo teoremi da una successione n di applicazioni di regole d’inferenza.

Tentativo non riuscito considerando che anche a me, che lo sto rileggendo, non dice molto.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Marcus on 04-11-2018, 20:40:33
Buonasera professore.
Per quanto riguarda la prima delle due osservazioni, ovvero "una teoria pura è una teoria", è valido il ragionamento che segue?

Teoria: insieme di fbf chiuso rispetto alla derivazione <=> Con(Γ) = Γ
Teoria pura: insieme dei teoremi <=> Con(∅) = Con(Ax)

Con(∅) = {α ∈ W | ⊢D α }  quindi α è un assioma o una regola di inferenza
Con(Ax) = {α ∈ W | Ax ⊢D α } ma per poter essere derivata, α deve per forza essere un assioma o una regola di inferenza.

Ne consegue che Con(∅) = Con(Ax) è chiuso rispetto alla derivazione perchè non posso derivare altro che non sia un assioma o una regola di inferenza. Quindi per definizione di teoria, una teoria pura è una teoria.


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 21:18:10
Quote
ciò ci garantisce la costante veridicità della fbf che abbiamo derivato.

EEEHH?????


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 21:20:33
Quote
Con(∅) = {α ∈ W | ⊢D α }  quindi α è un assioma o una regola di inferenza

Stai scherzando, vero?


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 04-11-2018, 22:21:24
 Per Marcus:

Quand'e' che, dato un sistema D, possiamo scrivere  ⊢D α  ?


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Marcus on 05-11-2018, 00:59:37
Per Marcus:

Quand'e' che, dato un sistema D, possiamo scrivere  ⊢D α  ?

Quando esiste una sequenza di fbf, partendo da un insieme di ipotesi vuoto, la cui conclusione è α
Giusto?


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 05-11-2018, 21:03:44
Quote
Quando esiste una sequenza di fbf

E quali caratteristiche deve avere tale sequenza?


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 07-11-2018, 16:43:49
Quote
ciò ci garantisce la costante veridicità della fbf che abbiamo derivato.

EEEHH?????

Forse ricordo male una delle prime lezione seguite.
Un ipotesi è qualcosa che diamo per vera nella derivazione ma che non abbiamo effettivamente verificato, sono fuori strada?


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 08-11-2018, 10:52:03
Quote
Un ipotesi è qualcosa che diamo per vera nella derivazione ma che non abbiamo effettivamente verificato, sono fuori strada?

Nella definitione di derivazione hai mai letto la parola "vero"?
Oppure la parola "verificato"?



Title: Re:Esercizi lezione I A-L e M-Z
Post by: Muro on 10-11-2018, 12:28:53
Quote
Un ipotesi è qualcosa che diamo per vera nella derivazione ma che non abbiamo effettivamente verificato, sono fuori strada?

Nella definitione di derivazione hai mai letto la parola "vero"?
Oppure la parola "verificato"?


Nel Martini no, era il ricordo di una delle prime spiegazioni. Non vorrei aver interpretato male la spiegazione quella volta.   


Title: Re:Esercizi lezione I A-L e M-Z
Post by: Franco Barbanera on 10-11-2018, 12:41:25
il ricordo??!?

E il Martini lo abbiamo studiato?