0
$\begingroup$

Transform this formula so that all the quantifiers are located at the beginning of the formule:

$\big((\exists{x})(a(x) \Rightarrow b(x)\big) \Rightarrow \big((\exists{x})a(x) \Rightarrow (\exists{x})b(x)\big) $

  • 0
    This is not my homework. I've been absent from a couple of clases and I'm trying to catch up with the material, but since i have no notes and can't find appropriate books i came to this site for help.2012-11-18

2 Answers 2

3

Note: Each existential quantifier in your statement is limited in its scope.

$((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow ((\exists{x})a(x) \Rightarrow (\exists{x})b(x)) \tag{1}$

The following statement is equivalent to $(1)$:

$((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow ((\exists{y})a(y) \Rightarrow (\exists{z})b(z)).\tag{2}$

The quantified variables first need to be disambiguated in $(1)$, as shown in $(2)$ - to transform $(1)$ into a statement with all quantifiers at the start of the statement.

I'll let you take $(2)$ from here. Most of the work is simply keeping straight what's being quantified, and where.

Care must be taken with respect to quantifiers that appear in the antecedent of an implication, when transforming such statements so all quantifiers appear at the start of the entire statement. In this case, it turns out, that the final representation leaves the quantifiers unchanged.

But as you'll see with your more complicated case (the one you posted in your final comment below, that's not always the case.


EDIT: In response to the work shown in the comments below (user please do not delete comments below):

Slow down a bit: From $(2)$, and given the question you posted above, we can, if need be, bring all the quantifiers to the start, as there three existentially quantified variables. $(\exists x)(\exists y)(\exists z)\left((a(x) \Rightarrow b(x)) \Rightarrow (a(y) \Rightarrow b(z))\right).\tag{3}$

  • 0
    Sorry, I deleted that part of my answer before seeing your comment and thought it wasn't helpful to the problem at hand. Perhaps you should post your "simple example" as a separate question. Note that the$y$in your example is not bound by any quantifier and as such, is a free variable. But otherwise, looks good to me. But the "y" means nothing, as it stands.2012-11-18
2

Here's something more than a mere hint, but less than a full answer doing your homework for you!

  1. First change variables so that each quantifier gets a different variable. (Do you see why this is a good idea to help keep track of things?)
  2. Now you need two transformation rules for pulling quantifiers to the front, one to deal with wffs of the form $(A \Rightarrow (Ev)\varphi(v))$ where $v$ doesn't occur in $A$, and one to deal with wffs of the form $((Ev)\varphi(v) \Rightarrow B)$ where $v$ doesn't occur in $B$. (Do you know the rules??)
  3. Be methodical and work step by step, 'from the inside out'. (Do you see the sort of sequence of steps you need???)
  • 0
    So the good answer is: $((\e$x$ists{x})(a(x) \Rightarrow b(x)) \Rightarrow ((\exists{$y$})a(y) \Rightarrow (\e$x$ists{z})b(z)) \Leftrightarrow ((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow (\forall{$y$})(\exists{z})(a(y) \Rightarrow b(x)) \Leftrightarrow (\forall{y})(\exists{z})(\forall{x}) ((a(x) \Rightarrow b(x)) \Rightarrow (a(y) \Rightarrow b(x)))$2012-11-19