Version imprimable
Bonsoir,
Je cherche à simplifier cette équation (algèbre booléenne) :
X = (b + bc)(b + (¬b)c)(b + d)
Le résultat donne X = b, cependant, je n'arrive pas à trouver les simplifications qui sont faites pour arriver à ce résultat... Quelqu'un pour m'aider ?
Merci, très bonne soirée,
Metallic-84s
Cette simplification vient probablement d'un diagramme de karnaugh.
Tu trouveras ton bonheur sur cette page:
http://villemin.gerard.free.fr/LogForm/Integram.htm
Les multiplications sont des 'et' logiques, les additions des 'ou' c'est bien ça?
Finalement, pas simple avec Karnaugh, mais avec les expressions ici:
http://fr.wikipedia.org/wiki/Alg%C3%A8bre_de_Boole_(logique)
b+bc = b(1+c) = bCitation:
Envoyé par Metallic-84s
b(b+x) = b+bx = b
A c'est bien ce qui me semblait:
1+a = 1
1.a = a
Si tu veux t'en convaincre, fait les tables de vérité. Tu verras mieux les simplifications.
le probleme général de la simplification des expressions booléennes est compliqué, il doit etre NP-complet je pense...
ce que tu peux faire assez facilement et systematiquement c'est te ramener à une forme normale conjonctive ou disjonctive...
Dans ton probleme je pense plutot que ce que tu veux c'est effectuer des opérations basiques de simplification à partir d'une expression, et avec de la chance ça te donnera une expression simplifiée.
Tu peux alors décider de factoriser à chaque fois qu'une variable apparait dans tous les termes d'une somme.
Ensuite en appliquant effectivement les regles 1+x = 1, 1.x = x , x.x = x, tu devrais deja obtenir pas mal de simplifications.
L'algo serait donc un simple parcours récursif d'arbre, en faisant du matching sur la regle à appliquer (je sais pas si je suis clair là...)
Hum Karnaug ça marche bien, je viens de le faire...
En plus c'est rapide.
hm mes souvenirs sont assez vagues la dessus j'avoue, mais il me semble que Karnaugh est pas en temps polynomial... ça revient à essayer toutes les valeurs non?
Effectivement pour Karnaugh il faut faire toute la table.
Pfiou, je suis plus capable de faire un tableau de Karnaugh moi.
Si Qqun veut bien poster la table :)
Code:
2
3
4
5
6bc bc bc bc 00 01 11 10 ------ d 0 F F |V V| d 1 F F |V V| ------
La taille des tables de Karnaugh est exponentielle en le nombre de variables (si on a n variables, il faut 2^n entrees dans les tables).
Une des techniques utilisees en pratique, c'est les BDD (Binary Decision Diagram) et leurs variantes (ZBDD entres autres). Un optimiseur booleen plus ancien c'est espresso dont le code doit toujours se trouver sur le web.