Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Distributivité de ∃ sur ∨ - Déduction naturelle

Posté par
Hugo142857
09-11-20 à 15:25

Bonjour,

je souhaite prouver par les règles de la déduction naturelle sur les quantificateurs la relation suivante :

∃x, [P(x) ∨ Q(x)] => ∃x,P(x) ∨ ∃x,Q(x)

Je sais qu'il faut commencer par l'introduction de l'implication mais ensuite je suis complètement bloqué.

Merci d'avance pour votre aide.

Posté par
GBZM
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 15:39

Bonjour,

Tu as à démontrer la conclusion sous l'hypothèse.
Pour cela il te faut éliminer le quantificateur existentiel, éliminer la disjonction, introduire deux quantificateurs existentiels et introduire une disjonction.

Posté par
Hugo142857
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 16:10

Bonjour et merci pour votre réponse,

je ne suis pas sur d'avoir compris la méthode : en éliminant l'existentiel, je dois donner deux informations :

Une formule "∃x,A(x)" à prouver
Une preuve de ∃x,P(x) ∨ ∃x,Q(x) sous l'hypothèse "soit x, A(x)"

que dois-je fournir ?

Posté par
Hugo142857
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 16:19

Je viens finalement de résoudre l'implication. Merci Beaucoup

D'autre part, l'autre sens me semble aussi valide, comment le prouver ?

Posté par
GBZM
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 16:20

Non,

Pour l'élimination du quantificateur existentiel, tu as à fournir une démonstration de \exists x\;P(x) \vee \exists x\; Q(x)\ (=B) sous l'hypothèse P(x) \vee Q(x)\ (=A(x)) :



 \\ \begin{array}{ccc} &&[A(x)]\\&&\vdots\\ \exists x\; A(x)&&B\\\hline&B&\end{array}

Posté par
GBZM
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 16:23

Apparemment, tu t'en es sorti.

L'autre sens est du même tabac. On commence par éliminer la disjonction ...

Posté par
Hugo142857
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 17:09

Que met on dans la disjonction que l'on élimine ?

Je pensais mettre simplement l'hypotèse "∃x,P(x) ∨ ∃x,Q(x)"

mais je ne pense pas que l'on puisse prouver ∃x,[P(x)∨Q(x)] simplement avec l'hypothèse ∃x,P(x) ou simplement avec l'hypothèse ∃x,Q(x)

Posté par
GBZM
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 17:46

Bien sûr que si. Le bon sens indique clairement que \exists x\;P(x) entraîne \exists x\,(P(x)\vee Q(x)), et le bon sens se traduit facilement en déduction naturelle : éliminer la quantification existentielle, introduire une disjonction, introduire une quantification existentielle.

Posté par
Hugo142857
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 18:26

d'accord, je comprends mieux.

Merci pour votre aide

Posté par
GBZM
re : Distributivité de ∃ sur ∨ - Déduction naturell 09-11-20 à 18:27

Avec plaisir.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !