Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Is it homework? What have you tried? Are you familiar with the steps to transform into prenex normal form for universal quantifiers? –  hardmath Nov 18 '12 at 16:49
    
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. –  Max Nov 18 '12 at 17:36
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
i Transform (2) : $$((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow ((\exists{y})a(y) \Rightarrow (\exists{z})b(z)) (\sim (\exists{x})(\sim a(x) \lor b(x))) \lor (\sim ((\exists{y})a(y)) \lor (\exists{z})b(z)) \Leftrightarrow (\forall{x})(\sim a(x) \lor b(x)) \lor (\forall{y})\sim a(y) \lor (\exists{z})b(z) $$ and knowing that $\forall{x}/\exists{x}(a(x) \lor/\land b) \Leftrightarrow (\forall{x}/\exists{x}a(x)) \lor/\land b $ i get: $$(\exists{z})(\forall{y})(\forall{x})(\sim a(x) \lor b(x)) \lor \sim a(y) \lor b(z)$$ Am i right? –  Max Nov 18 '12 at 17:36
    
Max, I'm not clear what you are saying. I am working with the statement you posted. In the left-hand side of the implication of $(1)$, the scope the the existentially quantified $x$ is the entire implication $(a(x) \Rightarrow b(x))$. Yes, you are correct that $\forall x(a(x) \lor b(y)) \iff \forall x(a(x)) \lor b(y)$; that is $y$ is a "free" variable. How does that relate to your question? You have only existential quantifiers in your question. If you also have the premise (not posted) from which you derived you posted statement (in your question), then your derivation is incorrect. –  amWhy Nov 18 '12 at 17:37
    
I deleted my first (unfinished) comment because i had editing issues. What I was basically doing was trying to find a way to pull the quantifiers to the front, but i didn't know which rules to use. I thought that maybe if i transform the material conditional into logical disjunction I will be able to solve this task but it is not worth the hassle. I think the solution i posted in my comment to Peter Smith's answer is correct, which you just confirmed in your post. Thanks! –  Max Nov 18 '12 at 18:06
    
Max - Almost correct, see $(2)$ above: $(\exists z) b(z)$ you need that last occurrence of $b( )$ to be the quantified $z$, not "x", as in your post below Peter's answer. –  amWhy Nov 18 '12 at 18:08
    
Oh, it's a typo that i must've overlooked. Also, you wrote that $(\exists r)(p(r)) \iff \lnot\lnot (\exists r)(p(r)) \iff \lnot(\forall r)(\lnot p(r))$ might be helpful but what should i do with that one negation? I came up with a very simple example that i tried to do, but i don't know if my reasoning is proper (most likely not) and if i even need your advise here: $ ((\exists{x})a(x) \Leftrightarrow \forall{x}\ b(x,y))\Leftrightarrow \lnot (\forall{x} \lnot a(x)) \Leftrightarrow (\forall{z})\ b(z,y) \Leftrightarrow (\lnot (\forall{x}))(\forall{z})(a(x)\Leftrightarrow b(z,y)) $ –  Max Nov 18 '12 at 18:25
show 1 more comment

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???)
share|improve this answer
    
just like this?:$$((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow ((\exists{y})a(y) \Rightarrow (\exists{z})b(z)) \Leftrightarrow ((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow (\exists{y})(\exists{z})(a(y) \Rightarrow b(x)) \Leftrightarrow (\exists{y})(\exists{z})((\exists{x}) (a(x) \Rightarrow b(x)) \Rightarrow (a(y) \Rightarrow b(x))$$ –  Max Nov 18 '12 at 17:39
    
No. Note $(\exists v\varphi(v) \to B)$ is equivalent to $(\neg\exists v\varphi(v) \lor B)$ is equivalent to $(\forall v\neg\varphi(v) \lor B)$ is equivalent to $\forall v(\neg\varphi(v) \lor B)$ is equivalent to $\forall v(\varphi(v) \to B)$ –  Peter Smith Nov 18 '12 at 18:33
    
So the good answer is: $((\exists{x})(a(x) \Rightarrow b(x)) \Rightarrow ((\exists{y})a(y) \Rightarrow (\exists{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)))$ –  Max Nov 19 '12 at 7:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.