# TP noté Prolog (Logique)

## Exercice 2 - Requête et base de connaissances

### 2.1 Introduction

Cet exercice ne possède pas de fichier indépendant où est écrit le code, car il ne fallait pas en écrire.
Par contre, nous avons expliqué toutes les réponses aux questions.

#### 1)

On remarque, à la ligne 8, le fait suivant:

boit(vincent, vodka).

Ce qui signifie que "vincent" boit de la "vodka". Donc, d'après ce qui est écrit dans le fichier, il est vrai que vincent boit de la vodka.

#### 2)
Lorsque l'on tape boit(vincent, vodka), on obtient la sortie suivante :

?- boit(vincent, vodka).
true .

#### 3)
D'après le fichier, Otto ne boit que de l'eau et de la bière, car les deux seuls faits qui parlent d'Otto sont les suivant:

boit(otto, biere).
boit(otto, eau).

#### 4)

En tapant "boit(otto, vodka)." dans l'interpréteur, on obtient :

?- boit(otto, vodka).
false .

#### 5)
Après avoir changé le fichier, l'interpréteur nous donne :

?- boit(otto, vodka).
true .

Donc la _réponse de l'interpréteur a changé_.

#### 6)

L'interpréteur donne :

?- boit(X, eau).
X = abdoul .

Cette réponse implique que "abdoul" boit de l'eau.

#### 7)

L'interpréteur répond à la question "que boit lhouari ?" par :

?- boit(lhouari, X).
X = eau ;
X = cafe.

#### 8)

En s'inspirant de *boisson*, l'implication logique de *personne* qui permet d'obtenir si X est une personne est :

personne(X) :- boit(X, _).

### 2.2 La famille

#### 1)

Le prédicat *mère* fonctionne comme *père*, mais il teste si X est une femme au lieu d'un homme.

#### 2)

Les prédicats *fils*/*fille* testent si Y est un parent de X et X est un homme/une femme.

#### 3)

Les prédicats *grand-père* et *grand-mère* testent si X est le père/la mère d'un parent de Y.

#### 4)

Les prédicats *frère* et *soeur* testent si X et Y ont le même père (Z), la même mère (M), si X est un homme (frère)/une femme (soeur), et si X est différent de Y (sinon, Prolog dirait que tout le monde est son propre frère/sa propre soeur). Cette définition ne prend pas en compte les demi-frères et les demi-soeurs.

#### 5)

Le prédicat intermédiaire *sibling*(X, Y) teste si X et Y sont différents et ont le même père et la même mère (c'est-à-dire s'ils sont frères ou soeurs l'un de l'autre).

Le prédicat intermédiaire *enfant*(X, Y) teste si Y est un parent de X.

Le prédicat *cousin* (resp. *cousine*) teste si un parent de X est sibling d'un parent de Y, avec X un homme (resp. une femme).

#### 6)

Pour cette question, nous ne ferons pas l'arbre généalogique en entier (trop de temps requis pour quelque chose que l'on juge que l'on a déjà compris), mais nous ferons "une branche" de cet arbre, en prenant comme point de départ **Aurelien**.

Voir le fichier cette image/google draw joint.


### 2.3 La fin de la solitude
#### 1)

Voir code joint dans le reste du dossier.

#### 2)

Tout d'abord, nous avons besoin de la création de la condition pour plaire physiquement.
Il faut donc comparer certains attributs des personnes avec les goûts des autres, et renvoyer vrai si c'est égal.

Pour voir l'implémentation en Prolog, voir le code joint dans le reste du dossier.

#### 3)

Pour que deux personnes puissent se mettre en couple, il faut qu'ils aient les mêmes goûts et qu'ils soient attirés l'un par l'autre. Il faut donc réunir trois conditions, ainsi que vérifier que X ne soit pas en couple avec X (lui-même).

### 2.4 Attention à ne pas dépasser !
#### 1)

Voir question suivante (Nous avons fait les deux questions en même temps).

#### 2)

Pour voir l'implémentation en Prolog, voir le code joint dans le reste du dossier, nous avons également été confrontés au problème suivant :
Si l'on met les tests de différences des couleurs le plus tôt possible dans l'écriture du prédicat, on obtient toutes les 81 possibilités de répartition des couleurs au lieu des possibilités pour lesquelles deux zones adjacentes ont une couleur différente. En effet, lorsque l'on met ces tests au début, les variables C1, C2, C3 et C4 viennent d'être instanciées, elles n'ont donc aucune valeur.
Nous avons donc dû rajouter ceci :

    , not(C1 == C2), not(C1 == C3), not(C1 == C4), not(C2 == C3),not(C3 == C4).
	

à la fin de notre prédicat, afin que la vérification ait lieu.

## Exercice 3

### Exercice 3.1

Pour voir les prédicats en entier, voir les programmes dans le dossier joint.

#### Factorielle

Pour ce prédicat, on part de la base 0! = 1, qu'on code comme un fait en Prolog. Puis on réalise un appel récursif avec la formule : $n! = n\times (n-1)!$

#### Somme des entiers de 1 à n

Pour ce prédicat, on part de la base *somme(1) = 1*, qu'on code comme un fait en Prolog. Puis on réalise un appel récursif avec la formule : $somme(n) = n + somme(n-1)$

#### La suite de Fibonacci

Pour ce prédicat, on part des deux premiers termes de la suite de Fibonacci, 0 et 1, qu'on code comme des faits en Prolog. Dans le cas général, on réalise deux appels récursifs pour récupérer les deux termes précédents de la suite, puis on les additionne.

#### La fonction Ackermann

On implémente en Prolog les trois formules qui définissent la fonction d'Ackermann, qu'on définit comme un prédicat d'arité 3 prenant en paramètre M, N et le résultat R.

### Exercice 3.2

#### 1)

*chemin-oriente* est simplement une suite d'*arete* tel qu'il existe un *chemin-oriente* entre Z et Y, avec une *arete* entre X et Z.

#### 2)

Même cas, sauf qu'il faut un autre paramètre : N. Il s'incrémente à chaque fois qu'un appel récursif est effectué et commence à 1 (pour le cas où il existe directement X vers Y par exemple).

#### 3)

Pour résoudre l'exercice, nous nous sommes servis du prédicat *relier* qui est le suivant : 

relier(X,Y) :- arete(X,Y).
relier(X,Y) :- arete(Y,X).

Il renvoie vrai s'il y a une arête entre X et Y OU Y et X.

Pour avoir le prédicat *chemin*, nous avons besoin d'une liste pour nous permettre de stocker les différents points déjà parcourus pour ne pas les reprendre (nous avons donc rajouté le prédicat *membre* qui teste si un élément est dans une liste). En effet, sans cette condition, nous aurions une boucle infinie.
Nous avons donc besoin du prédicat suivant :

cheminliste(X,Y, L) :- sommet(X), sommet(Y), sommet(Z), relier(X,Z), not(membre(X, L)), not(membre(Z, L)), addhead(X, L, L1), addhead(Z, L1, L2), cheminliste(Z,Y ,L2), X\==Y.

qui nous permet de renvoyer si un chemin de X vers Y est disponible en fonction d'une liste qui contient déjà les points parcourus.

Puis, le prédicat suivant : 

chemin(X,Y) :- cheminliste(X, Y, []).

nous permet, en donnant la liste vide, (car encore aucun point n'est parcouru) de savoir si un chemin est disponible entre X et Y.

Le prédicat *connecte* quant à lui est appelé grâce au prédicat suivant :

separe(X,Y) :- sommet(X), sommet(Y), X\==Y, not(chemin(X,Y)).

qui renvoie vrai si un chemin entre un point X et un point Y n'existe pas (qui est la définition d'un graphe *non* connecté)

Nous avons donc juste à renvoyer la valeur inverse de *separe* pour savoir si le graphe est bien connecté.

## Exercice 4
### 4.1 Introduction

Nous n'avons pas pu mettre de fichier à part qui représente le code pour cette exercice, car il n'est pas demandé d'ajouter des lignes dans le logiciel. Par contre, nous avons expliqué toutes les réponses aux questions dans ce document.

#### 1)

?- [X|Y] = [a, b, c, d].
X = a,
Y = [b, c, d].

D'après la réponse de l'interpréteur, X est la *tête* de la liste et Y est son *corps* de cette liste.

#### 2)

Lorsque l'on rentre cette requête dans l'interpréteur, nous obtenons le résultat suivant :

?- [X] = [a,b,c,d].
false.

X étant le seul élement entre crochets, il correspond à la *tête* de la liste ainsi qu'à son *corps*. Donc X vaut deux choses différentes en même temps, ce qui est impossible.

### 4.2 Opérations sur les listes

#### 1)

Voir les fichiers joints dans le dossier rendu pour voir les réponses/prédicats.

#### 2)

Voir les fichiers joints dans le dossier rendu pour voir les réponses/prédicats.

#### 3)

Voir les fichiers joints dans le dossier rendu pour voir les réponses/prédicats.

#### 4)

Il y a un problème car [L | X] met L dans la tête alors que c'est une liste. On obtient donc une liste dont le premier élément est la liste L et le second est X, au lieu d'obtenir une liste d'éléments simples.

#### 5)

Voir les fichiers joints dans le dossier rendu pour voir les réponses/prédicats.

### 4.3 Construction inductive et langages
Pour cet exercice, nous posons $\epsilon$ le mot vide.
#### 1) aⁿb :

b $\in$ L
S $\in$ L $\to$ aS $\in$ L

Le mot b correspond à a⁰b, donc il appartient au langage et il suffit ensuite d'ajouter uniquement des a.

#### 2) abⁿ :

a $\in$ L
aS $\in$ L $\to$ abS $\in$ L

Le mot a correspond à ab⁰, donc il appartient au langage et il suffit ensuite d'ajouter uniquement des b juste derrière le a.

#### 3) aⁿb^m :

$\epsilon$ $\in$ L
a $\in$ L
b $\in$ L

aS $\in$ L $\to$ aaS $\in$ L
aS $\in$ L $\to$ abS $\in$ L
bS $\in$ L $\to$ bbS $\in$ L

Le mot vide correspond à a⁰b⁰ donc il appartient au langage, tout comme a¹b⁰ et a⁰b¹, respectivement a et b qui appartiennent au langage. Enfin, on peut ajouter des b, ou des a si on n'a pas encore trouvé de b.

#### 4) a^2*n :

$\epsilon$ $\in$ L
S $\in$ L $\to$ aaS $\in$ L

Le mot vide correspond à a^2*0 et 0 $\in$ N. Ensuite, il suffit d'ajouter 2 "a" d'un coup pour que le nombre de a soit toujours un multiple de 2.

#### 5) aⁿbⁿ :

$\epsilon$ $\in$ L
S $\in$ L $\to$ aSb $\in$ L

Le mot vide correspond à a⁰b⁰. Donc il appartient à ce langage. Comme la règle est aⁿbⁿ, si on ajoute un a, on obtient aⁿ⁺¹bⁿ or n = n $\neq$ n+1. Donc pour respecter la règle, si on ajoute a au debut, il faut aussi ajouter un b à la fin.

#### 6) palindrome :

$\epsilon$ $\in$ L
a $\in$ L
b $\in$ L

S $\in$ L $\to$ aSa $\in$ L
S $\in$ L $\to$ bSb $\in$ L

Un mot vide est un palindrome, tout comme un mot contenant une seule lettre.
Ensuite, pour être un palindrome, il suffit d'avoir la même lettre (qui appartient au langage) au début et à la fin.

#### 7) a^lb^mcⁿ :

Un mot qui ne contient que des b fait évidemment partie de ce langage. On utilise, pour tester si le mot ne contient que des b, le prédicat *onlyB*, qui a pour base le mot [b], et qui fait un appel récursif pour voir si la queue du mot ne contient que des b.

On peut alors rajouter des a au début du mot et des c à la fin du mot en utilisant le prédicat *addlast*.

#### 8) a^mbⁿc^m :

Pour ce langage, on rajoute le mot b dans la base, et on s'autorise à rajouter un b à un mot qui commence et finit par b (composé uniquement de b).

On peut aussi rajouter un a au début du mot et un c à la fin (dans le même temps), ce qui permet de garder le même nombre de a et de c.

#### 9) au plus un b :

La base est le mot b ainsi que le mot vide (car on peut avoir au plus un b, donc aucun). Puis, on peut rajouter des a au début, ou à la fin du mot.

#### 10) autant de a et b :

Il y a six manières d'ajouter un a et un b en même temps à un mot S, ce qui nous donnera les configurations finales suivantes :

* aSb
* bSa
* abS
* baS
* Sab
* Sba

Pour les implémenter, on utilise les têtes de liste ainsi que le prédicat *addlast*. (Voir le code)

#### 11) aⁿbⁿcⁿ :

Un mot de la forme aⁿbⁿcⁿ est un mot de la forme a^mbⁿc^m (question 8) ayant le même nombre de a, de b et de c.

Nous créons donc un prédicat intermédiaire *l_count* qui permet de récupérer le nombre de a, b et c d'un mot. Pour cela, il décompose le mot lettre par lettre en partant de la tête et incrémente le paramètre correspondant à la lettre trouvée.

On définit ensuite le langage 11 en testant que le nombre de a est égal au nombre de b, lui-même égal au nombre de c (ces données sont récupérées à l'aide du prédicat *l_count*), et en utilisant le prédicat *langage8* sur le mot testé pour vérifier que les a, b et c sont placés dans le bon ordre.