Simplification logique

[fatal_error]

hello,

suite à http://www.maths-forum.com/question-logique-153105.php
qui soulève (en tout cas pour moi) un peu d'intérêt:

Créer un algorithme qui permette à partir d'une fonction booléenne, de simplifier son expression.
Par simplifier l'expression, j'entends terminer avec le moins de termes possibles (et pas de groupe parenthésé...)

Bien sûr, un karnaugh suffirait pour arriver à la fin.
Le but ici, c'est de pouvoir simplifier l'expression à l'aide des règles de base:
not(not(a))=a
not(a)+a=1
not(ab)=not(a)+not(b)
not(a+b)=not(a)not(b)
not(a)b+a=b
1a=a
0a=0
et éventuellement d'autres règles simples tel que multiplier par (a+b+c)


ex:

Code: Tout sélectionner

f(a,b,c)=abnot(c)+not(b)not(c)a+c
f(a,b,c)=anot(c)(b+not(b))+c
f(a,b,c)=anot(c)1+c                       //application x+not(x)=1
f(a,b,c)=anot(c)+c                        //application a1=a
f(a,b,c)=a                                //application not(a)b+a=b

[Ben314]

Salut,
Un truc assez classique qui ne "simplifie" pas forcément l'expression, mais qui permet d'aboutir à une forme "standard" (et donc de vérifier facilement si deux expresions sont équivalentes), c'est d'utliser les notations correspondant à l'algèbre de boole où + désigne le ou exclusif (qui, contrairement au ou inclusif, a le bon gout de donner une structure de groupe avec pour neutre 0="faux" et comme "opposé" d'une proposition P la proposition P elle même).
La multiplication . désigne quand à elle le "et".
Pour le codage partant des connecteurs usuels ET, OU en NON, c'est totalement mécanique :
non(P) -> 1+P
P et Q -> PQ
P ou Q -> P+Q+PQ = 1+(1+P)(1+Q) (c'est à dire non[non(P) et non(Q)] )

Avec ça comme notation, on n'a pas besoin d'autre chose vu que la négation de P devient 1+P (ou 1="vrai") et les "règles de calculs" sont précisément celle d'une algèbre sur Z/2Z, c'est à dire les même règles que le + et le x sur R plus la règle P+P=0 et rien d'autre.

De mémoire, si on utilise cette notation, qu'on développe totalement l'expression de base (ici on ne peut distribuer que le x sur le + et pas le contraire) et qu'on simplifie les "doublons" (i.e. P.Q.R+P.Q.R=0 par exemple), on obtient une forme "unique" de la proposition.

[fatal_error]

hello ben,

pas mal la méthode, j'ai l'impression qu'elle donne toujours l'expression la plus simplifiée, (notamment grace a la propriété p o p=0, o le ou exclusif) qui empêche les propositions de se "duppliquer".

Au final, il reste à remonter à partir de l'expression avec les ou exclusif vers les not, ET et OU
Puis pour les termes qu'on a pas réussi à remonter, par exemple
PoQoR (le o étant donc le ou exclusif)

(PoQ)oR=[ not(P)Q+not(Q)P ] o R = not(not(P)Q...)R + not(R)(not(P)...)
Or en simplifiant la dernière on a pas de termes qui se recouvrent, sinon ils auraient pété dans la forme simplifiée. Ca reste complètement flou pour la preuve, mais je pense que ca se tient...

A l'algo donc :D