É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$.
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$
:-DAide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 4
4 Invités