Question de prédicats

Adaq
Adaq
dans Fondements et Logique
Bonjour,
Je viens de lire dans mon script que $$\exists x (P(x) \land Q(x)) \vDash \exists x P(x) \land \exists x Q(x)$$ Alors première question, est-ce que dans la partie de droite les deux $x$ sont les mêmes par définition ? Evidemment qu'ils doivent être semblables pour que l'identité soie correct mais est-ce que par définition quand on a 2 $\exists x$ dans une formule les $x$ sont de toute façon les mêmes ou est-ce que $x$ peut prendre deux valeurs différentes pour chacun des $\exists$?

En d'autres mots est-ce que dire $\exists x (P(x) \land Q(x)) \vDash \exists x P(x) \land \exists x Q(x)$ est équivalent à $\exists x (P(x) \land Q(x)) \vDash \exists x P(x) \land \exists y Q(y)$ ?

Maintenant je n'ai pas de mal à me convainvre que cette affirmation est correct par contre j'aimerais bien me convaincre que le contraire n'est pas valable puisque $\exists x (P(x) \land Q(x)) \vDash \exists x P(x) \land \exists x Q(x)$ n'implique pas que $\exists x P(x) \land \exists x Q(x) \vDash \exists x (P(x) \land Q(x))$. J'ai donc penser à utiliser le lemme suivant :
- Soit $F$ et $G$ deux formules, si et seulement si $F \to G \equiv \top$ alors $F \vDash G$

Sans prédicats il n'y aurait pas de problème mais je ne sais pas comment déterminer si $\exists x P(x) \land \exists x Q(x) \to \exists x (P(x) \land Q(x)) \equiv \top$. Comment poser les tables de vérité ? Est-ce qu'il faut considérer $\exists x P(x)$ comme un symbole et simplement lui donner la valeur de 0 ou de 1, faire de même pour $\exists x Q(x)$ puis appliquer la conjonction comme si on faisait simplement $A \land B$ ?

Merci de votre aide, je suis à dispostion pour toute question.

Réponses

  • seb78
    seb78
    A ton avis est-ce-que les propositions suivantes sont équivalentes ?

    { il existe un humain qui court le 100m en moins de 10s et qui est champion du monde de tennis de table }

    { il existe un humain qui court le 100m en moins de 10s et il existe un humain qui est champion du monde de tennis de table }
  • Adaq
    Adaq
    Non, mais je ne pense pas que je puisse argumenter comme cela dans un examen, malheureusement. Mais merci pour la démonstration intuitive, je vois très bien le problème.
  • Poirot
    Poirot
    $\exists x P(x) \land \exists x Q(x)$ est la même formule que $\exists x P(x) \land \exists y Q(y)$, tout du moins elles sont équivalentes.
  • seb78
    seb78
    et par ailleurs tu as l'axiome $\exists x, y ( P(x) \land \lnot P(y))$
  • christophe c
    christophe c
    Alors première question, est-ce que dans la partie de droite les deux x sont les mêmes par définition ?

    Il n'y a aucun $x$ dans la partie droite (pas plus que dans la partie gauche). Ta question n'a donc pas de sens.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Adaq
    Adaq
    Poirot : merci, c'est ce que je voulais savoir.
    Seb78 : merci de l'info :-)
    Christophe : $\exists \textbf{x} (P(\textbf{x}) \land Q(\textbf{x})) \vDash \exists \textbf{x} P(\textbf{x}) \land \exists \textbf{x} Q(\textbf{x})$ ?

    Mais du coup, personne ne sais comment vérifier la réciproque (donc si $\exists x P(x) \land \exists x Q(x) \to \exists x (P(x) \land Q(x)) \equiv \top$) ?
  • christophe c
    christophe c
    :-D Je maintiens ce que j'ai dit. Je te laisse y réfléchir et ne demande à personne.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Poirot
    Poirot
    @cc : moui, je sais ce que tu veux dire, mais tu ne peux pas dire qu'il n'y a pas de $x$.
  • GaBuZoMeu
    GaBuZoMeu
    Le sens de la réponse de Christophe est : $x$ n'est variable libre ni à gauche ni à droite (il ne sera sans doute pas d'accord avec la formulation). Des deux côtés, toutes les occurrences de $x$ sont des occurrences muettes, c.-à-d. qui sont tuées par une quantification. Donc ce que tu écris est parfaitement équivalent à
    $$\exists \textbf{s} (P(\textbf{s}) \land Q(\textbf{s})) \vDash \exists \textbf{t} P(\textbf{t}) \land \exists \textbf{u} Q(\textbf{u})$$
    Est-ce que ça a un sens de demander, pour ce qui est écrit ci-dessus, si dans la partie de droite les deux $\mathbf x$ sont les mêmes ?
  • Adaq
    Adaq
    Et bien maintenant je sais que non apparemment, on écrit seulement $x$ pour que ce soit plus simple à lire, c'était ce que je voulais savoir, merci.
    Comment ça est-ce que ça a un sens ? Je voulais simplement savoir, rien à voir avec l'identité ci-dessus, c'était pour illustrer ma question.
  • christophe c
    christophe c
    :-D Je suis 100% d'accord avec ton post GBZM (et même je pense comprendre la contrariété de Poirot).

    Simplement je voulais que le "traumatisme" ait le temps de faire son nid dans les neurones de adaq pour qu'une réponse soulageante par exemple ce soir vienne clore une longue cogitation et le faire monter au septième ciel. Il aurait peut-être trouvé tout seul d'ailleurs en se demandant "ai-je besoin de connaître la valeur de x pour évaluer cette phrase ?"

    Mais le destin en a décidé autrement.

    (Si je n'ai pas droit de la part de dom à un "c'est de la pédagogie", j'aurai de la chance :-D )
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Adaq
    Adaq
    Encore une fois, ce n'était pas pour étudier cette phrase que je voulais connaître la valeur de $x$ c'était pour être sûr que j'aie bien compris ce que ce "il existe un x" signifiait, l'exemple était là pour illustrer de quoi je parlais, j'aurais pu mettre autre chose.

    Mais cela ne m'éclaire toujours pas sur comment vérifier des identités avec des quantificateurs par contre, mais je suppose que si personne n'a répondu c'est que cela doit être fort pénible hahaha.

    Enfin bon, je vous remercie de votre aide, c'est une bonne chose de tiré au clair.
  • GaBuZoMeu
    GaBuZoMeu
    @Christophe : Il semble que ma réponse à Adaq ait été suffisamment "rentre-dedans" pour prolonger le traumatisme. ;-)
    Désolé de t'avoir coupé l'herbe sous le pied.

    @Adaq : Que veux-tu dire par " vérifier des identité[ s] avec des quantificateur[ s]" ?
  • Adaq
    Adaq
    J'aimerais pouvoir démontrer, avec une table de vérité ou n'importe quoi de formel que $$\exists x P(x) \land \exists x Q(x) \to \exists x (P(x) \land Q(x)) \equiv \top$$ ne se vérifie pas.
    Autrement dit pouvoir produire la table de vérité $\exists x P(x) \land \exists x Q(x) \to \exists x (P(x) \land Q(x))$ comme on le ferait pour vérfier que par exemple $A \land B \vDash A \lor B$. Sauf que pour $A$ et $B$ je sais bien comment cela se passe, ils prennent soit la valeur de 0 soit de 1 mais je ne sais pas si il en est de même pour $\exists x P(x)$ et donc par extension je ne peut pas esquisser la table de vérité de $\exists x P(x) \land \exists x Q(x)$, etc...
  • Poirot
    Poirot
    Difficile de parler de table de vérité lorsque l'on a des quantificateurs dans les formules, on n'est plus dans le cadre de la logique des prédicats mais celui de la logique du premier ordre ! La bonne notion est alors la notion de satisfaisabilité, ce qui se vérifie dans des modèles.

    Un exemple très simple : dans un langage à deux constantes $\{a, b\}$, n'importe quel ensemble à deux éléments $E=\{x,y\}$ où l'interprétation de $a$ est $x$ et l'interprétation de $b$ est y satisfait $$\left(\exists x, x=a\right) \wedge \left(\exists x, x=b\right),$$ mais ne satisfait jamais $$\exists x, \left(x=a \wedge x=b\right).$$
  • Adaq
    Adaq
    Ah je vois, je n'ai encore jamais entendu parlé de logique du premier ordre donc j'imagine que cela viendra mais en somme, au lieu de traiter toutes les possibilités comme avec la logique des prédicats, on va donner une valeur (non binaire dans la plupart des cas j'imagine) et vérifier si on trouve un cas pour lequel on peut satisfaire le côté, dirons nous gauche du $\to$ mais pas le côté droit.
    Si on en trouve alors forcément cela vaudra dire que ce n'est pas une tautologie.

    Je crois avoir compris l'idée, merci
  • christophe c
    christophe c
    Un jour que je surfais, je ne sais plus pourquoi (et je venais d'acheter mon pc, j'essayais de comprendre comment on met un truc en favori vu que je ne l'avais jamais fait) j'avais mis en favori le lien suivant:
    https://www.umsu.de/logik/trees/

    je n'aurais jamais pensé :-D pouvoir le signaler des années plus tard, mais tant mieux, en espérant qu'il marche encore et qu'il soit bien documenté

    Tu vas être déçu adaq, mais il n'y a pas de tables de vérité possibles, car on doit envisager des modèles (ie des attributions de valeurs aux phrases et sous-phrases et objets) qui sont infinis, et essayer tous les modèles infinis, bof bof.

    Après si tu enrichis et précises ta demande (et ton niveau), on peut rechercher comment te satisfaire.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Adaq
    Adaq
    Il est très sympa ce site haha. Mais je suis pleinement satisfait merci à vous tous, je voulais juste avoir une idée du raisonnment, je ne suis qu'encore au début des prédicats, j'imagine que les interprétation et tout cela viendra par la suite :-)
  • Foys
    Foys
    Génial ce site christophe c.
    Le site applique la "méthode des tableaux", il commence par supposer la formule fausse et déduit successivement tout ce qu'il y a à déduire (en décomposant à chaque fois les formules) et s'il aboutit à une contradiction c'est que la formule de départ est en fait prouvable (un tel diagramme n'est rien d'autre qu'une preuve en calcul des séquents écrite à l'envers). Si on a $\exists x P (x)$ (ou $\neg \left (\forall y Q(y) \right)$ a.k.a $\exists y \neg Q(y)$), il poursuit le raisonnement avec $P(\alpha)$ (resp $\neg Q(\alpha)$) et avec une nouvelle lettre $\alpha$ non encore utilisée ("si quelqu'un vérifie la propriété X, appelons ce quelqu'un Jean-Jacques, pourvu que ce nom ne soit pas utilisé, et continuons la conversation en sachant que Jean-Jacques a la propriété X").
    Les formules $A \vee B$ et $\neg (C \wedge D)$ entraînent les distinctions de cas ($A$,$B$) et $(\neg C,\neg D)$
    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$.
  • Alesha
    Alesha
    seb78 a écrit:
    tu as l'axiome $\exists x, y (P(x) \land \lnot P(y))$

    D'où sort cet axiome?
  • seb78
    seb78
    Bonjour Alesha,

    C'est un bêtise. Cette formule est même fausse comme on le voit avec l'excellent lien de christophe.
  • Alesha
    Alesha
    J'avais vu que Adaq te remerciait de l'info donc je m'inquiétais qu'il ait été embrouillé par ton message; désolé si Christophe avait déjà corrigé ton message.
  • christophe c
    christophe c
    Je n'y suis pour rien je découvre seulement le vieux post avec coquille de seb et je n'ai pas encore eu non plus le temps d'aller explorer un le lien que j'ai mis . Quand j'étais tombé dessus j'avais un peu joué avec mais était ensuite passé à autre chose. Il faudra que je le regarde plus. Je crois qu'il est surtout pédago car il va vraiment vraiment très très doucement pour construire l'arbre si je me rappelle.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 20

APfCidrolinJLTMédiat_SuprèmeVassillia +15 Invités