# TP de logique
* **BLANCHON Amaury**
* **DUREL Enzo**
* **ROCHE Yannis**
## Requête et base de connaissances
### Introduction
**1. D’après ce qui est écrit dans le fichier, est-il vrai que Vincent boit de la vodka ?**
> D’après ce qui est écrit dans le fichier, Vincent boit de la vodka.
**2. Dans l’interpréteur (à droite), tapez `boit(vincent, vodka).` (attention au point !). Quelle est la réponse ?**
> En tapant `boit(vincent, vodka).`, la réponse de l'interpréteur est `true`
**3. D’après ce qui est écrit dans le fichier, est-il vrai qu’Otto boit de la vodka ?**
> Rien ne précise qu'Otto boit de la vodka dans le fichier.
**4. Tapez `boit(otto, vodka)`. et notez la réponse de l’interpréteur**
> En tapant `boit(otto, vodka).`, la réponse de l'interpréteur est `false`
**5. Ajoutez la ligne `boit(otto, vodka).` au fichier et retapez la commande `boit(otto, vodka).`.
La réponse de l’interpréteur a-t-elle changé ?**
> Après ajout du prédicat `boit(otto, vodka).`, la réponse de l'interpréteur est `true`
**6. Tapez `boit(X, eau).`, à quoi correspond la réponse de l’interpréteur ?**
*Tapez ; (plusieurs fois) pour avoir d’autres solutions.*
>La réponse donnée par l'interpréteur correspond à toutes les personnes qui boivent de l'eau
>| X | |
>| -------- | - |
>| abdoul | 1 |
>| lhouari | 2 |
>| otto | 3 |
**7. Tapez `boit(lhouari, X).`, que donne l’interpréteur ?**
>La réponse donnée par l'interpréteur correspond à toutes les boissons que boit Lhouari.
>| X | |
>| ----- | - |
>| eau | 1 |
>| cafe | 2 |
**8. En prenant exemple sur boisson, donner l’implication logique et le prédicat personne qui détermine si X est une personne ou non**
Implication logique
>$\forall\ x\ \exists\ y\ (boit(x, y)\rightarrow\ personne(x))$
Prédicat correspondant en Prolog
```prolog=
personne( X ) :- boit(X, _).
```
### La famille
**1. Le prédicat `mere(X, Y)` signifiant `X` est la mère de `Y`**
Implication logique
>$\forall\ x\ \exists\ y\ ((femme(x) \wedge\ parent(x, y))\rightarrow\ mere(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'une femme X qui a un enfant Y
mere(X,Y) :-
femme(X), % X est une femme
parent(X, Y). % X a un enfant Y
```
**2. Les prédicats `fils(X, Y)` et `fille(X, Y)`.**
Implication logique
>$\forall\ x\ \exists\ y\ ((homme(x) \wedge\ parent(y, x))\rightarrow\ fils(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'un homme X qui a un parent Y
fils(X, Y) :-
homme(X),
parent(Y, X).
```
Implication logique
>$\forall\ x\ \exists\ y\ ((femme(x) \wedge\ parent(y, x))\rightarrow\ fils(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'une femme X qui a un parent Y
fille(X, Y) :-
femme(X),
parent(Y, X).
```
**3. Les prédicats `grandpere(X, Y)` et `grandmere(X, Y).`**
Implication logique
>$\forall\ x\ \exists\ y\ \exists\ z (pere(x, z) \wedge\ parent(z, y))\rightarrow\ grandpere(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'un pere X qui a un enfant Z et Z parent de Y
grandpere(X, Y) :-
pere(X, Z), % X est pere de Z
parent(Z, Y). % Z est parent de Y
```
Implication logique
>$\forall\ x\ \exists\ y\ \exists\ z (mere(x, z) \wedge\ parent(z, y))\rightarrow\ grandpere(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'un pere X qui a un enfant Z et Z parent de Y
grandmere(X, Y) :-
mere(X, Z), % X est mere de Z
parent(Z, Y). % Z est parent de Y
```
**4. Les prédicats `soeur(X, Y)` et `frere(X, Y)`.**
Implication logique
>$\forall\ x\ \exists\ y\ \exists\ z ((homme(x) \wedge\ parent(z, x) \wedge\ parent(z, y))\rightarrow\ frere(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'un homme X qui a un parent commun avec Y
frere(X, Y) :-
X\==Y, % X différent de Y
parent(Z, X), % X a un parent Z
parent(Z, Y), % Y a un parent Z
homme(X). % X est un homme
```
Implication logique
>$\forall\ x\ \exists\ y\ \exists\ z ((femme(x) \wedge\ parent(z, x) \wedge\ parent(z, y))\rightarrow\ soeur(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'une femme X qui a un parent commun avec Y
soeur(X, Y) :-
X\==Y, % X différent de Y
parent(Z, X), % X a un parent Z
parent(Z, Y), % Y a un parent Z
femme(X). % X est une femme
```
**5. Les prédicats `cousin(X, Y)` et `cousine(X, Y)`**
Implication logique
>$\forall\ x\ \exists\ y\ \exists\ z ((homme(x) \wedge\ parent(a, x) \wedge\ parent(b, y)\wedge$
>$(soeur(a, b)\vee\ frere(a, b)))\rightarrow\ cousin(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'un homme X qui a un(e) cousin(e) Y
cousin(X, Y) :-
X\==Y, % X différent de Y
parent(A, X), % X a un parent A
homme(X), % X est un homme
parent(B, Y), % Y a un parent B
(soeur(A, B); frere(A, B)). % A et B ont un lien fraternel
```
Implication logique
>$\forall\ x\ \exists\ y\ \exists\ z ((femme(x) \wedge\ parent(a, x) \wedge\ parent(b, y)\wedge$
>$(soeur(a, b)\vee\ frere(a, b)))\rightarrow\ cousine(x, y))$
Prédicat correspondant en Prolog
```prolog=
% Prédicat d'un homme X qui a un(e) cousin(e) Y
cousine(X, Y) :-
X\==Y, % X différent de Y
parent(A, X), % X a un parent A
femme(X), % X est une femme
parent(B, Y), % Y a un parent B
(soeur(A, B); frere(A, B)). % A et B ont un lien fraternel
```
**6. Relations de parenté**
En plus des prédicats écrits aux questions précèdentes, nous avons également écrit trois prédicats supplémentaires qui nous ont permis de faciliter la détermination des relations de parenté entre les personnes.
1. Le prédicat `justeEnfant(X).` qui permet de déterminer si `X` est l'enfant de quelqu'un sans avoir d'enfants.
```prolog=
% Prédicat d'un enfant qui n'a pas d'enfants
justeEnfant(X) :-
not(parent(X, _)). % Si X n'est pas parent d'une autre personne
```
2. Le prédicat `justeParent(X).` qui permet de déterminer si `X` est parent mais n'as pas de parents connus.
```prolog=
% Prédicat d'un Parent dont on ne connait pas les parents
justeParent(X) :-
parent(X, _), % Si X est parent d'une autre personne
not(parent(_, X)). % Si aucun parent n'est associé à X
```
3. Le prédicat `couple(X, Y).` qui permet de déterminer si `X` et `Y` ont un/des enfant(s) en commun
```prolog=
% Prédicat de deux personnes qui ont au moins un enfant en commun
couple(X, Y) :-
parent(X, Z), % X a un enfant Z
parent(Y, Z). % Y a un enfant Z
```
**Premier arbre généalogique**
**Deuxième arbre généalogique**
### La fin de la solitude
**1. Donner un ensemble de faits représentant le fichier des candidats.**
```prolog=
personne(id:0001, jean, 165, brun, 23). % définition de jean
personne(id:0002, jeanne, 142, roux, 46). % définition de jeanne
personne(id:0003, henry, 187, blond, 32). % définition de henry
personne(id:0004, paul, 192, blond, 9). % définition de paul
gout(id:0001, rap, theatre, cheval). % gouts de jean
gout(id:0002, rock, classique, football). % gouts de jeanne
gout(id:0003, jazz, roman, basketball). % gouts de henry
gout(id:0004, rap, theatre, cheval). % gouts de paul
recherche(id:0001, 192, blond, 9). % jean recherche
recherche(id:0002, 176, brun, 32). % jeeanne recherche
recherche(id:0003, 146, roux, 19). % henry recherche
recherche(id:0004, 165, brun, 23). % paul recherche
```
**2. Écrire les règles définissant convient-physiquement(X, Y) et ont-memes-gouts(X, Y)**
```prolog=
% Une personne convient aux autre personnes si :
convient-physiquement(X, Y) :- % X une personne, Y une autre
personne(Y, _, T, C, A), % Si Y personne a N gout
recherche(X, T, C, A), % et X recherche N gout
X \== Y. % X différent de Y
% Deux personne ont les mêmes gouts si :
ont-meme-gout(X, Y) :-
gout(X, M, L, S), % X a N gout
gout(Y, M, L, S), % Y a N gout
X \== Y. % X différent de Y
```
**3. En déduire le programme qui détermine les couples assortis.**
```prolog=
% Deux personnes sont considérées en couple si :
est-en-couple(X, Y) :-
ont-meme-gout(X, Y), % Ils ont les mêmes gouts
convient-physiquement(X, Y), % X convient à Y
convient-physiquement(Y, X). % Y convient à X
```
### Attention à ne pas dépasser !
**1. Écrivez un prédicat coloriage(C1, C2, C3, C4) qui comportera deux parties. La première partie génère toutes les valeurs possibles de C1, C2, C3 et C4. La seconde vérifie si les colorations obtenues sont conformes à la carte par l’utilisation du prédicat X \== Y sur les couleurs des zones contiguës.**
```prolog=
couleur(rouge). % rouge est une couleur
couleur(vert). % vert est une couleur
couleur(jaune). % jaune est une couleur
% Coloriage selon le dessin :
coloriage(C1, C2, C3, C4) :-
couleur(C1), % emprunt de couleur en C1 parmi les couleurs définies
couleur(C2), % emprunt de couleur en C2 parmi les couleurs définies
couleur(C3), % emprunt de couleur en C3 parmi les couleurs définies
couleur(C4), % emprunt de couleur en C4 parmi les couleurs définies
C1 \== C2, % C1 doit être différent de C2 (selon le dessin)
C1 \== C3, % C1 doit être différent de C3 (selon le dessin)
C1 \== C4, % C1 doit être différent de C4 (selon le dessin)
C2 \== C3, % C2 doit être différent de C3 (selon le dessin)
C3 \== C4. % C3 doit être différent de C4 (selon le dessin)
```
**2. Reprenez ce prédicat, et modifiez le programme en déplaçant les tests de différence de couleurs le plus tôt possible dans l’écriture du prédicat, c’est-à-dire en vérifiant les différences de couleurs dès que celles-ci sont instanciées. Quelle en est la conséquence ?**
```prolog=
couleur(rouge). % rouge est une couleur
couleur(vert). % vert est une couleur
couleur(jaune). % jaune est une couleur
% Coloriage selon le dessin :
coloriage(C1, C2, C3, C4) :-
C1 \== C2, % C1 doit être différent de C2 (selon le dessin)
C1 \== C3, % C1 doit être différent de C3 (selon le dessin)
C1 \== C4, % C1 doit être différent de C4 (selon le dessin)
C2 \== C3, % C2 doit être différent de C3 (selon le dessin)
C3 \== C4, % C3 doit être différent de C4 (selon le dessin)
couleur(C1), % emprunt de couleur en C1 parmi les couleurs définies
couleur(C2), % emprunt de couleur en C2 parmi les couleurs définies
couleur(C3), % emprunt de couleur en C3 parmi les couleurs définies
couleur(C4). % emprunt de couleur en C4 parmi les couleurs définies
```
> Les différences de couleurs ne sont pas pris en compte, cela est du au choix de la couleur qui est fait après la condition émise. Le prédicat devient donc incorrects.
## Graphes et récursivité
### Introduction
**1. La fonction factorielle. Indice : on peut créer un prédicat `fact(N, R)` où la variable `R` contiendra le résultat de la fonction, un cas de base est `fact(0, 1)`**
```prolog=
% Factoriel de N à 0 des termes :
fact(0, 1). % On pose factoriel de 0 = 1
fact(N, R) :- % N nombre de départ, R le produit factoriel
N > 0, % Si n > 0 (vérification du cas d'arrêt)
N0 is N-1, % On décrément N en N0
fact(N0, R0), % on calcule le factorielle de N0 en R0
R is N * R0. % on écrase la valeur de R en R0
```
**2. La somme des entiers de 1 à n (en utilisant la récursivité !).**
```prolog=
% Somme de X à 0 des termes :
somme(0, 0). % On pose somme de 0 = 0
somme(X, R) :- % X le nombre du début de la somme, R la somme
X > 0, % vérifiaction du cas d'arrêt
X0 is X-1, % On décrément X en X0
somme(X0, R0), % calcul de la somme de X0 en R0
R is R0+X. % R = R0
```
**3. La suite de Fibonacci.**
```prolog=
% Fibonacci de N à 0 des termes :
fibo(N, 1) :- N<2, !. % renvoie 1 si N < 2.
fibo(N, R) :- % N le N terme de la suite, R la somme des termes
N1 is N-1, % on décrément N en N1 (terme à i-1 de la suite)
N2 is N-2, % on décrément N en N2 (terme à i-2 de la suite)
fibo(N1, R1), % calcul du terme en N-1 vers R1
fibo(N2, R2), % calcul du terme en N-2 vers R2
R is R1 + R2. % calcul du termle R par la somme des R1 et R2 (définition de la suite)
```
**2. La fonction d’Ackermann A(m, n), avec m, n entiers positifs, définie par :**
$$A(m,n) = \left\{
\begin{array}{ll}
n+1 & \mbox{si } m=0 \\
A(m-1, 1) & \mbox{si } m>0 \mbox{ et } n=0\\
A(m-1, A(m, n-1)) & \mbox{si } m>0 \mbox{ et } n>0
\end{array}
\right.$$
```prolog=
% Fonction d'ackerman : 3 cas :
% CAS 1 : Si m = 0 on renvoie n+1.
ackerman(0, N, R) :- R is N+1.
% CAS 2 : Si m > 0 et n = 0
ackerman(M, 0, R) :-
M > 0, % vérification du cas en m
M1 is M-1, % m = m-1
ackerman(M1, 1, R). % Calcul de Ackerman en m = m-1 et n = 1
% CAS 3 : Si m > 0 et n > 0
ackerman(M, N, R) :-
M > 0, % vérification du cas en m
N > 0, % vérification du cas en n
M1 is M-1, % m = m-1
N1 is N-1, % n = n-1
ackerman(M, N1, R1), % ackerman en m et n-1
ackerman(M1, R1, R). % ackerman en m-1 et en ackerman de m, n-1
```
### Graphes dirigés acycliques
**1. Écrivez un prédicat `chemin-oriente(X, Y)` qui teste s’il existe un chemin orienté de `X` à `Y` dans le graphe.**
```prolog=
% Prédicat d'un chemin orienté
chemin-oriente(X, Y) :-
arete(X, Y); % Il existe une arete directe entre X et Y
arete(X, Z), % Il existe une arete indirecte entre X et Y
chemin-oriente(Z, Y). % On détermine s'il existe une arete entre Z et Y
```
**2. Modifiez le prédicat `chemin-oriente` pour y ajouter un paramètre `N`. Ainsi, le nouveau prédicat `chemin-oriente(X, Y, N)` testera s’il existe un chemin orienté de `X` à `Y` de taille `N`.**
```prolog=
% Prédicat d'un chemin orienté d'une certaine longueur
chemin-oriente2(X, Y, R):-
arete(X, Y), % Il existe une arete directe entre X et Y
R is 1; % La taille du chemin est alors de 1
arete(X, Z), % Il existe une arete indirecte entre X et Y
chemin-oriente(Z, Y, R1), % On détermine s'il existe une arete entre Z et Y de longueur R1
R is R1+1. % La taille du chemin est alors de R1 + 1
```
**3. Écrivez un prédicat `chemin(X, Y)` qui teste s’il existe un chemin (non-orienté) de `X` à `Y` dans le graphe.**
**Chemin**
```prolog=
% Prédicat d'un lien direct entre deux sommet
lien(X, Y) :-
arete(X, Y); % Il existe une arete directe entre X et Y
arete(Y, X). % Il existe une arete directe entre Y et X
% Prédicat d'un chemin nonorienté entre X et Y
chemin(X, Y) :-
lien(X, Y). % Il existe un lien direct entre X et Y
chemin(X, Y) :-
lien(Z, Y), % Il existe un lien entre Y et un autre point Z
chemin(X, Z). % Il existe un chemin entre X et Z
```
**Connecte**
On écrit d'abord un prédicat `compareSommet(A, B).` qui teste s'il y a un chemin entre un sommet et une liste de sommet donnée
```prolog=
% Prédicat d'un chemin entre un sommet et une liste de sommet
compareSommet(A, [A]). % On considère un chemin entre un sommet et lui même
compareSommet(A, [A|Q]) :-
compareSommet(A, Q). % On passe la comparaison d'un sommet avec lui-même
compareSommet(A, [X]) :-
chemin(A, X). % Cas d'une liste de comparaison d'un seul élément
compareSommet(A, [H|Q]) :-
chemin(A, H), % On cherche un chemin entre A et H
compareSommet(A, Q). % On cherche un chemin entre A et les sommets restants
```
On écrit ensuite un prédicat `compareListes(A, B).` qui teste chaque sommet d'une liste donnée est connecté avec tous les autres sommets d'une seconde liste
```prolog=
% Prédicat d'un chemin entre chaque sommet d'une liste et une liste de sommet
compareListes([X], L1) :-
compareSommet(X, L1). % Cas d'une liste d'un seul élément
compareListes([H|Q], L1) :-
compareSommet(H, L1), % Il existe un chemin entre H et chaque sommets de L1
compareListes(Q, L1). % Il existe un chemin entre chaque points de Q et chaque sommets de L1
```
Enfin la prédicat `connecte(A).` correspond à tester le prédicat `compareListes(A, B).` sur une même liste de sommets.
```prolog=
% Prédicat d'une liste de sommets connectés
connecte(L) :- compareListes(L, L). % Test de compareListes/2 sur la liste donné
```
## Listes et languages
### Introduction
**1. Résultat de la ligne `[X | Y] = [a, b, c, d].`**
| X = a |
| -------- |
| Y = [b, c, d] |
> X est la tête de la liste, Y est le corps.
**2. Résultat de la ligne `[X] = [a, b, c, d].`**
> Le retour obtenu est false. Cela vient du fait que l'on associe une seule variable `X` à une liste qui contient 4 éléments. Une variable ne peut pas être égale à quatre autres.
### Opérations sur les listes
**1. Donner le code du prédicat `head(X, L)` qui renvoie le premier élément de la liste L.**
```prolog=
head(X, [X|_]). % X prend la valeur de la tête de liste
```
**2. Coder `addhead(X, L, L1)` , le prédicat qui ajoute un élément X au début de la liste L.**
```prolog=
addhead(X, L, [X | L]). % On ajoute X à une liste L en le plaçant en tête de liste
```
**3. Coder le prédicat last(X, L), qui renvoie le dernier élément de la liste L**
```prolog=
last(X, [X]). % Si liste ne contient q'un élément, c'est cet élément qui est renvoyé
last(X, [_ | Q]) :- last(X, Q). % Parcours la liste en effaçant la tête à chaque fois
```
**4. Exécutez la ligne suivante : `addlast(e, [a,b,c,d], Resultat)`. Que se passe-t-il ? Quel est le problème à votre avis ? Corrigez le prédicat en fonction de vos observations.**
```prolog=
addlast(X, [], [X]). % ajoute X à une liste vide pour obtenir une liste de cet élément
addlast(X, [H | Q], [H | W]) :- addlast(X, Q, W). % Enleve la même tête à chaque liste, et parcours tant qu'elle est vide jusqu'au cas d'arrêt.
```
**5. Enfin, on souhaiterait retourner la liste, par exemple transformer la liste `[a, b, c, d]` en `[d, c, b, a]`. Écrire le prédicat `reverse(L, L1)` correspondant.**
```prolog=
reverse([X], [X]). % l'inverse d'une liste d'un élément est la liste elle-même
reverse([H | Q], L1) :- % renvoie L1 liste inverse
reverse(L, Q), % Inverse la queue de liste vers L
addlast(H, L, L1). % ajoute la tête enlevée à L qui devient L1
```
## Construction inductive et langages
Nous utiliserons ces fonctions pour construire les langages en prolog :
```prolog=
head(X, [X|_]). % X prend la valeur de la tête de liste
addlast(X, [], [X]). % ajoute X à une liste vide pour obtenir une liste de cet élément
addlast(X, [H | Q], [H | W]) :- addlast(X, Q, W). % Enleve la même tête à chaque liste, et parcours tant qu'elle est vide jusqu'au cas d'arrêt.
```
### Langage 1 : a<sup>n</sup>b
On note L$_{1}$ le langage.
**BASE**
Le mot z = "b" appartient à L$_{1}$
> b $\in$ L$_{1}$
**INDUCTION**
> S $\in$ L$_{1}$ $\to$ aS $\in$ L$_{1}$
**CODE PROLOG**
```prolog=
% langage 1 : a^nb
langage1([b]). % Base : b est seul dans la liste, il appartient au langage 1
langage1([a | S]) :- langage1(S). % Induction : Si S appartient à langage 1 aS appartient au langage 1
```
### Langage 2 : ab$^n$
On note L$_{2}$ le langage.
**BASE**
Le mot z = "a" appartient à L$_{2}$
> a $\in$ L$_{2}$
**INDUCTION**
> S $\in$ L$_{2}$ $\to$ Sb $\in$ L$_{2}$
**CODE PROLOG**
```prolog=
% langage 2 : ab^n
langage2([a]). % Base : a est seul dans la liste, il appartient au langage 2
langage2([a, b | S]) :- langage2([a | S]). % Induction : Si aS appartient à langage 2 abS appartient au langage 2
```
### Langage 3 : a<sup>n</sup>b<sup>m</sup>
On note L$_{3}$ le langage.
**BASE**
Le mot vide z appartient à L$_{2}$
> z $\in$ L$_{3}$
**INDUCTION**
> S $\in$ L$_{3}$ $\wedge$ T $\in$ L$_{3}$ $\to$ aS $\cup$ Tb $\in$ L$_{3}$
**CODE PROLOG**
```prolog=
% langage 3 : a^nb^m
% BASE :
langage3([]). % élément vide appartient au langage 3
langage3([a]). % a est seul dans la liste, il appartient au langage 3
langage3([b]). % b est seul dans la liste, il appartient au langage 3
langage3([a, b]). % ab appartient au langage 3
% INDUCTION :
langage3([a, a | S]) :- langage3([a | S]). % Si aS appartient à langage 3 aaS appartient au langage 3
langage3([b, b | S]) :- langage3([b | S]). % Si bS appartient à langage 3 bbS appartient au langage 3
langage3([a, b, b | S]) :- langage3([a, b | S]). % Si abS appartient à langage 3 abbS appartient au langage 3
```
### Langage 4 : a<sup>2n</sup>
On note L$_{4}$ le langage.
**BASE**
Le mot vide z appartient à L$_{4}$
> z $\in$ L4
**INDUCTION**
> S $\in$ L$_{4}$ $\to$ aaS $\in$ L$_{4}$
**CODE PROLOG**
```prolog=
% langage 4 : a^2n
langage4([]). % Base : élément vide appartient au langage 4
langage4([a, a | S]) :- langage4(S). % Induction : Si S appartient à langage 4 aaS appartient au langage 4
```
### Langage 5 : a<sup>n</sup>b<sup>n</sup>
On note L$_{5}$ le langage.
**BASE**
Le mot vide z appartient à L$_{5}$
> z $\in$ L$_{5}$
**INDUCTION**
> S $\in$ L$_{5}$ $\to$ aSb $\in$ L$_{5}$
**CODE PROLOG**
```prolog=
% langage 5 : a^nb^n
langage5([]). % Base : élément vide appartient au langage 5
langage5([a | S]) :- addlast5(b, L, S), langage5(L). % Induction : Si Sb appartient à langage 5 aS appartient au langage 5
```
### Langage 6 : mots palindromes sur {a, b}
On note L$_{6}$ le langage.
**BASE**
Le mot vide z appartient à L$_{6}$
> z $\in$ L6
Le mot "a" appartient à L$_{6}$
> a $\in$ L6
Le mot "b" appartient à L$_{6}$
> b $\in$ L6
**INDUCTION**
> S $\in$ L$_{6}$ $\to$ aSa $\in$ L$_{6}$
> S $\in$ L$_{6}$ $\to$ bSb $\in$ L$_{6}$
**CODE PROLOG**
```prolog=
addlast(X, [], [X]).
addlast(X, [H | Q], [H | W]) :- addlast(X, Q, W).
% langage 6 : palindrome sur {a, b}
langage6([]). % Base : élément vide est un palindrome
langage6([H | Q]) :- % Induction :
(H == a; H == b), % Si aS ou bS appartient à langage 6
addlast(H, L, Q), % Sa ou Sb
langage6(L). % appartient à langage 6
```
### Langage 7 : a$^l$b$^m$c$^n$
On note L$_{7}$ le langage.
**BASE**
Le mot vide z appartient à L$_{7}$
> z $\in$ L$_7$
**INDUCTION**
> S $\in$ L$_{7}$ $\to$ aS $\in$ L$_{7}$
> S $\in$ L$_{7}$ $\to$ Sc $\in$ L$_{7}$
> a$^l$b$^{m-1}$c$^n$ $\in$ L$_{7}$ $\to$ a$^l$b$^m$c$^n$ $\in$ L$_{7}$
**CODE PROLOG**
```prolog=
% langage 7 : a^lb^mc^n
% Base :
langage7([b]). % b appartient au langage 7
% Induction :
langage7(L) :- addlast(c,L2,L), langage7(L2). % Si Sc appartient à langage 7 S appartient au langage 7
langage7([b|Q]) :- head(b, Q), langage7(Q). % Si bS appartient à langage 7 bbS appartient au langage 7
langage7([a|Q]) :- langage7(Q). % Si S appartient à langage 7 aS appartient au langage 7
```
### Langage 8 : a$^m$b$^n$c$^m$
On note L$_8$ le langage.
**BASE**
Le mot vide z appartient à L$_{8}$
> z $\in$ L$_8$
**INDUCTION**
> S $\in$ L$_{8}$ $\to$ aSc $\in$ L$_{8}$
> a$^m$b$^{n-1}$c$^m$ $\in$ L$_{8}$ $\to$ a$^m$b$^n$c$^m$ $\in$ L$_{8}$
**CODE PROLOG**
```prolog=
% langage 8 : a^mb^nc^m
% Base :
langage8([]). % élément vide appartient au langage 8
% Induction :
langage8(S) :- addlast(c,[a|S1],S), langage8(S1). % Si aSc appartient à langage 7 S appartient au langage 7
langage8([b|S]) :- head(b,S), langage8(S). % Si bS appartient à langage 7 bbS appartient au langage 7
```
### Langage 9 : 1 ou 0 fois b dans le mot
On note L$_9$ le langage.
**BASE**
Le mot vide z appartient à L$_{9}$
> z $\in$ L$_9$
**INDUCTION**
> a$^m$b$^0$a$^n$ $\in$ L$_{9}$ $\to$ a$^m$ba$^n$ $\in$ L$_{9}$
> a$^{m-1}$ba$^n$ $\in$ L$_{9}$ $\to$ a$^m$ba$^n$ $\in$ L$_{9}$
> a$^m$ba$^{n-1}$ $\in$ L$_{9}$ $\to$ a$^m$ba$^n$ $\in$ L$_{9}$
**CODE PROLOG**
```prolog=
% langage 9 : Au plus un b sur {a, b}
% Compte le nombre de b dans le mot
compteb([], 0). % élément vide renvoie 0 b
compteb([H | Q], XB) :- % Si la tête est B on incrémente XB et on relance compteb sur la queue de liste
H == b,
compteb(Q, XB1),
XB is XB1+1.
compteb([H | Q], XB) :- % Si la tête n'est pas b on incrémente pas XB mais on relance compteb sur la queue de liste
H == a,
compteb(Q, XB1),
XB is XB1.
% Base :
langage9([]). % Le mot vide ne contient aucun b il appartient à langage 9
% Induction :
langage9(L) :- compteb(L, X), X < 2. % L appartient à langage 9 si compteb renvoie X < 2 (1 ou 0)
```
### Langage 10 : autant de a que de b sur {a, b}
On note L$_{10}$ le langage.
**BASE**
Le mot vide z appartient à L$_{10}$
> z $\in$ L$_{10}$
**INDUCTION**
> S $\in$ L$_{10}$ $\to$ aSb $\in$ L$_{10}$
> S $\in$ L$_{10}$ $\to$ bSa $\in$ L$_{10}$
> S $\in$ L$_{10}$ $\wedge$ T $\in$ L$_{10}$ $\to$ S $\cup$ T $\in$ L$_{10}$
**CODE PROLOG**
```prolog=
% langage 10 : Autant de a que de b
compte([], 0, 0). % liste vide : aucun a et aucun b
% Définition basé sur compteb juste au dessus
compte([H | Q], XA, XB) :- % compte les a
H == a, % Si tête de liste est a
compte(Q, XA1, XB1), % compte les a et b sur la queue de liste
XA is XA1+1, % XA est XA1 incrémentéde 1.
XB is XB1. % XB est XB1 reste le même.
compte([H | Q], XA, XB) :- % compte les b
H == b, % Si tête de liste est b
compte(Q, XA1, XB1), % compte les a et b sur la queue de liste
XA is XA1, % XA est XA1 reste le même.
XB is XB1+1. % XB est XB1 incrémentéde 1.
% Base & Induction :
langage10(L) :- compte(L, X1, X2), X1 == X2. % Vrai si X1 = X2 (autant de a que de b)
```
### Langage 11 : a$^n$b$^n$c$^n$
On note L$_{10}$ le langage.
**BASE**
Le mot vide z appartient à L$_{10}$
> z $\in$ L$_{10}$
**INDUCTION**
> a$^{n-1}$b$^{n-1}$c$^{n-1}$ $\in$ L$_{7}$ $\to$ a$^n$b$^n$c$^n$ $\in$ L$_{7}$
**CODE PROLOG**
```prolog=
% langage 11 : a^nb^nc^n
% l_count : même principe que compte juste au dessus mais avec c en plus
l_count([], 0, 0, 0). % liste vide : aucun a, aucun b et aucun c
l_count([a|Q], CountA, CountB, CountC) :- % Si a en tête de liste = compteur en A incrémenté.
l_count(Q, CountA1, CountB, CountC),
CountA is CountA1+1.
l_count([b|Q], CountA, CountB, CountC) :- % Si b en tête de liste = compteur en Bincrémenté.
l_count(Q, CountA, CountB1, CountC),
CountB is CountB1+1.
l_count([c|Q], CountA, CountB, CountC) :- % Si c en tête de liste = compteur en C incrémenté.
l_count(Q, CountA, CountB, CountC1),
CountC is CountC1+1.
p(M):- l_count(M, N, N, N). % Vrai si autant de a que de b que de c.
langage11([]). % Base : Element vide appartient à langage 11
langage11(L):- langage8(L), p(L). % Induction : Induction de langage 8 + même nombre de a que de b que de c
```
Google Drive
Gist
Clipboard
Sign in with Wallet
