Ist diese Prädikatenlogiksequenz gültig?

Oct 13 2020

Dies ist vielleicht eine dumme Reihe verwandter Fragen, und das Folgende ist das Problem, das sie ausgelöst hat.

Ich werde gebeten, diese Prädikatenlogik zu beweisen:

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

Ich schäme mich zu sagen, dass ich es nicht beweisen kann. Ich habe den direkten Ansatz sowie einen Beweis durch Widerspruch versucht, ohne Glück. Und dann wurde mir klar, dass die Frage vielleicht falsch ist. Vielleicht gibt es keinen Beweis. Wenn ich nicht in der Lage bin, eine Folge zu beweisen, bedeutet dies natürlich nicht, dass sie ungültig ist, und daher weiß ich nicht einmal, ob die Frage falsch formuliert ist. Wenn dies eine Satzlogikfrage wäre und die Anzahl der Satzatome ausreichend klein wäre, könnte ich eine Wahrheitstabelle erstellen und auf semantische Konsequenzen prüfen. Eine Satzfolge ist gültig, wenn sie semantisch bedingt ist, und daher könnte eine Wahrheitstabelle sie ungültig machen. Mit dem Prädikat Logic und seinen Quantifizierern habe ich jedoch in diesem Fall keine Erfahrung mit der Überprüfung von Wahrheitstabellen und kann daher nicht einmal wissen, ob die Sequenz ungültig ist.

Mit einem englischen Argument kann ich es ungültig machen, indem ich es zulasse $R(x)$ bedeuten $x$ ist ein raues Objekt und $S(x)$ Bedeutung $x$ ist ein glattes Objekt:

"Prämisse: Es gibt ein raues Objekt wie eine Körnung. Fazit: Es gibt ein glattes Objekt wie ein Kugellager."

Der Satz ist aussagekräftig, weil die Prämisse und die Schlussfolgerung wahr sind. Aber logischerweise ist es ungültig. Die Existenz eines rauen Objekts impliziert nicht die Existenz eines glatten Objekts. (Randnotiz: Was besonders verwirrend ist, ist, dass ich jetzt die Kerndomäne der Aussagenlogik verlassen und in eine Domäne eingetreten bin, die sich "subjektiver" anfühlt und frustrierend ist.)

Das logische Argument auf Englisch enthält jedoch keine "Strenge".

Fragen:

Ist die obige Sequenz gültig?
Wenn Sie wissen, dass es gültig ist, weil Sie es anhand von Abzugsregeln bewiesen haben, hören Sie hier auf
Wenn es keinen Beweis gibt, wie können Sie beweisen, dass er ungültig ist? Verwenden Sie Wahrheitstabellen?

Antworten

2 lemontree Oct 13 2020 at 19:23

Die Folgerung ist gültig und ableitbar.

Im Allgemeinen besteht ein Gegenbeispiel zu einer ungültigen Folgerung aus einer Struktur, in der alle Prämissen wahr sind, die Schlussfolgerung jedoch falsch ist.

Ihr Argument ist falsch, weil es nicht genau zeigt (durch die Bereitstellung eines konkreten Gegenmodells), dass diese Interpretation der Prädikate die Folge ungültig macht, und Ihr englisches Beispiel keine angemessene Deformalisierung der Aussage darstellt: Sie können nicht einfach fallen lassen eines der Disjunkte in jedem der Sätze. Wenn$R(x)$ ist für ein raues Objekt zu stehen und $S(x)$ glatt, dann lautet das Argument "Wenn ein Objekt existiert, das rau oder glatt ist, dann existiert entweder ein raues Objekt oder es existiert ein glattes".

Normalerweise ist es ratsam, einen natürlichen Abzugsnachweis von unten nach oben zu starten, indem Sie beim Hauptoperator Rückwärtseinführungsregeln ausführen, bis Sie nicht mehr weiter kommen, dann nach oben wechseln und sich durch aufeinanderfolgende Eliminierungsanwendungen von den Räumlichkeiten nach unten arbeiten Regeln, bis Sie sich hoffentlich in der Mitte treffen.
In diesem Fall ist die Schlussfolgerung eine Disjunktion, aber der Versuch, die Disjunktion als letzten Schritt einzuführen, führt nicht zum Erfolg, da dies einen Beweis für eine der Disjunktionen erfordern würde, was offensichtlich nicht möglich ist, da Sie keine davon ableiten können die beiden Seiten sicher, nur die Disjunktion von ihnen. Gehen Sie also sofort nach oben und beginnen Sie mit der Demontage der Räumlichkeiten.

Die einzige Voraussetzung, die Ihnen gegeben wird, ist eine existenzielle Aussage. Das erste, was Sie tun müssen, ist eine existenzielle Eliminierung. Existenzielle Eliminierung bedeutet, dass Sie die quantifizierte Aussage für ein beliebiges Objekt annehmen (z$a$), leiten Sie aus dieser Annahme eine Schlussfolgerung ab. Da Sie wissen, dass mindestens ein solches Objekt vorhanden ist, können Sie die Schlussfolgerung mit Sicherheit ableiten. Die Schlussfolgerung, zu der Sie gelangen möchten, ist$\exists x R(x) \lor \exists x S(x)$Versuchen Sie also, dies unter der Annahme abzuleiten $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)

Das nächste, was von oben kommt, ist die Trennung $R(a) \lor S(a)$. Sie eliminieren also die Disjunktion, was bedeutet, dass Sie jedes der Disjunkte annehmen, aus beiden die gleiche Schlussfolgerung ableiten und dann zu dem Schluss kommen, dass die Schlussfolgerung mit Sicherheit folgt, da mindestens eine der beiden Seiten gilt. Die Schlussfolgerung, die am Ende und in den beiden Subproofs zu schließen ist, ist erneut$\exists x R(x) \lor \exists x S(x)$::