Prolog/Introduzione

Poiché il prolog è pesantemente basato sulla logica formale, potrebbe essere utile fare prima qualche esperienza prima di iniziare ad impararlo. Prenderci la mano può aiutare a comprendere la parte strettamente teorica. La prima parte di questo testo deve aiutare a comprendere i fondamenti della logica allo scopo di capire meglio come funziona il prolog. Saranno discussi due aspetti della logica: la logica proposizionale e la logica del primo ordine.

Logica Proposizionale

Nella logica proposizionale esistono due fondamentali elementi di base , termini e connettivi. I termini sono rappresentati da lettere (di solito maiuscole), e rappresentano i valori vero e falso, quindi un termine può essere vero o falso, benché non sia sempre chiaro cosa rappresenti veramente. In questo senso essi sono come le variabili in matematica perché rappresentano un valore.

I connettivi, come suggerisce la parola, connettono due termini. Il risultato di questa connessione prende il valore di vero o falso basandosi proprio sul valore dei due termini. Consideriamo per esempio il connettivo AND. Questo connettivo può mettere in relazione i termini A e B per creare la proposizione "A AND B". La proposizione "A AND B" è vera quando sono vere A e B. Se una o entrambe sono false, la proposizione è falsa. I connettivi sono solitamente rappresentati da simboli piuttosto che da parole. La seguente tabella mostra i connettivi più comunemente usati, il loro significato ed i simboli più correntemente usati per rappresentarli.

Nome	Uso	Significato	Simbolo
congiunzione	$A\leq B$	vera quando entrambe sono vere	$\leq \quad ,$
disgiunzione	$A\lor B$	vera quando una o entrambe sono vere	$\lor \quad ;$
or esclusivo	$A\oplus B$	vera quando una e solo una è vera	$\oplus \quad {\underline {\lor }}\quad$
negazione	$\lnot A$	vera quando una e falsa e viceversa	$\sim \quad \lnot \quad {\bar {q}}$
implicazione	$A\rightarrow B$	vera quando A è vera e B è vera; vera quando A è falsa	$\rightarrow \quad \Rightarrow \quad \models$
uguaglianza	$A\leftrightarrow B$	vera se entrambe false o entrambe vere	$\leftrightarrow \quad \Leftrightarrow \quad =$

Attenti al significato di implicazione, potrebbe non essere così intuitivo. A => B significa che se A è vera allora è vera anche B, in caso contrario B può essere sia vera che falsa.

Dal momento che ogni termine può prendere alternativamente solo due valori, tutte le possibilità possono essere chiaramente enumerate attraverso una tabella della verita':

A	B	A e B	A or B	A xor B	not A	A => B	A<=>B
f	f	f	f	f	v	v	v
f	v	f	v	v	v	v	f
v	f	f	v	v	f	f	f
v	v	v	v	f	f	v	v

Il passo successivo consiste nel connettere le due preposizioni, usando i connettivi, per avere proposizioni piu' complesse, come (A e B) => (B <=> A) o ((A or C) or (A or D)). Nell' ultima proposizione le parentesi vengono omesse dal momento che A or (B or C) è lo stesso che (A or B) or C. Comunque ,nel dubbio, è meglio usare le parentesi per maggior chiarezza.

Si possono analizzare proposizioni complesse come questa:

A	B	A e B	A or B	(A e B) or (A e C)
f	f	f	f	f
f	v	f	v	v
v	f	f	v	v
v	v	v	v	v

Ora possiamo dividere le proposizioni in tre gruppi: valide, insoddisfacenti e soddisfacenti. Le proposizioni valide o tautologie sono sempre vere, non importa che valori prednono. Esempi di proposizioni valide sono A or (not A), A => A or (A => B) or ( A e (not B)). Le Proposizioni insoddisfacenti sono sempre false, eg: A e (not A) or (A <=> B) e (B <=> not(A)). Tutte le altre proposizioni sono soddisfacenti, cioè possono essere sia vere che false, secondo i valori dei loro termini.

Significato e Intenzione

Nel linguaggio logico è importantissimo capire che le proposizioni possono essere usate e combinate nei modi piu' disparati. $A\wedge B$, per esempio, non implica alcun significato. È soltanto un modo formale di creare proposizioni logiche. Si può affermare che $A\wedge B$ è vera, dandole un significato (A e B sono entrambe vere), che può essere usato per derivare ulteriori verità se conosciamo meglio A e B. Si potrebbe chiedere se $A\wedge B$ è vera, e la risposta potrebbe essere basata su quanto si conosce riguardo A e B. In altre parole , una proposizione logica non significa nulla in sè se non viene riempita con qualcosa. Il lettore necessita di una conoscenza piu' approfondita allo scopo di fare qualcosa di ulteriore. Un costrutto logico comune è la conoscenza di base, una collezione di sentenze che sono assunte come sempre vere (in matematica sono chiamate anche postulati), ed una singola proposizione posta in forma di domanda. Occorre capire quale affemazione sia vera, data la conoscenza di base. Consideriamo per esempio la seguente conoscenza di base:

$A\wedge B$
$~B$

Con la domanda

$A$

In questo caso occorre capire se A è vera , data la conoscenza di base. È chiaro che la questione sia sicuramente vera, dal momento che $A\wedge B$ è vera, e B pure.Questa costruzione conoscenza di base/domanda è il modo in cui lavora il prolog. Puoi scrivere una conoscenza di base (il tuo programma) e chiedere una questione a prolog.A paragone dei linguaggi di programmazione , la conoscenza di base è il tuo programma , la domanda è il tuo input ed il prolog svolge il programma risolvendo la tua domanda.

Logica del Primo Ordine

La logica del primo ordine (conosciuta anche come logica dei predicati) è simile alla logica proposizionale, solo che usa predicati, variabili e oggetti. Nella logica proposizionale, le proposizioni atomiche sono i piu' piccoli elementi che possono assumere i valori vero/falso e i termini sono simboli rappresentati da lettere. Nella logica del primo ordine le proposizioni atomiche sono predicati. I predicati hanno un nome (che inizia con la lettera maiuscola) seguito da parecchie variabili (che iniziano con la lettera minuscola). Qui sotto abbiamo alcuni esempi di predicati:

• Predicato(variabile1, variabile2)
• FratelloDi(sorella, fratello)
• MadreDi(madre, figlio)
• HaRuote(cosa)

Queste variabili possono essere istanziate con oggetti. Gli oggetti sono elementi rappresentati da parole che iniziano con la lettera maiuscola. Per esempio, nel predicato $HaRuote(cosa)$ la variabile cosa pu' essere istnziata con gli oggetti Auto, Bici, o Banana. Basato sull'istanziazione delle variabili, il predicato ($HaRuote(Car)$ è vero se $HaRuote(Banana)$ è falso). Questi nomi vengono usati solo per migliorare la leggibilità, per i nosti scopi non significano nulla e possono essere sostituiti. $HaRuote(Banana)$ non è funzionalmente differente da $X(A)$. Tuttavia $HaRuote(Banana)$vera o falsa ha bisogno di essere definita in qualche modo formale (come in una conoscenza di base).

Questi predicati possono essere riuniti in proposizioni, proprio come i termini della logica proposizionale, usando connettivi (i connettivi sono gli stessi della logica proposizionale). Di solito esiste una collezione di proposizioni assunte come vere, per crare una definizione logica di predicati.Una simile collezione di predicati veri o postulati è detta conoscenza di base o knowledgebase. Una conoscenza di base può contenere le seguenti proposizioni:

HaRuote(Auto)
MadreDi(Carlo, Elisabetta)

Dicendo che il predicato HaRuote è vero , il primo elemnto è una macchina e Elisabetta è la madre di Carlo. Per costruire questo tipo di proposizioni con variabili abbiamo bisogno di stabilire cosa vogliamo dire effettivamente quando usiamo quelle variabili. Se HaRuote(x) è vera, vogliamo dire che è valida qualsiasi istanza di x o che esiste almeno una istanza di x in cui HaRuote è vera ? Per questo motivo dobbiamo usare dei quantificatori o quantifiers, che hanno il compito di determinare la quantità di una variabile. Nella logica del primo ordine esistono due quantificatori, il quantificatore universale $\forall$ ed il quantificatore esistenziale $\exists$.Questi quantificatori vengono piazzati prima di una variabile allo scopodi capire cosa vogliono dire quelle variabili nella proposizione che segue il quantificatore . Per esempio , la frase $\forall xHaRuote(x)$ significa che per quansiasi possibile istanza di x, HaRuote(x) è vera, quindi che tutti i possibli oggetti di quella frase devono avere le ruote. La frase $\exists xHaRuote(x)$ significa che esiste almeno un oggetto x per il quale il predicato HaRuote(x) è vero, in parole povere che esiste almeno un oggetto con le ruote.Per capire meglio il significato e l'uso dei quantificatori possiamo utilizzare i seguenti esempi:

• Se x è un veicolo, allora x ha le route. (se x non è un veicolo, la proposizione non può dire nulla su x)

$\forall xIlVeicolo(x)\Rightarrow HaRuote(x)$

• Se x ha un bambino y e x è un uomo, x è il padre di y.

$\forall x,yHaUnBambino(x,y)\wedge Man(x)=>PadreDi(x,y)$

• Allora esite un oggetto che non ha le ruote ed è una macchina

$\exists xHaRuote(x)\wedge \sim Auto(x)$

• Tutte le madri hanno un figlio

$\forall xMadre(x)=>\exists yBambino(y)\wedge HaUnFiglio(x,y)$

Logica in Prolog

La logica usata in prolog è una versione della logica del primo ordine, con l'uso delle lettere maiuscole invertite (predicati e iniziano con la lettera minuscola, le variabili iniziano con una lettera maiuscola). Un programma in prolog consiste di una conoscenza di base, in inglese knowledge base, dove ogni proposizione è congiunta ad altri predicati e ad un predicato finale con una implicazione. Per esempio:

$\forall a,b,c,dPred1(a,b)\wedge Pred2(b,c)\wedge Pred3(c,d)\Rightarrow Pred4(a)$

Una proposizione come questa è chiamata Clausola di Horn. In prolog la proposizione somiglierebbe a questa:

pred4(A) :- pred1(A, B), pred2(B, C), pred3(C, D).

Nota: il segno di implicazione è al contrario, i commi sono usati per le congiunzioni, un periodo è usato per delimitare una proposizione e tutte le variabili sono universalmente quantificate.

Esercizi

(x) Scrivi una tabella della verità per le seguenti proposizioni in logica proposizionale.
a) $(A\wedge B)VC$
b) $A$
c) $A$
d) $A$
e) $A$

(x) Quanti connettivi possono mettere in relazione due termini? Perché?

(x) Trovare una formula per le seguenti tabelle della verità
a)
b)
c)
d)

(x) Le tabelle della verità sono un modo per provare se una formula proposizionale è vera .Si può fare la stessa cosa per la logica del primo ordine ? Spiega se si può fare e come.

(x) TRasforma le seguenti proposizioni usando la logica del primo ordine. Cerca di seguire da vicino la struttura logica delle seguenti proposizioni (usando oggetti per individui, variabili per gruppi di persone, connettivi per costruzioni logiche e predicati per il resto).
a) Tutti i bambini sno piccoli.
b) Alcuni bambini hanno le scarpe.
b) tutti i bambini maschi preferiscono le macchinine.
d) Tutti i bambini che hanno le scarpe, le indossano.
e) Tutti i bambini hanno una mamma.
f) Se una donna è mamma ha un bambino.
g) Nessun bambino ama le verdure troppo cotte.
h) A nessuna madre piace una insegnante che punisce il suo bambino.

(x) (avanzato)Le domande seguenti riguardano il simbolo =. Esso riguarda soltanto due variabili ed è vera quando i due oggetti rappresentano la stessa cosa ,in altre parole x = y è vera se x e y sono identici.
(a) Il simbolo = è una funzione predicato o connettiva? Why?
(b) Il simbolo = non dovrebbe essere confuso con il connettivo uguaglianza. In cosa differiscono?
(c) Riesci a pensare ad una proposizione in logica del primo ordine tale che, aggiunta ad una conoscenza di base (e quindi considerata sempre vera) fa la stessa cosa del simbolo = .
(d) Il quantificatore esistenziale $\exists x$ definisce che una proposizione è vera se eè vera almeno una possibile istanza di x. Riesci a pensare ad un modo di quantificare x in modo che una prposizione sia vera se è vera solo e soltanto per una istanza di x e nient'altro ? Sicuramente avrai bisogno del simbolo = .