Semantic Web Lezione 2

febbraio 27, 2008 alle 3:14 PM · Archiviato in Appunti, Web Semantico and tagged: algebra di boole, Appunti, Gaspari, logica, modus ponens, Web Semantico

Numero di studenti a lezione: 2

Vediamo oggi un esempio di formalismo per rappresentare la conoscenza secondo la logica proposizionale. Il primo passo è definire la sintassi del formalismo, ovvero un insieme di formule atomiche (potenzialmente infinito) in genere limitato all’interno di un certo contesto. Il formalismo per indicare gli elementi di questo insieme sarà A, B, C, …., Ai

Definiamo dei connettivi logici AND, OR, NOT, ALLORA (implicazione)

Formule ben formate (FBF):
se e sono FBF allora , , , sono FBF, formule ben formate.

La sintassi è legata al concetto di verità. Le asserzioni di base da cui partire sono in generale date come vere

 

La semantica

Un assegnamento è la specifica dei valori di verità per tutte le formule atomiche.

A = (Tutti gli uomini sono mortali) è vero (oppure valore 1)

B = (Socrate è un uomo) è vero (oppure valore 1)

Indichiamo con 1 il valore di verità, indichiamo con 0 la non-verità (logica binaria).

Altro esempio: sia A=1, B=0, C=1.

Dati i valori di verità, allora tutti i valori di verità prodotti dalle inferenze successive risultano automaticamente determinati. Cioè, se ho una regola che mostra come la verità si propaga mediante la connessione, ad esempio, di due formule atomiche, allora assegnando i valori iniziali di verità, essendo l’applicazione delle inferenze un puro processo meccanico, allora i risultati sono automaticamente determinati senza incertezze.

AND
A	B
falsa	falsa	vera
falsa	vera	falsa
vera	falsa	falsa
vera	vera	falsa

 

OR
A	B
vera	falsa	vera
vera	vera	vera
falsa	falsa	falsa
falsa	vera	vera

IMPLICAZIONE
A	B
falsa	falsa	vera
falsa	vera	vera
vera	falsa	falsa
vera	vera	vera

 

 

Posso generare delle formule che mi portino ad avere tutte le possibili combinazioni di zeri e uno? si… ad esempio per ottenere 1000 potrei avere

Alcune definizioni:

Def: Un modello per una formula T è un assegnamento che rende vera F.

Def: una FBF (formula ben formata) F si dice soddisfacibile se esiste un assegnamento che è un modello per F

E’ sempre possibile fare formule del genere? è sempre falsa.

Def: una FBF F è detta insoddisfacibile se non esiste un modello per F.

Def: una FBF F è valida se tutti gli assegnamenti sono modelli per F (tautologia). Le tautologie sono poco interessanti poiché qualcosa che è sempre e comunque vero non aiuta, non aggiunge molta conoscenza.

 

Def: due FBF e sono equivalenti se hanno stessi modelli (o se hanno la stessa tabella di verità).

Alcuni esempi:

Leggi di De Morgan

 

e ancora…

 

Le leggi di De Morgan mostrano come non tutti i connettori logici siano necessari, ma utilizzando solo OR e NOT riesco a rappresentare tutte le formule possibili.

Concetto della conseguenza logica: voglio sapere quali sono le formule ben formate che implichino la verità, che soddisfano la seguente relazione?

Una formula G (generica) è conseguenza logica di un insieme di formule F (formule in AND fra di loro) se per ogni assegnamento che è un modello per F allora questo è un modello anche per G.

Se per tutte le righe della tabelle di verità in cui F è vera anche G è vera, cioè ha lo stesso risultato, allora G è conseguenza logica di F.

Esempio.

Sia F una specifica di formule costituita da:

Come verifico se G è conseguenza logica di F?

Posso costruire tutte le righe della tabella di verità e le confronto con quelle di G.

A	B			B
0	0	1	0	0
0	1	1	0	1
1	0	0	0	0
1	1	1	1	1

Sia G=B. B è conseguenza logica di F.

L’algoritmo che verifica la conseguenza logica ha complessità esponenziale.

 

Come si fanno le deduzioni?

Stabilisco un insieme di regole sulla base delle quali fare le deduzioni (regole di inferenza).

 

Se nel mio insieme di formule ho formule che hanno questa struttura, ad esempio al posto di A e B posso avere anche altre formule più complesse, se ho la stessa struttura del modus ponens, allora posso aggiungere al mio insieme di conoscenza anche B, cioè B è vero. Questa deduzione deriva dalla regola di inferenza modus ponens.

Questo metodo deduttivo è corretto? E’ completo? Genero qualcosa che sia vero? Devo verificare che la regola di inferenza logica sia corretta. Dato che B è conseguenza logica diallora B è vera.

Non è possibile trovare la completezza di ….. (non ho capito)

Deduzione naturale

Creare un insieme di regole di inferenza che ….. ecc…

; ; ….

Commenti