Forme normale disjonctive simplifiée

Raskolnikov

Bonjour,
on demande souvent dans les exercices (calcul propositionnel) l'obtention d'une forme normale disjonctive la plus réduite possible.
Comment s'assure-t-on qu'on ne peut plus simplifier ou, en tout cas, quelle est l'idée générale ? J'ai lu que les vérifications pouvaient être fastidieuses dans certains cas.

christophe c

Impossible de t'aider sans un exemple de forme normale réduite disjonctive dont tu crains qu'elle ne soit pas assez réduite.

Habituellement, $A\vee A$ peut être remplacé par $A$, ainsi que $A\wedge A$, etc. quand de telles simplifications (je n'ai pas mis une liste exhaustive) ne sont plus possibles, c'est bon.

Raskolnikov

Par exemple : $(A\vee \land(A\vee D) \land(A\vee E) \land(B\vee C) \land(B\vee D)$, exemple issu du Cori Lascar, où l'auteur précise : "des vérifications fastidieuses permettraient de s'assurer qu'il n'est pas possible de réduire davantage le nombre de clauses".

christophe c

Tout dépend. Elle est visiblement non réductible de manière immédiate puisqu'il n'y a pas deux clauses égales, ni, dans une des clauses, un truc à réduire.

Après, je ne sais pas ce que tu entends par réduit, car le problème de l'équivalence (ie existe-t-il une AUTRE formule, qui lui est équivalente, mais contient moins de clauses?) est co NP complet

Raskolnikov

Je ne comprends pas la dernière phrase. Je n'en suis qu'au chapitre 1 et suis totalement novice en logique. Je me satisferai de ta première explication.
Merci

christophe c

Donne-moi une défition de "réduite" et je serai plus précis.

Raskolnikov

Je n'ai pas souvenir d'avoir lu une définition précise dans le livre (en tout cas le chapitre 1). Je pensais que c'était écrire une forme normale disjonctive avec le moins de symboles de disjonction possible.
Peut-être suis-je à côté de la plaque.

christophe c

Non mais ça d'accord, mais que veut dire possible. C'est un sujet NP-complet célèbrissime et le premier historiquement. Tu as des maximums locaux et des maximus globaux qui ne coincident pas du tout. Un gars qui ne peut plus avancer sur la route où il est en direction de Paris n'a pas forcément atteint le point le plus proche de Paris de son pays, ça peut peut-être vouloir dire qu'il a pris un chemin sans issue.

donc "la plus réduite possible" nécessite de lever cette ambiguité. Je peux courrieler à René pour lui souhaiter la bonne année et mettre un lien vers le fil, cependant, tu auras peut-être envie d'être plus certifiant avant (ou de préciser comment tu comptes exploiter ta lecture, car ça fait plusieurs questions que tu poses où on voit bien qu'il serait nécessaire de mieux connaitre ton profil pour t'aider).

Raskolnikov

Plus proche d'un profil Oshine que d'un profil Martial, si l'analogie est parlante.

christophe c

Je pense avec peu de probas de me tromper, que dans ton contexte il s'agit de maximums locaux, autrement dit de "formules qu'on ne peut pas réduire plus en un pas"

Et non pas de formule pour laquelle il n'existerait aucune formule équivalente plus réduite dans tout l'espace des formules.

C'est donc le "en un pas" qui devait te manquer.

PetitLutinMalicieux

Bonjour

Raskolnikov a écrit:

Par exemple : $(A\vee \land(A\vee D) \land(A\vee E) \land(B\vee C) \land(B\vee D)$

:-) Un très mauvais exemple de forme normale disjonctive, puisque c'est une forme normale conjonctive. C'est une conjonction de disjonctions. N'est-ce pas ?

F=(A+B)(A+D)(A+E)(B+C)(B+D)
F=(A + AD + AB + BD)(A+E)(B+C)(B+D)
F=(A + BD)(A+E)(B+C)(B+D)
F=(A + AE + ABD + BDE)(B+C)(B+D)
F=(A + BDE)(B+C)(B+D)
F=(AB + AC + BDE + BCDE)(B+D)
F=(AB + AC + BDE)(B+D)
F=(AB + ABD + ABC + ACD + BDE + BDE)
F=AB + ACD + BDE

$(A \land \vee (A \land C \land D) \vee (B \land D \land E)$ me semble être la forme disjonctive. Qu'en penses-tu ?

Raskolnikov

Oui je sais bien que c'est une forme normale conjonctive. Mais bon le principe est le même...
D'ailleurs, dans l'exercice en question, on part de la forme disjonctive pour arriver à cette forme conjonctive. L'auteur dit que les vérifications pour s'assurer qu'on ne peut plus réduire le nombre de clauses sont fastidieuses. Ma question portait là-dessus.

christophe c

Et le flou sur le fait que que réduire voulait dire "réduire en un pas" ou "réduire en un nombre fini de pas" et 99% de chances que réduire soit synonyme de "réduire en un pas".

Et merci à PLM pour son post.

Raskolnikov

Oui évidemment merci à vous deux pour votre aide. Désolé pour cet oubli !

PetitLutinMalicieux

"Le problème SAT" est le petit nom du problème de satisfaisabilité des équations booléennes. Il est réputé irrésolu depuis son apparition. Si on savait simplifier n'importe quelle fonction booléenne, on résoudrait le problème SAT. À la vérité, personne ne sait répondre à ta question. Et si quelqu'un savait, il ferait fortune.

christophe c

En temps polynomial quand-même, faut préciser :-D Sinon, tu vas faire des déçus qui vont se pointer avec un algo d'inspection exhaustive.

PetitLutinMalicieux

Effectivement, j'avais omis ce point.