1
$\begingroup$

So I had a task "Formulate a statement d=GCD(a,b,c) using quantifiers" on my exam which was marked as wrong - however, I don't know why is that wrong so could anybody please help me understand? I formulated it as:

$\exists_{d}\forall_{k}(((k|a)\land(k|b)\land(k|c))\Rightarrow d\geq k)$

I had the first term ($\exists_{d}$) marked as wrong. Why is that so?

2 Answers 2

1

You forgot to say that $d$ divides $a,b,c$, but let's assume you put that in. The problem is that the statement you are asked to formulate says that some specific $d$ is the gcd of some specific triple $a,b,c$. So the $\exists d$ shouldn't be there. Your statement is trying to say "$a,b,c$ has a gcd", but it should say "$d$ is the gcd of $a,b,c$".

  • 0
    Oh, I see. Thank you a lot. But how can I use the quantifiers to show such a statement? I mean: I can't just do $d=$ and write down all the rest so how should one do it? Also, thank you a lot for the disclaimer about d dividing a,b,c - shamefully, I don't remember if I wrote _that_ down or not :)2012-11-23
  • 0
    The only quantifier you need is for $k$. You don't have one for $a,b,c$ after all. Do you see how to do it now?2012-11-23
  • 0
    Hm... So something like $d=\forall_{k}(...)$? It doesn't look right to me but I never did quantifier-things with an equal sign between so maybe it's right... Is it?2012-11-23
  • 0
    No, this is a type error! Martini has it right.2012-11-23
  • 0
    Yep, I see it now, it's senseless to assign some true-false value to d here, thank you :)2012-11-23
3

To answer your question in the comment to @mt_'s answer. First say that $d$ divides $a$, $b$ and $c$: $$ (d \mid a) \land (d \mid b) \land (d \mid c) $$ Then add your statement but without the existential quantifier: $$ \forall k. \bigl((k \mid a )\land (k \mid b) \land (k \mid c) \bigr)\to k \le d $$ So you get $$ (d \mid a) \land (d \mid b) \land (d \mid c) \land \forall k. \bigl((k \mid a )\land (k \mid b) \land (k \mid c) \bigr)\to k \le d $$

  • 0
    Ooh, I see. Thank you a lot :)2012-11-23