論理-材料条件を含む一階述語論理を減らす

Question

仮定 $$ \forall x \forall y: P(x,y) \implies Q(x) $$ そして $$ \forall x \exists y: P(x,y) $$

それでは、私はそれを結論付けることができますか $$ \forall x: Q(x) $$

それが本当なら、それの論理的根拠は何ですか？

私が試したこと：

$$ \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} $$ 結果を $\forall x \exists y: P(x,y)$、私は $Q(x)$ すべてに当てはまるはずです $x$ 以来 $\lnot (\exists y:P(x,y))$ 常に偽です。

$$ \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

それはすべて正しいです。その最後のステップでは、実際に次のディストリビューションを使用できます。$\forall$ 以上 $\land$ 再び：

$$\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)$$

あなたはまだ正式な派生を学んでいませんか？

Answer 2

それが本当なら、それの論理的根拠は何ですか？

$\def\boxit#1{\bbox[lemonchiffon,0.5ex]{#1}}$私たちはの前提を持っています $\boxit{\forall x~\forall y:(P(x,y)\to Q(x))}$ そして $\boxit{\forall x~\exists y:P(x,y)}$。任意の変数を取る必要があります、$\boxit a$、次に、2番目の前提から、証人変数があると推測し、それを呼び出します。 $\boxit b$、を満たす $\boxit{P(a,b)}$。これらの変数については、最初の前提から次のことも推測します。$\boxit{P(a,b)\to Q(a)}$満足します。したがって、モーダスポネンスによって、私たちはそれを推測します$\boxit{Q(a)}$満足しています。以来$\boxit b$ このステートメントでは発生しません。 $\boxit a$ は恣意的であるため、次のことを示しました。 $\boxit{\forall x:Q(x)}$ これらの前提に伴うものです。

$$\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}}$$