Formes normales — Les-mathematiques.net The most powerful custom community solution in the world

Formes normales

waliddzwaliddz
dans Fondements et Logique
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]

Réponses

  • MaxtimaxMaxtimax
    Ce ne sera pas une forme normale de la même formule, mais effectivement $\neg \bigvee_{i\in I} \bigwedge_{k=1}^{n_i}a_{ki} = \bigwedge_{i\in I} \bigvee_{k=1}^{n_i}\neg a_{ki} $ pour un $I$ fini, $n_i \in \N$
  • waliddzwaliddz
    Merci pour m'avoir répondu.
    Existe-il un moyen pour obtenir la FNC d'une formule F à partir de sa table de vérité lorsque F est une tautologie ?
  • MaxtimaxMaxtimax
    "à partir de sa table de vérité lorsque $F$ est une tautologie" -> sa table de vérité c'est que des $1$
    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é.
  • waliddzwaliddz
    Je précise : des formes normales CONJONCTIVES
  • waliddzwaliddz
    Maxtimax écrivait :
    > 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.
  • christophe cchristophe c
    Tu n'es pas assez précis. Comme te le dit max, a ou non a, peut être vu comme forme normale conjonctive de n'importe quelle formule, mais aussi (a ou non a) et (b ou non b), etc.

    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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • waliddzwaliddz
    On ne peut pas donc déterminer la FNC d'une formule à partir de sa table de vérité. C'est ça ? ( et même chose pour les contradictions et les FND )
  • GaBuZoMeuGaBuZoMeu
    Serais-tu satisfait avec pour forme normale conjonctive la constante propositionnelle $\top$ ("vrai") ?
  • christophe cchristophe c
    Comme te le dit GBZM: avec la constante vraie pour la conjonction de la liste vide et la constante te faux pour la disjonction de la liste vide si si.

    Mais encore une fois il faudrait que tu précises ton algo. Sinon elles ne sont pas nécessaires.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • waliddzwaliddz
    Pas vraiment ( $ \top $ est-elle vraiment une variable 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 ?
  • christophe cchristophe c
    Non. Car dans ce cas tu peux considérer qu'une tautologie ne contenant que la lettre X a une FNC : (X ou nonX) et (X ou nonX) par exemple.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe cchristophe c
    Quand je dis non bien entendu c'est en évaluant ton désir. Tu "ne serais pas content"....

    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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GaBuZoMeuGaBuZoMeu
    waliddz écrivait:
    > $ \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 ?
  • waliddzwaliddz
    Vous voulez dire qu'on peut avoir une FNC indépendamment des variables propositionnelles figurant dans F ?!
  • christophe cchristophe c
    On ne veut rien dire d'autre que ce qu'on t'a dit. en maths, il n'y a pas d'implicites d'auteur.

    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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GaBuZoMeuGaBuZoMeu
    Pas indépendamment. Il me semble que les variables propositionnelles d'une FNC se doivent d'être parmi les variables propositionnelles de la formule F de départ. Mais pourquoi une variable propositionnelle dont la valeur n'a aucune influence sur la valeur de vérité de la formule F devrait-elle figurer dans une FNC ?
  • christophe cchristophe c
    De plus, est-ce que tu (waliddz) considères comme acceptable la conjonction $x\wedge non(x)$ ?

    Ne souhaiterais-tu pas que les conjonctions soient des conjonctions de listes injectives ?
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • waliddzwaliddz
    Tout ce que je souhaite c'est écrire la FNC d'une formule tautologique à partir de ses variables propositionnelles et en utilisant sa table de vérité :-D
  • waliddzwaliddz
    Franchement, je ne sais pas pourquoi on nous enseigne ce module appelé " Logique mathématique ", qui - soi-disant- s'intéresse au raisonnement mathématique et qu'en réalité n'a rien à voir avec les autres disciplines mathématiques !
  • christophe cchristophe c
    La réponse t'a été donnée*. Mais si tu veux t'approprier les choses, on t'a aussi demandé d'être précis ce que pour l'instant tu n'as pas encore fait.

    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).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • MaxtimaxMaxtimax
    $x_1\lor \neg x_1 \lor x_2 \lor ... \lor x_n$ ? Il s'agit d'une formule équivalente à $F$, sous forme normale conjonctive, qui contient toutes les variables de $F$
  • christophe cchristophe c
    Et pour répondre à ton dernier post, idem, si tu ne précises pas ta filière, commenter ta critique du module n'est pas possible.

    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.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe cchristophe c
    @max: tu lui as déjà dit, mais il (ou elle) semble refuser d’être plus précis dans sa demande.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • waliddzwaliddz
    Je vois clairement les choses maintenant :-D
  • christophe cchristophe c
    hip hip hip...
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • waliddzwaliddz
    Je peux même aller plus loin :-D:-D
    une FND d'une contradiction: $ x_1\wedge \neg x_1 \wedge x_2 \wedge ... \wedge x_n $ :-D:-D:-D
  • christophe cchristophe c
    Comme tu n'as pas répondu, je réponds à ta place sur les exigences qui, non dites, rendent ta question sans contenu.

    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).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!