Calcul Propositionnel - Récurrence

Bonjour à tous! voici mon problème :

Soit $\phi \in F$ une formule du calcul propositionnel. Montrer par récurrence sur la hauteur d'une formule la proposition suivante :

$\phi$ {\it contient un nombre pair de symboles de négation si et seulement si $\phi$ contient un nombre impair de symboles en tout.}

Quelqu'un aurait-il une idée ? je ne vois vraiment pas comment faire :(


[Les bannières BBcode (...) ne fonctionnent pas si LaTeX est coché. AD]

Réponses

  • désolé j'ai posté 2 fois le sujet... :(

    [La deuxième discussion est maintenant cachée. ;) AD]
  • La proposition à montrer est en fait:

    \textit{Le nombre de symboles de négation et le nombre total de symboles de la formule $\phi$ sont de parités contraires.}

    Je te laisse initialiser la récurrence.

    Pour l'hérédité, il faut étudier tous les cas d'écriture de $\phi$:

    Si $\phi$ est $\neg \psi$, lorsque tu passes de $\psi$ à $\phi$, tu rajoutes un seul symbole, qui est un symbole de négation; tu changes donc la parité, tant du nombre total de symboles que du nombre de symboles de négation, ces parités restent différentes.

    Si $\phi$ est $\forall x \psi$, ou $\exists x \psi$, tu rajoutes deux symboles qui ne sont pas des négation, tu ne changes aucune parité.

    Si $\phi$ est $\psi_1 \oplus \psi_2$, pù $\oplus$ est un connecteur d'arité 2, tu étudies la parité du nombre de symboles de négation dans $\psi_1$ et $\psi_2$ suivant le nombre total de symboles de ces formules, et tu conclues quant au résultat sur $\phi$.
  • juste deux détails : à moins d'utiliser la notation polonaise, il y a des parenthèses : ¬(P), (P) k (Q) pour un connecteur binaire k,
    mais ça ne change pas le raisonnement de gb.
    (les quantificateurs sont en prime puisqu'il est question de calcul propositionnel !)
  • oula merci pour toutes ces précisions mais je crois avoir seulement compris le 1er cas dans lequel on rajoute simplement le symbole de négation.

    Donc si j'ai bien compris j'initialise la récurrence en montrant pour h=1 puis je suppose vrai pour h=n et je démontre pour h=n+1 dans les 3 cas que vous m'avez indiqué ?
  • En effet, je n'avais pas lu le "propositionnel", donc les quantificateurs sont hors sujet.

    Quant aus parenthèses, bien que n'utilisant pas, par raison de lisibilité, la notation polonaise, je ne les considère pas comme faisant partie des symboles de la logique. Comme elles vont toujours par 2, elles n'interviennent pas dans la parité du nombre de symboles.
  • ça marche bien avec h=1 et h=2 mais j'ai beau chercher je ne trouve pas comment démontrer que la proposition est vraie pour une hauteur de n+1 ??
  • Il faut faire une récurrence forte. Une formule de hauteur h+1 est construite à partir de sous-formules de hauteurs inférieures ou égales à h.
  • ok merci beaucoup pour l'information, je vais tenter de résoudre le problème (mais ça me paraît assez difficile après seulement 3 cours de Logique...)
  • typho, en attendant que tu termines ta démo, je te propose une autre approche.

    Il y a un résultat très utile, qui te servira aussi pour d'autres constructions par induction, c'est le principe de démonstration par induction :

    Si les propositions atomiques vérifient une certaine propriété R, et si ¬(P) et (P) k (Q) la vérifient aussi (pour tous les connecteurs binaires k) dès que P et Q la vérifient , alors toutes les formules ont la propriété R.

    Si ce principe est valide, alors ton problème est immédiat :
    tu prends pour R la propriété : la formule F a son nombre de symboles de parité contraire à son nombre d'occurences de ¬.

    R est bien sûr vraie pour les formules atomiques : un symbole, pas d'occurence de ¬.
    Si R est vraie pour P, alors elle est encore vraie pour ¬(P) : tu rajoutes trois symboles et un ¬,
    et si R est vérifiée par P et Q, elle l'est encore par (P) k (Q) : la somme des symboles de P et Q est de même parité que la somme de leurs ¬, et tu rajoutes cinq symboles et pas de ¬.

    Ainsi, la propriété R est vraie pour toutes les formules. Reste à démontrer ce principe :

    L'ensemble F des formules étant défini comme l'intersection de tous les ensembles A de mots vérifiant : A contient les formules atomiques, ainsi que les mots ¬(P) et (P) k (Q) dès qu'il contient P et Q pour tout connecteur k,
    supposons donc une propriété R vérifiée par les formules atomiques et par ¬(P) et (P) k (Q) si P et Q la vérifient.

    Soit alors T l'ensemble des formules vérifiant R. Il est clair que T contient les formules atomiques et que si P et Q sont des formules de T, alors ¬(P) et (P) k (Q) sont aussi dans T, pour tout connecteur k.

    T est donc l'un des A, et F étant inclus dans T, toutes les formules vérifient R.
  • Ca c'est du raisonnement ! Et en plus très utile ! Je vais quand même essayer de le faire par récurrence et je repasserai si je n'arrive pas !
    En tout cas merci !
Connectez-vous ou Inscrivez-vous pour répondre.