Logik - Reduzieren einer Logik erster Ordnung mit einer Materialbedingung

Question

Nehme an, dass $$ \forall x \forall y: P(x,y) \implies Q(x) $$ und $$ \forall x \exists y: P(x,y) $$

Darf ich daraus schließen? $$ \forall x: Q(x) $$

Wenn es wahr ist, was ist der Grund dafür?

Was ich versucht habe:

$$ \begin{align} &\forall x \forall y: P(x,y) \implies Q(x)\\ &\iff \forall x \forall y:\lnot P(x,y) \lor Q(x)\\ &\iff \forall x: (Q(x) \lor \forall y:\lnot P(x,y))\\ &\iff \forall x: (Q(x) \lor \lnot (\exists y:P(x,y))) \end{align} $$ Kombinieren Sie das Ergebnis mit $\forall x \exists y: P(x,y)$Ich kam zu dem Schluss $Q(x)$ sollte für alle gelten $x$ schon seit $\lnot (\exists y:P(x,y))$ ist immer falsch.

$$ \begin{align} &\forall x: (Q(x) \lor \lnot (\exists y:P(x,y))) \land \forall x \exists y: P(x,y)\\ &\iff \forall x: ((Q(x) \lor \lnot (\exists y:P(x,y))) \land \exists y: P(x,y))\\ &\iff \forall x: (Q(x) \land \exists y: P(x,y))\\ &\implies \forall x: Q(x) \end{align} $$

Answer 1

Das ist alles richtig. Für diesen letzten Schritt können Sie tatsächlich die Verteilung von verwenden$\forall$ Über $\land$ nochmal:

$$\forall x : (Q(x) \land \exists y : P(x,y))$$

$$\Leftrightarrow$$

$$\forall x : Q(x) \land \forall x \exists y : P(x,y))$$

$$\Rightarrow$$

$$\forall x : Q(x)$$

Sie haben noch keine formalen Ableitungen gelernt?

Answer 2

Wenn es wahr ist, was ist der Grund dafür?

$\def\boxit#1{\bbox[lemonchiffon,0.5ex]{#1}}$Wir haben Räumlichkeiten von $\boxit{\forall x~\forall y:(P(x,y)\to Q(x))}$ und $\boxit{\forall x~\exists y:P(x,y)}$. Sollten wir eine beliebige Variable nehmen,$\boxit a$, dann schließen wir aus der zweiten Prämisse, dass es eine Zeugenvariable gibt, nennen wir es $\boxit b$, was befriedigt $\boxit{P(a,b)}$. Für diese Variablen schließen wir auch aus der ersten Prämisse, dass$\boxit{P(a,b)\to Q(a)}$wird zufrieden sein. Aus dem Modus Ponens schließen wir daraus$\boxit{Q(a)}$ist befriedigt. Schon seit$\boxit b$ tritt in dieser Anweisung nicht auf, und $\boxit a$ ist willkürlich, wir haben daher gezeigt, dass $\boxit{\forall x:Q(x)}$ ist durch diese Räumlichkeiten verbunden.

$$\def\fitch#1#2{~~~~{\begin{array}{|l}#1\\\hline#2\end{array}}}\fitch{~~1.~\forall x\,\forall y:(P(x,y)\to Q(x))\hspace{3.5ex}\textsf{Premise}\\~~2.~\forall x\,\exists y:P(x,y)\hspace{14ex}\textsf{Premise}}{\fitch{~~3.~\boxed a\hspace{23.5ex}\textsf{Assumption (Arbitrary)}}{~~4.~\forall y:(P(a,y)\to Q(a))\hspace{4ex}\textsf{Universal Elimination, 1}\\~~5.~\exists y:P(a,y)\hspace{14.5ex}\textsf{Universal Elimination, 2}\\\fitch{~~6.~\boxed b~P(a,b)\hspace{13.5ex}\textsf{Assumption (Witness)}}{~~7.~P(a,b)\to Q(a)\hspace{8ex}\textsf{Universal Elimination, 4}\\~~8.~Q(a)\hspace{18.5ex}\textsf{Conditional Elimination, 6, 7}}\\~~9.~Q(a)\hspace{21.5ex}\textsf{Existential Elimination 5, 6-8}}\\10.~\forall x:Q(x)\hspace{19.75ex}\textsf{Universal Introduction, 3-9}}$$