My favorites | Sign in
Project Home Downloads Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
EliminerConj  

Elimination des Conjonctions

Dans la procédure de traitement d'un changement de grammaire, nous allons chercher à éliminer les conjonctions, afin de tenter de simplifier voire évaluer une proposition écrite selon la grammaire Pos. Durant le traitement, nous allons devoir déterminer, pour 2 ensembles X et Y, le produit cartésien X x Y = Z puis l'ensemble des parties de ce produit P(Z), selon la relation binaire (a, b). Ainsi nous aurons un ensemble d'ensemble d'éléments de la forme (a, b), avec a appartenant à X, b à Y. Par exemple, et pour fixer les idées, supposons que

X =  { a , d } et Y = { e , f }

Alors

Z = X x Y = {(a,e) , (a,f ) , (d,e) , (d,f) }.

Et P(Z), l'ensemble des parties de Z :

P(Z) = { { (a,e) } , { (a,f) }, { (d,e) }, { (d,f) }, { (a,e), (a,f) }, { (a,e), (d,e) } , { (a,e) , (d,f) } , { (a,f) , (d,e) }, 

{ (a,f) , (d,f) }, { (d,e) , (d,f) }, { (a,e) , (a,f ) , (d,e) } , {(a,e) , (d,e) , (d,f) }, {(a,f) , (d,e) , (d,f) } , Z , Ø },

soit l'ensemble des combinaisons d'éléments, à permutation près.

Ensuite, nous allons chercher l'ensemble des éléments de P(Z) qui satisfassent la proposition (P) suivante :

Pour tout C, ensemble de relations binaires (a,b) de P(Z),

Pour tout a appartenant à X, il existe b appartenant à Y tel que (a,b) appartient à C
et
Pour tout b appartenant à Y, il existe a appartenant à X tel que (a, b) appartient à C

Nous considérons les 2 grammaires suivantes :

La grammaire Pos

où x est une variable propositionnelle, et a un programme.

La grammaire Nab

où x est une variable propositionnelle, et a un programme.

Fonctions d'éliminations des conjonctions :


val prodCart : 'a list -> 'b list -> ('a * 'b) list
renvoie une liste comportant le produit cartésien des deux listes d'éléments passés en paramètre. Cette fonction est récursive.
val list_length : 'a list -> int
renvoie le cardinal de la liste. Cette fonction est récursive.
val groupe_2 : 'a list -> 'a list list
renvoie l'ensemble des groupes d'arité 2 de la liste. Cette fonction est tail-récursive.
val groupe_3 : 'a list -> 'a list list 
renvoie l'ensemble des groupes d'arité 3 de la liste. Cette fonction est tail-récursive.
val monom : 'a list -> 'a list list
renvoie l'ensemble des groupes d'arité 1 de la liste. Cette fonction est récursive.
val distr_liste: 'a list -> 'a list list -> 'a list list
distribue la liste simple à tous les éléments de la liste de liste. Cette fonction est récursive.
val efface_doublon : 'a list list -> 'a list list
élimine les listes qui possèdent un élément en double.

Fonctions développées :


proCart

let rec prodCart x y = 
	let rec distr p liste = match liste with [] -> []
					| r::t -> (p,r)::distr p t
	in match x with [] -> []
		| p::q -> (distr p y)@(prodCart q y)
;;

monom

let rec monom liste = match liste with 
	  [] -> []
	| t::q -> [t]::monom q;;

list_length

let rec list_length = function
			| [ ] -> 0
			| _::q -> 1 + list_length q ;;

groupe_2

let rec groupe_2 t = match t with [] -> []
			| p :: q ->
				let fold acc elt = [p; elt] :: acc in
			List.fold_left fold (groupe_2 q) (List.rev q);;

groupe_3

let rec groupe_3 t = match t with [] -> []
			|p :: q -> let fold acc elt = [p;List.hd q ; elt]:: acc in
			List.fold_left fold (groupe_3 q) (List.rev q);;

distr_liste

let rec distr_liste a liste_new = match liste_new with
	  [] -> []
	| t::q -> (a@t)::(distr_liste a q);;

efface_doublon

let efface_doublon liste = let rec doublon liste = 
						let rec doublon_membre a liste = match liste with [] -> true
						|t ::q -> if(t = a) then false else true && doublon_membre a q  
					
					in
					match liste with [] -> true
					| t ::q -> doublon_membre t q && doublon q 
				in
				match liste with [] -> []
					|p -> List.filter doublon p;;

Explication des fonctions :


La fonction distr_liste prend une liste d'éléments [a1,...,an] et une liste de liste d'éléments [ [b11;...;b1n]; [b21;...;b2n];...;[bn1;...;bnn] ] en paramètre, puis distribue la liste d'éléments à la liste de liste de manière à ce que nous ayons en sortie : [[a1;...;an;b11;...;b1n]; [a1;...;an;b21;...;b2n];...;[a1;...;an;bn1;...;bnn]]. Cette fonction est nécessaire dans la création du produit cartésien entre 2 ensembles d'élements. Cette fonction est récursive.

Sa complexité est estimée à O(2n).

La fonction prodCart prend 2 listes en paramètre et renvoie une liste comportant le produit cartésien des paramètres. La fonction fait référence à la fonction distr de cette façon : la première liste est décortiquée de manière à ce que chacun de ses éléments soit distribué à tous les éléments de la seconde liste. L'utilisation de la fonction distr s'opère dans la distribution des éléments, c'est une version simplifiée de distr_liste. Cette fonction est récursive.

Sa complexité est estimée à O(2n).

La fonction monom créé une liste de liste d'éléments, comportant l'ensemble des monômes de la liste [a1;...;an] passée en paramètre. Ainsi, nous aurons en sortie : [[a1];[a2];...;[an]]. Cette fonction est récursive.

Sa compléxité est estimée à O(2n).

Les fonctions groupe_2, groupe_3 utilisent le même principe que la fonction monom, mais pour les groupes d'arités respectivement deux et trois. Elles prennent chacune en paramètre une liste de la forme [a1;...;an] et crééent respectivement [ [a1;a2];[a1;a3];...;[a1;an];[a2;a3];...;[an-1;an] ] et [ [a1;a2;a3] ; [a1;a2;a4]; ... ;[a1;a2;an];[a2;a3;a4];...;[an-2;an-1;an] ], les listes de listes d'éléments d'arités respectivement deux et trois. Cette fonction est tail-récursive.

Sa complexité est estimée à O(n2).

La fonction list_length permet de compter le nombre d'éléments d'une liste, et donc de renvoyer son cardinal. Elle est récursive.

Sa complexité est estimée à O(2n).

La fonction efface_doublon est une fonction de nettoyage que l'utilisateur applique généralement après avoir utilisé les fonctions permettant de créer l'ensemble des parties du produit cartésien de deux éléments. Elle va tout d'abord créer une fonction temporaire permettant de créer un prédicat sur l'existence d'un élément en double. Ensuite, la fonction efface_doublon utilise la fonction List.filter à ce prédicat de chaque élément de la liste. La fonction fait appel à des fonctions récursives.

Sa complexité est estimée à O(2n).

Améliorations possibles :


Cette partie n'est pas terminée. Il reste alors à coder la fonction permettant de créer l'ensemble des parties du produit cartésien, pour deux groupes d'éléments de taille respectivement n et m. Ensuite, il reste à coder la fonction qui vérifie la proposition (P). Ce traitement permettra de transformer une conjonction de nabla en conjonction de propositions du premier ordre. Enfin, il nous reste à simplifier voire évaluer ses propositions, selon les possibilités et les éléments mis en place.

Powered by Google Project Hosting