Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
219 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Forme normale disjonctive simplifiée

Envoyé par Raskolnikov 
Forme normale disjonctive simplifiée
il y a trois mois
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.
Re: Forme normale disjonctive simplifiée
il y a trois mois
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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
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".
Re: Forme normale disjonctive simplifiée
il y a trois mois
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

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
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
Re: Forme normale disjonctive simplifiée
il y a trois mois
Donne-moi une défition de "réduite" et je serai plus précis.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
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.
Re: Forme normale disjonctive simplifiée
il y a trois mois
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).

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
Plus proche d'un profil Oshine que d'un profil Martial, si l'analogie est parlante.
Re: Forme normale disjonctive simplifiée
il y a trois mois
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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
Bonjour

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

smiling smiley 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 ?



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par PetitLutinMalicieux.
Re: Forme normale disjonctive simplifiée
il y a trois mois
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.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par Raskolnikov.
Re: Forme normale disjonctive simplifiée
il y a trois mois
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.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
Oui évidemment merci à vous deux pour votre aide. Désolé pour cet oubli !
Re: Forme normale disjonctive simplifiée
il y a trois mois
"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.
Re: Forme normale disjonctive simplifiée
il y a trois mois
En temps polynomial quand-même, faut préciser grinning smiley Sinon, tu vas faire des déçus qui vont se pointer avec un algo d'inspection exhaustive.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Forme normale disjonctive simplifiée
il y a trois mois
Effectivement, j'avais omis ce point.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 228, Messages: 1 506 987, Utilisateurs: 27 661.
Notre dernier utilisateur inscrit ibra.


Ce forum
Discussions: 2 516, Messages: 51 075.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page