Équivalence logique entre trois énoncés

Bonjour à toutes et tous
J'ai une question un peu stupide.

Soit $\mathcal{L}$ un langage du premier. Soient $A(x)$ et $B(y,z)$ deux $\mathcal{L}$-formules dont les variables libres sont respectivement incluses dans $\{x\}$ et $\{y,z\}$.

Êtes-vous d'accord pour dire que les formules ci-dessous sont logiquement équivalentes ?

Formule n°1 : $[\forall x A(x)] \to [\forall z \exists y B(y,z)]$

Formule n°2 : $\forall z \exists x \exists y [A(x) \to B(y,z)]$

Formule n°3 : $\exists x \forall z \exists y [A(x) \to B(y,z)]$

J'ai démontré sémantiquement et assez simplement ces trois équivalences (pour les connaisseurs : à certains endroits la démonstration ressemble un peu à la preuve sémantique de la validité de la "formule du buveur").

Malgré tout, l'interversion des quantificateurs dans les formules n°2 et n°3 me semble suspect. Par conséquent, j'ai peur d'avoir fait une erreur grossière dans ma démonstration.

Merci d'avance pour vos réponses.

PS : Évidemment, pour toutes paires de $\mathcal{L}$-énoncés $\phi$ et $\psi$, on dit que $\phi$ et $\psi$ sont logiquement équivalentes lorsque $\vdash \phi \leftrightarrow \psi$.

Réponses

  • Soyons barbares : $P\to Q$ est équivalent à $\neg P\lor Q$, ainsi ta formule 1 est $(\exists x, \neg A(x))\lor (\forall z, \exists y, B(y,z))$

    Maintenant, dans une disjonction, les quantificateurs peuvent toujours se passer devant : $(\exists x, P(x))\lor Q \equiv \exists x, (P(x)\lor Q)$ et $(\forall x, P(x))\lor Q \equiv \forall x,(P(x)\lor Q)$

    Pour le premier, c'est évident (enfin euh bon il faut savoir que $\exists x, \top$ est vraie, je le mets en axiome - d'ailleurs tu en as besoin aussi, car sinon, 1 est vraie et 3 est fausse; mais peut-être que c'est mis par défaut dans ton formalisme); et pour le second aussi.

    En conclusion, dès que tu as "(quantificateurs $P)\lor ($quantificateurs $Q)$", tu peux sortir tes quantificateurs dans n'importe quel ordre, tant que tu sors ceux de $P$ dans le bon ordre, et ceux de $Q$ dans le bon ordre (à nouveau, en supposant que $\exists x,\top$).

    Donc l'inversion des quantificateurs n'a pas à te surprendre ici : c'est que les deux sont "indépendants"
  • Merci beaucoup d'avoir confirmé la validité du résultat.

    PS : En réalité, j'ai un peu menti dans mon message précédent : j'ai d'abord obtenu ces équivalences avec la même démarche que toi et j'ai ensuite vérifié sémantiquement ces équivalences.
  • Les formules 1 et 2 admettent des modèles vides, la 3ième non.
    Ces formules sont équivalentes en logique du 1er ordre sans contexte (celle qui reconnaît la validité de formules telles que $\forall x P x \to \exists x P x$), mais non équivalentes avec contextes (sauf à ajouter un symbole de constante dans le langage).
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Alors $\rightarrow $ serait le nouveau nom de $\Rightarrow $ ?
    Bonne soirée.
    Fr. Ch.
    [small]SGANARELLE.- Oui, cela était, autrefois, ainsi ; mais nous avons changé tout cela, et nous faisons maintenant la médecine d’une méthode toute nouvelle.[/small]
  • Chaurien: $\Rightarrow$ et $\to$ désignent la même chose en logique (l'implication) cependant comme en maths la flèche $\to$ est déjà utilisée de plein de façons différentes, on peut préférer la double flèche $\Rightarrow$ pour éviter les ambiguïtés lorsqu'il peut y en avoir.

    De plus sur le forum il est plus court d'écrire "\to" que "\Rightarrow"...

    [Il y a aussi \implies : $\implies$ :-D AD]
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • @Foys : Je travaille toujours avec l'axiome donnant l'existence d'un élément.

    @Chaurien : Dans beaucoup de manuels et d'articles modernes de logique on trouve la notation $\to$ pour l'implication.

    Personnellement, je trouve cela plus esthétique : la notation $\implies$ est un peu trop chargée à mon goût.
    Comme l'a indiqué Foys, la véritable raison de ce changement est (probablement) que cela va plus vite à taper en LaTeX.

    Dans certains (vieux) textes on trouve même la notation $P \supset Q$ au lieu $P \implies Q$.
  • Merci AD!!!!!!!!!

    $\implies$

    $\implies$

    $\implies$

    :-D
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.