Logique - Réduire une logique du premier ordre impliquant un conditionnel matériel
Supposer que $$ \forall x \forall y: P(x,y) \implies Q(x) $$ et $$ \forall x \exists y: P(x,y) $$
Alors, puis-je conclure que $$ \forall x: Q(x) $$
Si c'est vrai, quelle en est la raison?
Ce que j'ai essayé:
$$ \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} $$ Combiner le résultat avec $\forall x \exists y: P(x,y)$, J'ai conclu que $Q(x)$ devrait être vrai pour tous $x$ depuis $\lnot (\exists y:P(x,y))$ est toujours faux.
$$ \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} $$
Réponses
C'est tout correct. pour cette dernière étape, vous pouvez utiliser la distribution de$\forall$ plus de $\land$ encore:
$$\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)$$
Vous n'avez pas encore appris les dérivations formelles?
Si c'est vrai, quelle en est la raison?
$\def\boxit#1{\bbox[lemonchiffon,0.5ex]{#1}}$Nous avons des locaux de $\boxit{\forall x~\forall y:(P(x,y)\to Q(x))}$ et $\boxit{\forall x~\exists y:P(x,y)}$. Devrions-nous prendre une variable arbitraire,$\boxit a$, alors nous déduisons de la deuxième prémisse qu'il existe une variable témoin, appelons-la $\boxit b$, qui satisfait $\boxit{P(a,b)}$. Pour ces variables, nous déduisons également du premier principe que$\boxit{P(a,b)\to Q(a)}$sera satisfait. Ainsi, par modus ponens, on en déduit que$\boxit{Q(a)}$est satisfait. Depuis$\boxit b$ ne se produit pas dans cette déclaration, et $\boxit a$ est arbitraire, nous avons donc montré que $\boxit{\forall x:Q(x)}$ est impliqué par ces prémisses.
$$\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}}$$