Pages: [1] 2 3   Go Down
Print
Author Topic: Esercizi lezione I A-L e M-Z  (Read 1311 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« 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}?
« Last Edit: 15-10-2018, 22:27:52 by Franco Barbanera » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



WWW
« Reply #1 on: 03-10-2018, 15:26:29 »

Dimostrare che in un sistema formale
un teorema ha infinite prove (deduzioni)
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



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

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!  )
E poi ora non ho corretto un errore grammaticale...
Logged
maujeri
Matricola
*
Offline Offline

Posts: 2



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

Posts: 3.027



WWW
« Reply #4 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 
« Last Edit: 28-10-2018, 18:59:02 by Franco Barbanera » Logged
Muro
Matricola
*
Offline Offline

Posts: 7


« Reply #5 on: 28-10-2018, 22:24:55 »

Devo riformulare quel che avevo scritto
« Last Edit: 29-10-2018, 12:25:04 by Muro » Logged
maujeri
Matricola
*
Offline Offline

Posts: 2



« Reply #6 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 

Ma é proprio sbagliato utilizzare una dimostrazione formale?
Potrebbe aiutarmi a correggere la mia dimostrazione? Grazie mille e buona serata   
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.027



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

Posts: 7


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

Posts: 3.027



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

Posts: 3.027



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

Posts: 3.027



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

Posts: 3.027



WWW
« Reply #12 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,

Logged
why?
Matricola
*
Offline Offline

Posts: 2



« Reply #13 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
Logged
why?
Matricola
*
Offline Offline

Posts: 2



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