Formes normales
Bonjour,
j'aimerais savoir si on peut obtenir une FND à partir d'une FNC par négation de celle-ci !
Merci.
[Pour les béotiens dont je suis FND Forme Normale Disjonctive et FNC Forme Normale Conjonctive. AD]
j'aimerais savoir si on peut obtenir une FND à partir d'une FNC par négation de celle-ci !
Merci.
[Pour les béotiens dont je suis FND Forme Normale Disjonctive et FNC Forme Normale Conjonctive. AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Existe-il un moyen pour obtenir la FNC d'une formule F à partir de sa table de vérité lorsque F est une tautologie ?
Et sa forme normale sera quelque chose comme $a\lor \neg a$ pour une variable propositionnelle $a$ quelconque.
Mais on peut effectivement récupérer la forme normale conjonctive d'une formule (pas forcément une tautologie) à partir de sa table de vérité.
> Mais on peut effectivement récupérer la forme normale conjonctive d'une formule (pas forcément
> une tautologie) à partir de sa table de vérité.
Justement, lorsque la formule n'est pas une tautologie, on regarde les 0 figurant dans la colonne de la formule considérée. Ce qui n'est pas faisable lorsque F est une tautologie, d'où ma question.
Il faut que tu précises par quel procédé tu souhaites passer de la formule à une forme normale de cette formule et que tu précises aussi ta question qui pourrait être "est-ce que la table de vérité me permet de deviner à l'avance quelle sera la forme obtenue par tel algorithme?
Tel que tu postes pour l'heure, une formule F sous forme normale prouvablement équivalente à une formule G peut être suspectée d'être acceptée par toi comme forme normale de G.
Et sinon, sache que de manière naturelle, sans même parler de logique, il existe deux "objets vides" duaux pour les listes de listes où le jeu consiste à opposer deux personnes, disons Lea et Bob où
Lea choisit un item de la liste, puis Bob choisit un item de l'item choisi par Lea. Bloquer Bob et bloquer Lea ce n'est pas du tout la même chose: on peut donc créer deux symboles, un pour la liste vide à laquelle Lea peut faire face et UN AUTRE pour désigner la liste vide qui pourrait être présentée à Bob.
En logique ce sont respectivement le vrai et le faux.
Mais encore une fois il faudrait que tu précises ton algo. Sinon elles ne sont pas nécessaires.
Etant donnée une formule F contenant n variables propositionnelles; mettre F sous FNC, c'est trouver une formule normale conjonctive logiquement équivalente à F et qui contient toutes les variable de F, non ?
Par ailleurs pour des raisons autres (pédagogiques :-D ) il est sain de te signaler les listes vides. GBZM "fait semblant" de te proposer un nouveau symbole mais en fait vrai N EST PAS un nouveau signe mais juste le nom de la conjonction de la liste vide.
> $ \top $ est-elle vraiment une variable propositionnelle ?)
Ben non, comme je l'ai écrit c'est une constante propositionnelle.
> Etant donnée une formule F contenant n
> variables propositionnelles; mettre F sous FNC,
> c'est trouver une formule normale conjonctive
> logiquement équivalente à F et qui contient
> toutes les variable de F, non ?
D'où sort cette "définition" de la forme normale conjonctive ?
On te demande d'être précis dans ta demande sinon, on peut la satisfaire d'une manière qui ne te comblera pas.
Par exemple ta définition de "FNC de P" est trop lâche.
Ne souhaiterais-tu pas que les conjonctions soient des conjonctions de listes injectives ?
Réponds aux questions suivantes:
1/ qu'est-ce qu'une FNC?
2/ Comment souhaites-tu passer d'une formule à sa (ou ses) FNC?
3/ Qu'appelles-tu "table de vérité" d'une formule? Je te rappelle que deux formules prouvablement équivalentes et contenant les mêmes variables ont la même TV, donc ta demande n'est pour l'heure pas vraiment sensée.
* En l'état actuelle de tes demandes, la conjonction de la liste vide (qui est une FNC parfaitement banale, mais apparemment tu n'en as pas accusé réception) est la FNC de n'importe quelle tautologie, fin de l'histoire; car apparemment les non tautologies, tu as une idée bien précise de leur FNC (on ne va donc pas tout t'écrire).
Les maths étant juste de la logique appliquée, a priori, sauf dans les études où on ne fait pas de maths (où le mot "math" est mis pour autre chose), il parait assez banal d'y enseigner les bases, ie les règles du jeu de la démarche mathématique.
une FND d'une contradiction: $ x_1\wedge \neg x_1 \wedge x_2 \wedge ... \wedge x_n $ :-D:-D:-D
1/ Une conjonction (resp disjonction) de variables sera dites bonne quand chaque variable apparaît au plus une fois dedans.
2/ Dans une FND (resp FNC) il ne peut pas apparaître deux items singletons avec la même variable d'une part et d'autre part tous ses items doivent être bonnes.
Partant de là, toute formule peut être mise sous FND comme sous FNC dès lors qu'on admet les listes vides d'une part, et d'autre part en se contentant de développer et simplifier.
Par ailleurs, il est très recommandé de faire apparaitre une notation pour dire si on a affaire à une conjonction ou à une disjonction. Sinon, par exemple $x\vee y$ peut apparaitre comme une disjonction alors que son auteur a voulu parler de la conjonction de la liste contenant comme unique formule la formule $x\vee y$.
C'est de plus indispensable pour distinguer la conjonction de lia liste vide (le vrai) et la disjonction de la liste vide (le faux).