Forme normale disjonctive simplifiée — Les-mathematiques.net The most powerful custom community solution in the world

Forme normale disjonctive simplifiée

RaskolnikovRaskolnikov
dans Fondements et Logique
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.

Réponses

  • christophe cchristophe 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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • RaskolnikovRaskolnikov
    Par exemple : $(A\vee B) \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 cchristophe 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
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • RaskolnikovRaskolnikov
    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 cchristophe c
    Donne-moi une défition de "réduite" et je serai plus précis.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • RaskolnikovRaskolnikov
    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 cchristophe 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).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • RaskolnikovRaskolnikov
    Plus proche d'un profil Oshine que d'un profil Martial, si l'analogie est parlante.
  • christophe cchristophe 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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PetitLutinMalicieuxPetitLutinMalicieux
    Bonjour
    Raskolnikov a écrit:
    Par exemple : $(A\vee B) \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 B) \vee (A \land C \land D) \vee (B \land D \land E)$ me semble être la forme disjonctive. Qu'en penses-tu ?
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • RaskolnikovRaskolnikov
    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 cchristophe 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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • RaskolnikovRaskolnikov
    Oui évidemment merci à vous deux pour votre aide. Désolé pour cet oubli !
  • PetitLutinMalicieuxPetitLutinMalicieux
    "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.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
  • christophe cchristophe 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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PetitLutinMalicieuxPetitLutinMalicieux
    Effectivement, j'avais omis ce point.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!