On définit les expressions booléennes généralisées par la grammaire :
| <expBoolGen> |
-> |
<atomique> |
| |
|
<négation> |
| |
|
<n-aire> |
| |
|
|
| <atomique> |
-> |
<constante>
|
| |
|
<variable>
|
| |
|
|
| <constante> |
-> |
@v |
vrai
|
| |
|
@f |
faux
|
| |
|
|
| <variable> |
-> |
Une suite de caractères autres que l'espace, les parenthèses et @ |
| |
|
|
| <négation> |
-> |
(@non <expBoolGen> )
|
| |
|
|
| <n-aire> |
-> |
(@et <expBoolGen>*)
|
conjonction
|
| |
|
(@ou <expBoolGen>*)
|
disjonction
|
| |
|
|
comme en Scheme, les disjonctions et les
conjonctions opèrent sur un nombre quelconque d'arguments, y compris 1
argument ou même 0 argument.
(@et (@non (@et @v a)) (@ou b (@et @v a)))
(@ou a)
(@ou)
Lorsqu'il y a un argument, la sémantique va de soi: la valeur de
vérité d'une conjonction ou d'une disjonction n'ayant qu'une
sous-expression est égale à la valeur de vérité de la sous-expression.
La valeur de vérité d'une disjonction sans argument est « faux » et la
valeur de vérité d'une conjonction sans argument est « vrai ».
;;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;;
;;;
;;;
;;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
;;;
Exactement comme pour les expressions booléennes simples:
;;;
;;;
;;;
Exemples :
(ebg-exp-const-val '(@et (@ou @v @f @f) (@non @f) @v)) ->
VRAI
(ebg-exp-const-val '(@et (@ou @v @f @f) (@non @f) @v (@et @v @f))) ->
FAUX
Comme d'habitude, le schéma de la définition suit la grammaire:
(define (ebg-exp-const-val exp)
(cond ((ebg-atomique? exp)
... à faire
... à faire
... à faire
... à faire
... à faire
((ebg-negation? exp)
... à faire
((ebg-conjonction? exp)
... à faire
((ebg-disjonction? exp)
... à faire
(else (erreur 'ebg-exp-const-val
"mal formée ou non constante"))))
pour les constantes et les négations, on fait comme pour les expressions
simples:
(define (ebg-exp-const-val exp)
(cond ((ebg-atomique? exp)
(if (ebg-constante? exp)
(if (ebg-constante-vrai? exp)
(vrai)
(faux))
(erreur 'ebg-exp-const-val exp " est une variable")))
((ebg-negation? exp)
(non (ebg-exp-const-val (ebg-neg-sous-exp exp))))
((ebg-conjonction? exp)
... à faire
((ebg-disjonction? exp)
... à faire
(else (erreur 'ebg-exp-const-val
"mal formée ou non constante"))))
En revanche, les conjonctions et les disjonctions ne peuvent
pas être traitées comme dans le cas des expressions simples puisque
l'on peut avoir un nombre quelconque de sous-expressions.
Calculer la valeur d'une conjonction paraît compliqué: nous spécifions
(et nous implanterons) une fonction pour le faire:
(define (ebg-exp-const-val exp)
(cond ((ebg-atomique? exp)
(if (ebg-constante? exp)
(if (ebg-constante-vrai? exp)
(vrai)
(faux))
(erreur 'ebg-exp-const-val exp " est une variable")))
((ebg-negation? exp)
(non (ebg-exp-const-val (ebg-neg-sous-exp exp))))
((ebg-conjonction? exp)
(ebg-conjonction-const-val (ebg-n-aire-sous-exps exp)))
((ebg-disjonction? exp)
... à faire
(else (erreur 'ebg-exp-const-val
"mal formée ou non constante"))))
;;;
;;;
;;;
;;;
Noter que la donnée de la fonction
ebg-conjonction-const-val est
une liste d'expressions et, lors de son application dans
ebg-exp-const-val, elle est appelée avec la liste des
sous-expressions de l'expression donnée.
On agit de même pour les disjonctions:
(define (ebg-exp-const-val exp)
(cond ((ebg-atomique? exp)
(if (ebg-constante? exp)
(if (ebg-constante-vrai? exp)
(vrai)
(faux))
(erreur 'ebg-exp-const-val exp " est une variable")))
((ebg-negation? exp)
(non (ebg-exp-const-val (ebg-neg-sous-exp exp))))
((ebg-conjonction? exp)
(ebg-conjonction-const-val (ebg-n-aire-sous-exps exp)))
((ebg-disjonction? exp)
(ebg-disjonction-const-val (ebg-n-aire-sous-exps exp)))
(else (erreur 'ebg-exp-const-val
"mal formée ou non constante"))))
;;;
;;;
;;;
;;;
Rappelons la spécification:
;;;
;;;
;;;
;;;
La donnée de cette fonction étant une liste, on suit le schéma sur les
listes:
(define (ebg-conjonction-const-val exps)
(if (pair? exps)
;
... à faire
... à faire
;
)
Comme nous l'avons dit plus haut, la valeur de la conjonction d'une
liste d'expressions vide est
VRAI:
(define (ebg-conjonction-const-val exps)
(if (pair? exps)
;
... à faire
... à faire
(vrai))
)
Lorsque la liste n'est pas vide, la valeur de vérité de la conjonction
de ses éléments est égale à la conjonction (binaire) de la valeur de
vérité de son premier élément et de la valeur de vérité de la
conjonction (généralisée) de ses autres éléments. On pourait donc
utiliser la fonction
et, mais, pour des raisons d'efficacité,
on préfère calculer la conjonction binaire à l'aide d'une alternative:
(define (ebg-conjonction-const-val exps)
(if (pair? exps)
(if (vrai? (ebg-exp-const-val (car exps)))
(ebg-conjonction-const-val (cdr exps))
(faux))
(vrai)))
Remarque: nous pourrions aussi écrire la définition suivante:
(define (ebg-conjonction-const-val exps)
(reduce et (vrai) (map ebg-exp-const-val exps)))
Nous avons préféré la version donnée ci-dessus car elle est plus
efficace. En effet, dans cette version, dès qu'une sous-expression
est fausse, on ne calcule pas la valeur de vérité des autres
sous-expressions alors que dans la version avec
map et
reduce, on calcule toujours la valeur de vérité de toutes les
sous-expressions.
Laissée en exercice.
Exactement comme pour les expressions simples:
;;;
;;;
;;;
;;;
Exemples:
(ebg-exp-simplifiee '(@et @v a b))
->
(@et a b)
(ebg-exp-simplifiee '(@et (@non (@et @v a)) (@ou b (@et @v a))))
->
(@et (@non a) (@ou b a))
Encore une fois, nous suivons le même schéma:
(define (ebg-exp-simplifiee exp)
(cond
((ebg-atomique? exp)
... à faire
((ebg-negation? exp)
... à faire
((ebg-conjonction? exp)
... à faire
... à faire
((ebg-disjonction? exp)
... à faire
... à faire
(else (erreur 'ebg-exp-simplifiee "expression mal formée"))))
Comme pour les expressions simples, la simplifiée d'une expression
atomique est égale à elle-même:
(define (ebg-exp-simplifiee exp)
(cond
((ebg-atomique? exp)
exp)
((ebg-negation? exp)
... à faire
((ebg-conjonction? exp)
... à faire
... à faire
((ebg-disjonction? exp)
... à faire
... à faire
(else (erreur 'ebg-exp-simplifiee "expression mal formée"))))
les négations se traitent
exactement comme dans le cas des expressions simples, aussi nous ne
les revoyons pas:
(define (ebg-exp-simplifiee exp)
(cond
((ebg-atomique? exp)
exp)
((ebg-negation? exp)
(ebg-neg-simpl (ebg-exp-simplifiee (ebg-neg-sous-exp exp))))
((ebg-conjonction? exp)
... à faire
... à faire
((ebg-disjonction? exp)
... à faire
... à faire
(else (erreur 'ebg-exp-simplifiee "expression mal formée"))))
Pour les conjonctions (et il en va de même pour les disjonctions) on
doit effectuer une opération de simplification sur les simplifiées de
toutes les sous-expressions. Pour avoir la liste des simplifiées de
toutes les sous-expressions, il suffit de « maper » la fonction
ebg-exp-simplifiee sur la liste des sous-expressions:
(define (ebg-exp-simplifiee exp)
(cond
((ebg-atomique? exp)
exp)
((ebg-negation? exp)
(ebg-neg-simpl (ebg-exp-simplifiee (ebg-neg-sous-exp exp))))
((ebg-conjonction? exp)
(ebg-conj-simpl (map ebg-exp-simplifiee
(ebg-n-aire-sous-exps exp))))
((ebg-disjonction? exp)
(ebg-disj-simpl (map ebg-exp-simplifiee
(ebg-n-aire-sous-exps exp))))
(else (erreur 'ebg-exp-simplifiee "expression mal formée"))))
la fonction
ebg-conj-simpl ayant comme spécification:
;;;
;;;
;;;
(Le cas de la disjonction est similaire, nous ne le traiterons pas)
Comment peut-on simplifier une conjonction?
-
si une des sous-expressions est fausse, l'expression est fausse,
- on peut supprimer toutes les sous-expressions vraies,
- une conjonction sans sous-expressions est vraie,
- une conjonction ayant une seule sous-expression est équivalente
à cette sous-expression.
D'où l'implantation de
ebg-conj-simpl:
(define (ebg-conj-simpl exps)
(if (member (ebg-constante-faux) exps)
(ebg-constante-faux)
(let ((exps-simp (ebg-liste-sans (ebg-constante-vrai) exps)))
(if (pair? exps-simp)
(if (pair? (cdr exps-simp))
(ebg-conjonction exps-simp)
(car exps-simp))
(ebg-constante-vrai)))))
la fonction
ebg-liste-sans ayant comme spécification:
;;;
;;;
L'implantation de cette fonction, simple exercice sur les listes,
est laissée en exercice (on pourra utiliser la fonction
filtre).
