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

2

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
    Yep, I see it now, it's senseless to assign some true-false value to d here, thank you :)2012-11-23
4

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. Tha$n$k you a lot :)2012-11-23