% Rapport TP - Logique - Augustin Quatrefages & Matheo Fortias

\pagebreak

## Requête et base de connaissances

### Introduction <a id="intro"></a>
1) D'après la ligne 8 du fichier, il est vrai que Vincent boit de la vodka.

2) Lorsque l'on tape dans l'interpréteur :

boit(vincent,vodka).

La réponse est ```true```.

3) On ne trouve pas de fait tel que :

boit(otto,vodka).

Donc, d'après ce qui est écrit dans le fichier, otto ne boit pas de vodka.

4) Lorsque l'on tape dans l'interpréteur :

boit(otto,vodka).

La réponse est ```false```.

5) En ajoutant dans le fichier boit.pl :

boit(otto,vodka).

et en tapant dans l'interpréteur :

boit(otto,vodka).

La réponse est ```true```.

6) Lorsque l'on tape dans l'interpréteur :

boit(X,eau).

Cela correspond à rechercher toutes les personnes qui boivent de l'eau. En tapant plusieurs fois ;, on obtient :

X = abdoul
X = simon
X = otto

On en déduit qu'en tapant ;, on obtient une personne supplémentaire qui boit de l'eau.

7) Lorsque l'on tape dans l'interpréteur :

boit(simon,X).

Cela correspond à rechercher toutes les boissons que boit simon. En tapant plusieurs fois ;, on obtient :

X = eau
X = cafe
X = cafe

8) En prenant exemple sur boisson, on peut modéliser la régle personne par l'implication logique suivante :
$$\forall X \quad \exists Y, \quad boit(X,Y) \longrightarrow personne(X)$$
En prolog, cette règle s'écrit de la manière suivante

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

Cette ligne signifie que X est une personne s’il existe une boisson qui est bu par X.

### La famille

1) **X est la mère de Y**

A partir des faits énoncés dans le fichier famille.pl, on peut déduire qu'une femme est la mère d'une autre personne si elle est son parent. Logiquement, on peut l'écrire :
$$\forall X,Y \quad (parent(X,Y) \wedge femme(X)) \longrightarrow mere(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

mere(X,Y) :- parent(X,Y), femme(X).

2) **X est le fils de Y** et **X est la fille de Y**

On peut déduire qu'un homme est le fils d'une autre personne si cette autre personne est son parent. Logiquement, on peut l'écrire :
$$\forall X,Y \quad (parent(Y,X) \wedge homme(X)) \longrightarrow fils(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

fils(X,Y) :- parent(Y,X), homme(X).

On peut déduire qu'une femme est la fille d'une autre personne si cette autre personne est son parent. Logiquement, on peut l'écrire :
$$\forall X,Y \quad (parent(Y,X) \wedge femme(X)) \longrightarrow fille(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

fille(X,Y) :- parent(Y,X), femme(X).

3) **X est le grand-père de Y** et **X est la grand-mère de Y**

On peut déduire qu'un homme X est grand-père d'une personne Y si X est père d'une autre personne W et que W est parent de Y.
Logiquement, on peut l'écrire :
$$\forall X,Y \; \exists W \quad (pere(X,W) \wedge parent(W,Y)) \longrightarrow grandpere(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

grandpere(X,Y) :- pere(X,W), parent(W,Y).

On peut déduire qu'une femme X est grand-mère d'une personne Y si X est mère d'une autre personne W et que W est parent de Y.
Logiquement, on peut l'écrire :
$$\forall X,Y \; \exists W \quad (mere(X,W) \wedge parent(W,Y)) \longrightarrow grandmere(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

grandmere(X,Y) :- mere(X,W), parent(W,Y).

4) **X est la soeur de Y** et **X est le frère de Y**

On peut déduire qu'une femme X est la soeur d'une personne Y si X est la fille d'une autre personne W et que W est parent de Y. Il est important que X soit différent de Y. On considère qu'une personne est la soeur d'une autre personne si ces deux personnes ont au moins un parent en commun.
Logiquement, on peut l'écrire :
$$\forall X,Y \; \exists W \quad (\neg(X==Y) \wedge (fille(X,W) \wedge parent(W,Y))) \longrightarrow soeur(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

soeur(X,Y) :- fille(X,W), parent(W,Y), not(X==Y).

On peut déduire qu'un homme X est le frère d'une personne Y si X est le fils d'une autre personne W et que W est parent de Y. Il est important que X soit différent de Y. On considère qu'une personne est le frère d'une autre personne si ces deux personnes ont au moins un parent en commun.
Logiquement, on peut l'écrire :
$$\forall X,Y \; \exists W \quad (\neg(X==Y) \wedge (fils(X,W) \wedge parent(W,Y))) \longrightarrow frere(X,Y)$$
Ce que l'on peut traduire en prolog par la règle :

frere(X,Y) :- fils(X,W), parent(W,Y), not(X==Y).

On remarque que lorsque deux personnes ont deux parents en commun, on obtient un doublon, ce que l'on ne sait pas gérer pour le moment.

5) **X est le cousin de Y** et **X est la cousine de Y**

On peut déduire qu'un homme X est le cousin d'une personne Y si X est le fils d'une autre personne W, que W est frère ou soeur d'une personne Z, et que Z est parent de Y. Il est important que X soit différent de Y. On considère qu'une personne est le cousin d'une autre personne si ces deux personnes ont au moins un de leurs deux parents qui sont frère-et-soeur.
Logiquement, on peut l'écrire :

$$\begin{aligned}
\forall X,Y \; \exists W,Z \quad ((X \neq Y) \wedge ((fils(X,W) \wedge parent(W,Y)) &\\
\wedge (frere(W,Z) \lor soeur(W,Z)))) \longrightarrow cousin(X,Y) &
\end{aligned}$$

Ce que l'on peut traduire en prolog par la règle :

cousin(X,Y) :- fils(X,W), parent(W,Y), frere(W,Z), not(X==Y).
cousin(X,Y) :- fils(X,W), parent(W,Y), soeur(W,Z), not(X==Y).

On peut déduire qu'une femme X est la cousine d'une personne Y si X est la fille d'une autre personne W, que W est frère ou soeur d'une personne Z, et que Z est parent de Y. Il est important que X soit différent de Y. On considère qu'une personne est la cousine d'une autre personne si ces deux personnes ont au moins un de leurs deux parents qui sont frère-et-soeur.
Logiquement, on peut l'écrire :

$$\begin{aligned}
\forall X,Y \; \exists W,Z \quad ((X \neq Y) \wedge ((fille(X,W) \wedge parent(W,Y)) &\\
\wedge (frere(W,Z) \lor soeur(W,Z)))) \longrightarrow cousine(X,Y) &
\end{aligned}$$

Ce que l'on peut traduire en prolog par la règle :

cousine(X,Y) :- fille(X,W), parent(W,Y), frere(W,Z), not(X==Y).
cousine(X,Y) :- fille(X,W), parent(W,Y), soeur(W,Z), not(X==Y).

6) Voici les arbres généalogiques que l'on a réussi à créer grâce aux règles précédentes :


### La fin et la solitude

1) **Donnons un ensemble de faits représentant le fichier des candidats :**

Nous avons créé une liste représentants l'ensemble des faits que l'on a créé à partir des prédicats :

personne(I, N, T, C, A)
gout(I, M, L, S)
recherche(I, T, C, A)

Voici cette liste :

%liste candidats
personne(1,romain,180,marron,18).
personne(2,dorine,150,blond,17).
personne(3,valbuena,110,noir,32).
personne(4,claire,165,bleu,19).
personne(5,gabin,189,roux,18).
personne(6,yves,150,marron,78).
personne(7,ousmane,170,noir,26).
personne(8,antoine,180,marron,25).
personne(9,barthez,190,chauve,50).
personne(10,james,169,rouge,36).
personne(11,marine,179,blond,56).
personne(12,jeanluc,189,gris,13).
personne(13,gontran,179,noir,18).
personne(14,chloe,170,marron,23).
personne(15,loli,167,blond,56).
personne(16,catherine,145,rouge,89).

%liste goûts
gout(1,drill,poesie,muscu).
gout(2,drill,poesie,muscu).
gout(3,rap,theatre,rugby).
gout(4,classique,theatre,basket).
gout(5,rap,theatre,rugby).
gout(6,classique,theatre,basket).
gout(7,variete,roman,muscu).
gout(8,variete,poesie,muscu).
gout(9,salsa,roman,natation).
gout(10,variete,fantaisie,basket).
gout(11,classique,roman,rugby).
gout(12,classique,roman,rugby).
gout(13,jazz,theatre,boxe).
gout(14,salsa,roman,natation).
gout(15,variete,poesie,muscu).
gout(16,rap,theatre,basket).

%liste recherches
recherche(1,150,blond,17).
recherche(2,180,marron,18).
recherche(3,189,roux,18).
recherche(4,150,marron,78).
recherche(5,110,noir,32).
recherche(6,165,bleu,19).
recherche(7,180,marron,25).
recherche(8,167,blond,56).
recherche(9,170,marron,23).
recherche(10,179,blond,56).
recherche(11,189,gris,13).
recherche(12,145,rouge,89).
recherche(13,189,gris,13).
recherche(14,190,chauve,50).
recherche(15,180,marron,25).
recherche(16,180,marron,18).

2) **Écrire les règles définissant ```convient-physiquement(X, Y)``` et ```ont-memes-gouts(X, Y)``` :**

D'après la consigne, on considère qu'une personne X convient physiquement à Y si les goûts de Y correspondent aux recherche de X. Ainsi, nous avons la formule logique suivante :

$$\begin{aligned}
\forall X,Y \; \exists N,T,C,A \quad (personne(X,N,T,C,A) \wedge recherche(Y,T,C,A)) &\\
\longrightarrow convient\_physiquement(X,Y) &
\end{aligned}$$

Ce que l'on peut traduire en prolog par la règle :

convient_physiquement(X,Y) :- personne(X,N,T,C,A), recherche(Y,T,C,A).

D'après la consigne, on considère qu'une personne X a les mêmes goûts qu'une personne Y si les goûts de X correspondent aux goûts de Y et réciproquement. Ainsi, nous avons la formule logique suivante :

$$\begin{aligned}
\forall X,Y \; \exists T,C,A \quad ((X \neq Y) \wedge (gout(X,T,C,A) \wedge gout(Y,T,C,A))) &\\
\longrightarrow ont\_memes\_gouts(X,Y) &
\end{aligned}$$

Ce que l'on peut traduire en prolog par la règle :

ont_memes_gouts(X,Y) :- gout(X,M,L,S), gout(Y,M,L,S), not(X==Y).

3) **Déduisons-en le programme qui détermine les couples assortis :**

D'après la consigne, on considère qu'une personne X et une personne Y sont assortis si X convient à Y et si Y convient à X, et si X a les mêmes goûts que Y et réciproquement. Ainsi, nous avons la formule logique suivante :

$$\begin{aligned}
\forall X,Y \quad ((X \neq Y) \wedge (convient\_physiquement(X,Y) &\\
\wedge convient\_physiquement(Y,X) \wedge ont\_memes\_gouts(X,Y))) &\\
\longrightarrow sont\_assortis(X,Y) &
\end{aligned}$$

Ce que l'on peut traduire en prolog par la règle :

sont_assortis(X,Y) :- convient_physiquement(X,Y), convient_physiquement(Y,X), ont_memes_gouts(X,Y).

### Attention à ne pas dépasser !

1) **Écrivons un prédicat ```coloriage(C1, C2, C3, C4)``` qui génère toutes les valeurs possibles de C1, C2, C3 et C4 et vérifie si les colorations obtenues sont conformes à la carte :**

On remarque sur la figure que seulement la zone C2 et la zone C4 peuvent avoir la même couleur. C'est-à-dire que :
* C1 et C2 ont une couleur différente
* C1 et C3 ont une couleur différente
* C1 et C4 ont une couleur différente
* C2 et C3 ont une couleur différente
* C3 et C4 ont une couleur différente

Pour établir le prédicat ```coloriage(C1,C2,C3,C4)```, nous avons besoin d'une liste de couleurs :

%liste des couleurs
couleur(vert).
couleur(jaune).
couleur(rouge).

Ainsi, on a la formule logique suivante :

$$\begin{aligned}
\forall C1,C2,C3,C4 \quad &\\
((couleur(C1) \wedge couleur(C2) \wedge couleur(C3) \wedge couleur(C4)) &\\
\wedge ((C1 \neq C2) \wedge (C1 \neq C3) \wedge (C1 \neq C4) \wedge (C2 \neq C3) \wedge (C3 \neq C4))) &\\
\longrightarrow coloriage(C1,C2,C3,C4) &
\end{aligned}$$

Ce que l'on peut traduire en prolog par la règle :

coloriage(C1,C2,C3,C4) :- couleur(C1), couleur(C2), couleur(C3), couleur(C4), not(C1==C2), not(C1==C3), not(C1==C4), not(C2==C3), not(C3==C4).

2) **Modifions le programme en déplaçant les tests de différence de couleurs le plus tôt possible dans l’écriture du prédicat :**

En déplaçant les tests de différence de couleurs le plus tôt possible dans l’écriture du prédicat, on obtient la formule logique suivante :

$$\begin{aligned}
\forall C1,C2,C3,C4 \quad &\\
(couleur(C1) \wedge (couleur(C2) \wedge (C1 \neq C2)) \wedge (couleur(C3) \wedge (C1 \neq C3) &\\
\wedge (C2 \neq C3)) \wedge (couleur(C4) \wedge (C1 \neq C4) \wedge (C3 \neq C4))) &\\
\longrightarrow coloriage(C1,C2,C3,C4) &
\end{aligned}$$

Ce qui se traduit en prolog par :

coloriage(C1,C2,C3,C4) :- couleur(C1), couleur(C2), not(C2==C1), couleur(C3), not(C2==C3), not(C1==C3), couleur(C4), not(C1==C4), not(C3==C4).

Les conséquences sont qu'en tapant la commande :

coloriage(C1,C2,C3,C4).

On obtient :

C1 = C2, C2 = C3, C3 = C4, C4 = vert

Or, ceci n'est pas un coloriage valide car il existe au moins deux zones contiguës qui sont de couleurs identiques. En fait, l'ensemble du coloriage est de la même couleur.

## Graphe et récursivité

### Intoduction

1) **La fonction factorielle :**

La fonction factorielle(n) correspond au produit des éléments de 1 à n. Par convention, la factorielle de 0 est égale à 1. Ainsi, la facrorielle de n se traduit par la formule :
$$ n! = \prod_{i = 1}^{n} i $$
De plus, on sait que :
$$ n! = n * (n-1)!$$

On obtient la formule logique suivante :

$$\begin{aligned}
fact(0,1) &\\
((n > 0) \wedge fact(n-1,r/n)) \longrightarrow fact(n,r) &
\end{aligned}$$

Ce qu'on peut traduire en prolog par la règle :

fact(0,1).
fact(N,R1) :- N>0, M is N-1, R2 is N/R1, fact(M,R2).

2) **Somme des entiers de 1 à n :**

La somme des entiers de 1 à n se traduit par la formule :
$$ \sum_{i = 1}^{n} i = 1 + 2 + ... + n$$
De plus, on sait que :
$$ \sum_{i = 1}^{n} i = n + \sum_{j = 1}^{n-1} j$$

On obtient la formule logique suivante :

$$\begin{aligned}
somme(1,1) &\\
((n > 1) \wedge somme(n-1, r-n)) \longrightarrow somme(n,r) &
\end{aligned}$$

Ce qu'on peut traduire en prolog par la règle :

somme(1,1).
somme(N,R1) :- N>1, M is N-1, R2 is R1-N, somme(M,R2).

3) **La suite Fibonacci :**

La suite de Fibonacci est définie par la suite $(U_{n})$ :
$$
\begin{array}{r c l}
U_{1} & = & 1 \\
U_{2} & = & 1 \\
U_{n} & = & U_{n-1} + U_{n-2}
\end{array}
$$

On obtient la formule logique suivante :

$$\begin{aligned}
fibo(1,1) &\\
fibo(2,1) &\\
((n > 1) \wedge fibo(n-1,r1) \wedge fibo(n-2,r2)) \longrightarrow fibo(n,r1+r2) &
\end{aligned}$$

Ce qu'on peut traduire en prolog par la règle :

fibo(1,1).
fibo(2,1).
somme(N,R1) :- N>1, M is N-1, R2 is R1-N, somme(M,R2).

4) **La fonction d'Ackermann :**

La fonction d'Ackermann $A(n,m)$ est définie comme ceci :
$$
\begin{array}{r c l}
A(0,n) & = & n+1 \\
A(m,0) & = & A(m-1,1) \\
A(m,n) & = & A(m-1,A(m,n-1))
\end{array}
$$

On obtient la formule logique suivante :
$$\begin{aligned}
ackermann(0,n,n+1) &\\
(((m>0) \wedge ackermann(m,0,ackermann(m-1,1,r))) &\\
\lor ((m>0) \wedge (n>0) \wedge ackermann(m,n-1,r1) \wedge ackermann(m-1,r1,r))) &\\\longrightarrow ackermann(m,n,r) &
\end{aligned}$$

Ce qu'on peut traduire en prolog par la règle :

ackermann(0,N,R) :- R is N+1.
ackermann(M,0,R) :- M > 0, M1 is M-1, ackermann(M1,1,R).
ackermann(M,N,R) :- M > 0, N > 0, M1 is M-1, N1 is N-1, ackermann(M,N1,R1), ackermann(M1,R1,R).

Si $m=0$, on a $A(m,n)=n+1$. Ainsi, on attribut à $R$ la valeur $N+1$. On obtient donc la ligne 1.

De plus, si $n=0$ et $m>0$, on a A(m,n)=A(m-1,1). Ainsi, le résultat de notre prédicat avec $N=0$ et $M>0$ est le même que le prédicat où $M=N-1$ et $N=1$ d'où l'utilisation de la même variable $R$ donnant le résultat.

Pour finir, le résultat du predicat ackermann(m,n,r) pour $m>0$ et $n>0$ est le même que le résultat du prédicat tel que m=m-1 et n=A(m,n-1) d'où l'utilsation de la même variable $R$ donnant le réulstat.

### Graphes dirigés acycliques

1) **Chemin orienté :**

Un chemin entre deux sommets X et Y est dit orienté s'il existe un chemin permettant de relier le sommet X au sommet Y.

On a donc la formule logique suivante :

$$\begin{aligned}
\forall X \forall Y \exists R \quad ((sommet(X) \wedge sommet(Y) \wedge sommet(R)) &\\
\wedge((arete(X,Y)) \lor (arete(X,R) \wedge chemin\_oriente(R,Y)))) &\\
\longrightarrow chemin\_oriente(X,Y)
\end{aligned}$$

Ce qu'on peut traduire en prolog par :

chemin_oriente(X, Y) :- arete(X,Y).
chemin_oriente(X, Y) :- arete(X, R), chemin_oriente(R, Y).

2) **Chemin orienté de taille N:**

Un chemin entre deux sommets X et Y est dit orienté s'il existe un chemin permettant de relier le sommet X au sommet Y en passant par exactement par N sommets, soit les sommets intermédiaires et le sommet d'arrivée Y.

On a donc la formule logique suivante :

$$\begin{aligned}
\forall X \forall Y \exists R \exists N \quad ((sommet(X) \wedge sommet(Y) \wedge sommet(R)) &\\
\wedge((arete(X,Y)) \lor (arete(X,R) \wedge chemin\_oriente(R,Y,N-1)))) &\\
\longrightarrow chemin\_oriente(X,Y,N) &
\end{aligned}$$

Ce qu'on peut traduire en prolog par :

chemin_oriente(X,Y,N) :- arete(X,Y), N=1.
chemin_oriente(X,Y,N) :- N1 is N-1, arete(X,R), chemin_oriente(R,Y,N1).

3) **Chemin non-orienté :**

Il existe un chemin entre deux sommets X et Y s'il existe un chemin non-orienté permettant de relier le sommet X au sommet Y. Il y a ainsi 5 cas possibles :

* il existe une arête reliant X à Y.
* il existe une arête reliant Y à X.
* il existe un sommet R tel qu'il existe une arête reliant X à R et un chemin reliant R à Y.
* il existe un sommet R tel qu'il existe une arête reliant Y à R et un chemin reliant R à X.
* il existe un sommet R tel qu'il existe une arête reliant R à Y et un chemin reliant R à X.

Il est important que X soit différent de Y.

On a donc la formule logique suivante :

$$\begin{aligned}
\forall X \forall Y \exists R \quad ((X \neq Y) &\\
\wedge (arete(X,Y) \lor arete(Y,X) \lor (arete(X,R) \wedge chemin(R,Y)) &\\
\lor (arete(Y,R) \wedge chemin(R,X)) \lor (arete(R,Y) \wedge chemin(R,X)))) &\\
\longrightarrow chemin(X,Y) &
\end{aligned}$$

Ce qu'on peut traduire en prolog par :

chemin(X, Y) :- not(X==Y), arete(X, Y).
chemin(X, Y) :- not(X==Y), arete(Y, X). 
chemin(X, Y) :- not(X==Y), arete(X, R), chemin(R, Y).
chemin(X, Y) :- not(X==Y), arete(Y, R), chemin(R, X).
chemin(X, Y) :- not(X==Y), arete(R, Y), chemin(R, X).

4) **Graphe connect :**

On remarque qu'un graphe est connecte si il existe un sommet X du graphe qui est relié à tous les autres sommets du graphe. Autrement dit, si il existe un chemin reliant X à chacun des autres sommets du graphe. Soit $L$ la liste des sommets du graphe

$$\begin{aligned}
\exists X \in L, \quad \forall Y \in L \; ((X \neq Y) \wedge chemin(X,Y)) \longrightarrow connecte(L)
\end{aligned}$$

On utilisera ici la récursivité sur les liste, il faut donc définir une condition d'arrêt. Ainsi, lorsque la liste qui représente le graphe sera vide, alors le graphe sera connecte.

Ce qui se traduit en prolog par :

connecte(L) :- L = [_].
connecte(L) :- L = [X,Y|T], chemin(X,Y), L1 = [X|T], connecte(L1).

## Listes et langages

### Introduction

1)

En tapant dans l'interpréteur ceci :

[X | Y] = [a, b, c, d]

On obtient :

X = a,
Y = [b, c, d]

Ainsi, X représente la tête de la liste ```[a, b, c, d]``` et Y représente la queue de la liste ```[a, b, c, d]```.

2)

En tapant dans l'interpréteur ceci :

[X] = [a, b, c, d]

On obtient ```false```.

### Opérations sur les listes

1) **Prédicat ```head(X,L)```**

On sait que X est la tête de L si X est situé au début de L. Aisi, on a le code prolog suivant :

head(X,L) :- L = [X|_].

Par exemple, si on tape dans l'interpréteur :

head(X,[1,2,3]).

On obtient bien ```X = 1```.

2) **Prédicat ```addhead(X,L,L1)```**

On sait que le fait d'ajouter X au début de L correspond au fait de créer une liste L1 avec pour tête X et pour queue L, d'où le code prolog :

addhead(X,L,L1) :- L1 = [X|L].

Par exemple, si on tape dans l'interpréteur :

addhead(1,[2,3],L1).

On obtient bien ```L1 = [1, 2, 3]```.


3) **Prédicat ```last(X,L)```**

Pour connaître le dernier élément d'une liste, il y a deux cas possibles :

* soit la liste ne contient qu'un seul élément, donc la queue est vide, donc on renvoie la tête de la liste.
* soit la liste contient plus d'un élément, donc la queue n'est pas vide, donc on rappel la le prédicat ```last``` sur la queue de la liste.

On a ainsi le code prolog suivant :

last(X,L) :- L = [X].
last(X,L) :- L = [_|Q], last(X,Q).

Par exemple, si on tape dans l'interpréteur :

last(X,[1,2,3]).

On obtient bien ```X = 3```.

4) **Prédicat ```addlast(X,L,L1)```**

En éxécutant la ligne suivante, 

addlast(e,[a,b,c,d],Resultat).

On obtient :

Resultat = [[a, b, c, d]|e]

Ici, on remarque que la t^te de ```Resultat``` est en fait la liste L et la queue est l'élément X. En effet, on remarque que si L n'est pas vide, alors L1 aura pour tête L et pour queue X. Or, ce n'est pas ce que l'on veut.

Pour ajouter un élément à la fin de la liste, il y a deux cas possibles :

* soit la liste L est vide, alors on ajoute X à la liste L1 qui contient désormais un élément.
* soit la liste L n'est pas vide, elle est alors composée d'une tête T et d'une queue Q. Ainsi, puisque L1 est obtenue à partir de L de façon récursive la tête T de L est la même tête que celle de L1. Et le début de la queue est aussi le même. On a donc juste à ajouter X à rappeler la règle ```addlast```jusqu'à ce que la liste L soit vide.

On a ainsi le code prolog suivant :

addlast(X, [], [X]).
addlast(X,L,L1) :- L = [T|Q], L1 = [T|Q2], addlast(X,Q,Q2).

Par exemple, si on tape dans l'interpréteur :

addlast(e,[a,b,c,d],Resultat).

On obtient bien ```Resultat = [a, b, c, d, e]```.

5) **Prédicat ```reverse(L,L)```**

Pour creer une liste L1 correspondant au renversesement d'une liste L, il y a deux cas possibles :

* soit la liste L nest vide, donc son renversement L1 est vide.
* soit la liste  L contient au moins un élément, alors on va appelr la règle pour inverser Q, soit la queue de L, et on va stocker cette liste renverser dans L2. Puis, on va ajouter la tête T de L à la fin de L2 grâce à la règle ```addlast(X,L,L1)``` et on stockera le résultat dans L1.

On a ainsi le code prolog suivant :

reverse([],[]).
reverse(L,L1) :- L = [T|Q], reverse(Q,L2), addlast(T,L2,L1).

Il est important ici d'appliquer la règle ```reverse``` avant d'ajouter T à la fin de L2 car il faut que L2 corresponde déjà au renversement de la queue Q de L.

Par exemple, si on tape dans l'interpréteur :

reverse([a,b,c,d],Resultat).

On obtient bien ```Resultat = [d, c, b, a]```.

### Construction inductive et langages

1) **Langage 1 : $a^nb$ avec $n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$ et de $b$ tels qu'ils contiennent $n$ $a$ et un seul $b$ à la fin. Voici la construction inductive :

$$\begin{aligned}
b \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aS \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage1([b]).
langage1([a|S]) :- langage1(S).

Tout mot auquel on ajoute a au début est valide. De plus, S est valide donc [a|S] est valide (S auquel on ajoute a au début).

2) **Langage 2 : $ab^n$ avec $n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$ et de $b$ tels qu'ils contiennent $n$ $b$ et un seul $a$ au début. Voici la construction inductive :

$$\begin{aligned}
a \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad Sb \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage2([a]).
langage2(S) :- addlast(b,S1,S), langage2(S1).

Tout mot auquel on ajoute b à la fin est valide. De plus, S1 est valide donc si on ajoute b à la fin de S1, on obtient S (par addlast) qui est par conséquent valide.


3) **Langage 3 : $a^nb^m$ avec $n,m \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$ et de $b$ tels qu'ils contiennent $n$ $a$ au début et $m$ $b$ à la fin. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aS \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad Sb \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage3([]).
langage3([a]).
langage3([b]).
langage3([a|S]) :- langage3(S).
langage3(S) :- addlast(b,S1,S), langage3(S1).

Tout mot auquel on ajoute a devant ou b à la fin est valide. De plus, si S est valide alors [a|S] est valide (avant dernière ligne). Enfin, si S1 est valide alors S qui est S1 avec b ajouté devant est valide.

4) **Langage 4 : $a^{2n}$ avec $n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$ tels qu'ils contiennent un nombre pair de $a$. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aaS \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage4([]).
langage4([a,a|S]) :- langage4(S).

Tout mot avec un nombre pair de a est valide. De plus, si S est valide alors S auquel on a ajouté deux a devant [a,a|S] est valide.

5) **Langage 5 : $a^nb^n$ avec $n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$ et de $b$ tels qu'ils contiennent $n$ $a$ au début et $n$ $b$ à la fin. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aSb \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage5(S) :- S = [].
langage5([a|Q]) :- addlast(b,S1,Q), langage5(S1).

Il y a deux cas possible :

* soit le mot S est vide,
* soit le mot S contient un $a$ en première position, alors on fait comme si on avait ajouté un b à la fin de la queue de S et on vérifie si la queue sans le b à la fin est un mot construit comme ceci : $a^nb^n$.

6) **Langage 6 : L’ensemble des mots palindromes sur** {$a,b$} **:**

Soit $\varpi$ l'ensemble des mots constitués de $a$ et de $b$ tels que le mot soit mots palindromes sur {$a,b$}. Un mot sur cet alphabet est palindrome si on
peut le lire de gauche à droite ET de droite à gauche. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
a \in \varpi &\\
b \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aSa \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad bSb \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage6([]).
langage6([a]).
langage6([b]).
langage6([a|S2]) :- addlast(a,S1,S2), langage6(S1).
langage6([b|S2]) :- addlast(b,S1,S2), langage6(S1).

Tout palindrome est valide. De plus, si S1 est valide alors S2 qui est S1 avec a derriere n'est pas valide mais S2 avec un a devant est valide. Enfin, si S1 est valide alors S1 avec un b derrière (qui est S2) n'est pas valide. Or, S2 avec un b devant lui est valide.


7) **Langage 7 : $a^lb^mc^n$ avec $l,m,n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$, de $b$ et de $c$ tels qu'ils contiennent $l$ $a$ au début, $m$ $b$ au milieu et $n$ $c$ à la fin. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
b^m \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aS \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad Sc \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage7([]).
langage7([c]).
langage7([b]).
langage7([a|S]) :- langage7(S).
langage7(S) :- addlast(c,S1,S), langage7(S1).

Tout mot avec n'importe quel nombre de a devant, b au milieu et c à la fin est valide. De plus, si S est valide alors si on ajoute a devant S alors S est toujours valide. Enfin, si S1 est valide alors S qui est S1 avec c à la fin est valide.

8) **Langage 8 : $a^mb^nc^m$ avec $m,n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$, de $b$ et de $c$ tels qu'ils contiennent $m$ $a$ au début, $n$ $b$ au milieu et $m$ $c$ à la fin. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
b^n \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aSc \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage8([]).
langage8([b]).
langage8([a,c]).
langage8([b|S]) :- langage8(S), S = [T|_], not(T==a).
langage8([a|S2]) :- addlast(c,S1,S2), langage8(S1).

On a pour le langage 8 que tout mot avec exactement le même nombre de a et de c respectivement avant et après un nombre indépendant de b est valide. Les règles se font en deux lignes: la première donne que si le mot S est valide et ne possède pas de a devant alors rajouter un b devant ne change pas la validité du mot. La deuxième ligne donne que si un mot S1 est valide alors un mot S2 qui est une copie de S1 avec un c à la fin n'est pas valide mais si on lui rajoute un a devant alors ce mot S2 devient valide.

9) **Langage 9 : L’ensemble des mots sur** {$a,b$} **contenant au plus un $b$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$ et de $b$ tels qu'ils contiennent 0, 1 ou plusieurs $a$ et un seul $b$. Voici la construction inductive :

$$\begin{aligned}
b \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aS \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad Sa \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage9([]).
langage9([b]).
langage9([a|S]) :- langage9(S).
langage9(S) :- S = [T|Q], not(T==b), langage9(Q).

Pour le langage 9 on a que tout mot avec au plus un b est valide. La construction se fait en deux lignes: la première donne que si un mot S est valide alors ce même mot avec un a devant est valide. La deuxième ligne indique que si un mot S est valide et que pour tout élément de S aucun n'est égal à b alors ce mot S avec un b devant est valide
10) **Langage 10 : L’ensemble des mots sur** {$a,b$} **contenant le même nombre de $a$ et de $b$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$, de $b$ et de $c$ tels qu'ils contiennent le même nombre de $a$ et de $b$. Voici la construction inductive :

$$\begin{aligned}
\epsilon \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad abS \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad baS \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad Sab \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad Sba \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad aSb \in \varpi &\\
S \in \varpi \quad \longrightarrow \quad bSa \in \varpi &
\end{aligned}$$

Voici le code prolog associé :

langage10([]).
langage10([a,b|S]) :- langage10(S).
langage10([a|S2]) :- addlast(b,S1,S2), langage10(S1).
langage10([b|S2]) :- addlast(a,S1,S2), langage10(S1).

Pour le langage 10, tout mot qui contient exactement le même nombre de a et de b est valide. La construction se fait en 3 lignes. La première ligne donne que ajouter ab au début d'un mot valide donne un mot valide. La deuxième ligne donne que ajouter un a au début et un b à la fin d'un mot valide S1 donne un mot valide S2. Enfin, la troisième ligne donne que ajouter un b au début et un a à la fin d'un mot valide S1 donne un mot valide S2.

11) **Langage 11 : $a^nb^nc^n$ avec $n \in \mathbb{N}$ :**

Soit $\varpi$ l'ensemble des mots constitués de $a$, de $b$ et de $c$ tels qu'ils contiennent n $a$ au début, n $b$ au milieu et n $c$ à la fin. Voici la construction inductive : 

$$\begin{aligned}
\epsilon \in \varpi &\\
S = a^{n_1-1}b^{n_2-1}c^{n_3-1} \in \varpi \longrightarrow S' = a^{n_1}b^{n_2}c^{n_3} \in \varpi &
\end{aligned}$$

On a, pour s'aider à réaliser le langage 11, créé un prédicat count. Ce prédicat est vrai si A apparait N fois dans L (avec count(A,L,N)).

count(_,[],0).
count(Y,[Y|T],N) :- count(Y,T,N1), N is N1 + 1.
count(Y,[X|T],N) :- X \= Y, count(Y,T,N).

Ce prédicat est construit en trois lignes. La première donne que si la liste est vide alors n'importe quelle valeur apparait 0 fois. La deuxième ligne donne que si la tête de L est égale à Y alors on ajoute 1 au compteur N et on passe à la valeur suivante par récurrence. Enfin la dernière ligne donne que si la tête n'est pas égale à Y alors on passe seulement à la valeur suivante pas récurrence.

Enfin, le prédicat du langage 11:

langage11(S) :- count(a,S,N1), count(b,S,N2), N1==N2, count(c,S,N3), N3==N1.

Pour le langage 11, on a qu'un mot est valide si il possède exactement le même nombre de a, de b et de c dans cet ordre précis. Pour ce faire l'unique ligne du prédicat compte le nombre de a, de b et de c du mot et s'assure que ces nombres sont égaux.

## Conclusion

Durant ce projet, nous avons découvert le langage ```prolog``` et l'implémentation de la logique avec ```prolog```. Ainsi, nous avons abordé ce projet avec l'utilisation et la création de règles simples. Dans un second temps, on a approché le concept de récursivité qui s'est avéré très utile dans la programmation des fonctions arithmétiques et dans le traitement des graphes dirigés acycliques. Enfin, l'utilisation des listes en ```prolog```. Tout d'bord, nous avons implémenter des règles  récursives permettant de faire des opérations sur les liste. Puis, nous avons utlisé ces règles pour la construction inductive de langages. Nous nous sommes tout les deux impliqué à 50% chacun dans ce projet, aussi bien dans l'utlisation de ```prolog``` qua dans la rédaction du rapport en ```markdown```.

Commande pandoc : ``` pandoc --toc --listings -H listings-setup.tex --pdf-engine=xelatex -o rapport.pdf rapport.md ```