Cette séquence logique de prédicat est-elle valide?

Oct 13 2020

C'est peut-être un ensemble idiot de questions connexes et ce qui suit est le problème qui l'a déclenché.

On me demande de prouver cette séquence logique de prédicat:

$\exists x[R(x) \vee S(x)] \;\;\;\;\; |- \;\;\;\;\exists x R(x) \vee \exists x S(x) $

J'ai honte de dire que je ne peux pas le prouver. J'ai essayé l'approche directe ainsi qu'une approche preuve par contradiction, sans succès. Et puis, je me suis rendu compte que la question était peut-être fausse. Il n'y a peut-être aucune preuve. Bien entendu, ne pas être en mesure de prouver une séquence n'implique pas qu'elle est invalide et je ne sais donc même pas si la question est mal formulée. Si c'était une question de logique propositionnelle, et que la quantité d'atomes propositionnels était suffisamment petite, je pourrais construire une table de vérité et vérifier l'implication sémantique. Un séquent propositionnel est valide ssil est impliqué sémantiquement, et donc une table de vérité pourrait l'invalider. Cependant, avec le prédicat Logic et son ensemble de quantificateurs, je n'ai aucune expérience de la vérification des tables de vérité dans ce cas et je ne peux donc même pas savoir si la séquence est invalide.

En utilisant un argument anglais, je peux l'invalider en laissant $R(x)$ signifier $x$ est un objet rugueux et $S(x)$ sens $x$ est un objet lisse:

"Prémisse: Il existe un objet rugueux comme un grain. Conclusion: Il existe un objet lisse comme un roulement à billes".

Propositionnellement, la phrase est valide parce que la prémisse et la conclusion sont vraies. Mais logiquement, il est invalide. L'existence d'un objet rugueux n'implique pas l'existence d'un objet lisse. (Note latérale: ce qui est encore plus déroutant, c'est que j'ai maintenant quitté le domaine de la logique propositionnelle de base pour entrer dans ce qui semble être un domaine plus "subjectif" et c'est frustrant)

Mais il n'y a pas de «rigueur» dans l'argumentation logique articulée en anglais.

Des questions:

La séquence ci-dessus est-elle valide?
Si vous connaissez sa validité parce que vous l'avez prouvé à l'aide des règles de déduction, arrêtez-vous ici
S'il n'y a pas de preuve, comment pouvez-vous prouver qu'elle est invalide? Utilisez-vous des tables de vérité?

Réponses

2 lemontree Oct 13 2020 at 19:23

L'inférence est valide et dérivable.

En général, un contre-exemple à une inférence invalide consiste en une structure dans laquelle toutes les prémisses sont vraies mais la conclusion est fausse.

Votre argument est incorrect car il ne montre pas précisément (en fournissant un modèle de compteur concret) que cette interprétation des prédicats invalide le séquent, et votre exemple anglais n'est pas une déformalisation appropriée de l'instruction: vous ne pouvez pas simplement laisser tomber l'un des disjoints dans chacune des phrases. Si$R(x)$ est de représenter un objet rugueux et $S(x)$ lisse, alors l'argument est "S'il existe un objet qui est rugueux ou lisse, alors soit il existe un objet rugueux, soit il en existe un objet lisse".

Normalement, il est conseillé de commencer une preuve de déduction naturelle du bas vers le haut, en effectuant des règles d'introduction à l'envers sur l'opérateur principal jusqu'à ce que vous ne puissiez pas aller plus loin, puis en passant au sommet et en descendant des locaux par des applications successives d'élimination. règles jusqu'à ce que vous vous rencontriez, espérons-le, au milieu.
Dans ce cas, la conclusion est une disjonction, mais tenter l'introduction de la disjonction comme dernière étape ne mènera pas au succès, car cela nécessiterait une preuve de l'une des disjonctions, ce qui n'est évidemment pas possible, car vous ne pouvez pas en déduire ni les deux côtés bien sûr, seule la disjonction d'entre eux. Alors allez tout de suite en haut et commencez à démonter les locaux.

La seule prémisse qui vous est donnée est une déclaration existentielle, donc la première chose à faire est une élimination existentielle. L'élimination existentielle signifie que vous supposez l'énoncé quantifié pour un objet arbitraire (disons$a$), tirez une conclusion de cette hypothèse, alors, puisque vous savez qu'au moins un tel objet existe, vous pouvez en déduire la conclusion à coup sûr. La conclusion à laquelle vous voulez arriver est$\exists x R(x) \lor \exists x S(x)$, alors essayez de dériver que sous l'hypothèse $R(a) \lor S(a)$:

| exists x(R(x) v S(x))
| | R(a) v S(a)
| | -----------
| | ...
| | exists x R(x) v exists x S(x)
| exists x R(x) v exists x S(x)

La prochaine chose du haut est la disjnction $R(a) \lor S(a)$. Donc, vous effectuez une élimination de disjonction, ce qui signifie que vous supposez chacun des disjoints, tirez la même conclusion des deux, puis concluez que, comme au moins l'un des deux côtés est vrai, la conclusion suit à coup sûr. La conclusion à déduire à la fin, et dans les deux sous-épreuves, est à nouveau$\exists x R(x) \lor \exists x S(x)$: