1
$\begingroup$

This is the sentence that needs to be transformed: ∃x∀y(Ax → (Bxy ∨ ¬Cy)) → ∀x∃y(Py → Qyx) I have gotten to the point where I eliminated all occurrences of → and imported all negations inside all other logical connectives. Which lead me here:

∃x∀y(Ax ∧ ¬Bxy ∧ Cy) ∨ ∀x∃y(Py ∧¬ Qyx)

But I can't seem to pull the quantifiers in front.

$\endgroup$
2
  • $\begingroup$ you forgot to negate the quantifiers, after eliminated all $\to$, you should have \begin{align} &∃x∀y(Ax\to(Bxy\lor¬Cy)) \to ∀x∃y(Py \to Qyx)\\ =&\forall x\exists y(Ax\land\neg Bxy\land Cy)\lor\forall x\exists y(\neg Py \lor Qyx)\\ \end{align} $\endgroup$
    – Ethan
    Commented May 19, 2020 at 20:54
  • $\begingroup$ Thank you for the correction! $\endgroup$
    – Kat W.
    Commented May 19, 2020 at 20:58

1 Answer 1

Reset to default
3
$\begingroup$

I can't seem to pull the quantifiers in front.

To pull out the quantifiers, we will need to apply some quantifier distributive laws such that $$∀x(Px)∨∀x(Q)↔∀x(Px∨Q)\tag{1}$$ $$∃y(Py)∨∃y(Qy)↔∃y(Py∨Qy)\tag{2}$$ Then we start from \begin{align} &\forall x\exists y(Ax\land\neg Bxy\land Cy)\lor\forall x\exists y(\neg Py \lor Qyx)\\ =&\forall x_1\forall x_2(\exists y(Ax_1\land\neg Bx_1y\land Cy)\lor\exists y(\neg Py \lor Qyx_2))\tag*{By $(1)$}\\ =&\forall x_1\forall x_2\exists y((Ax_1\land\neg Bx_1y\land Cy)\lor(\neg Py \lor Qyx_2))\tag*{By $(2)$}\\ \end{align} Now you can put them into conjunctive normal form.

Note : As @user400188 mentioned, to avoid unnecessary confusion, we could just replace $(1)$ with $$\forall x_1(Px_1)\lor\forall x_2(Qx_2)\leftrightarrow \forall x_1\forall x_2(Px_1\lor Qx_2)$$ or equivalently we can also apply the original $(1)$ twice.

$\endgroup$
10
  • $\begingroup$ Is $(1)$ meant to be missing an $x$ in $Qx$? If it isn't, then $(1)$ is correct but not the rule you used between line 1 & 2 of the second paragraph, and if it is, then it should be an implication not a biconditional. $\endgroup$
    – user400188
    Commented May 20, 2020 at 9:56
  • $\begingroup$ @user400188 yes, it's just $Q$, like you mentioned, otherwise it won't hold, and i see the confusion, this is becuase two $x$ are in different scope of quantifiers, in another words they are not the same $x$, and in that step we applied $(1)$ twice $\dots$ $\endgroup$
    – Ethan
    Commented May 20, 2020 at 14:33
  • $\begingroup$ I believe if we write it in the following way, this confusion might gone \begin{align} &\forall \color{red}{x_1}\exists y(A\color{red}{x_1}\land\neg B\color{red}{x_1}y\land Cy)\lor\forall \color{blue}{x_2}\exists y(\neg Py \lor Qy\color{blue}{x_2})\\ =&\forall \color{red}{x_1}\forall \color{blue}{x_2}(\exists y(A\color{red}{x_1}\land\neg B\color{red}{x_1}y\land Cy)\lor\exists y(\neg Py \lor Qy\color{blue}{x_2}))\tag*{By $(1)$}\\ \end{align} Thanks for the question $\overset{\cdot~\cdot}\smile$ $\endgroup$
    – Ethan
    Commented May 20, 2020 at 14:33
  • 1
    $\begingroup$ @user400188 Thanks for the suggestion, that's right, I just added some notes. $\endgroup$
    – Ethan
    Commented May 24, 2020 at 23:22
  • 1
    $\begingroup$ I see what you did now, $\forall x\exists y(\lnot Px\lor Qxy)$ does not depend on the same $x$ as $\forall x\exists y(Ax\land\lnot Bxy\land Cy)$, and can then be treated as the $Q$ in your expression $(1)$. Sorry for my mistake, you do not actually need the note at the end. $\endgroup$
    – user400188
    Commented May 25, 2020 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .