0
$\begingroup$

Using only logical symbols and "$+, \cdot$" translate into a first-order logic: "$c$ is not the greatest common factor of $a$ and $b$". Assume that all variables are positive integers.

I have attempted to solve this but I am not sure if my reasoning is good. Neither am I sure whether I am not lacking quantifiers.
$$\neg((\exists\alpha)(\exists\beta)(a= \alpha c\land b= \beta c) \land (\forall d)((\exists \gamma)(\exists\delta)(a=\gamma d\land b= \delta d) \Rightarrow d \le c))$$
What do you think of my solution?

$\endgroup$
  • 1
    $\begingroup$ General comment. If you write your logic out in English first you're more likely to get it right and it will be easier for folks here to check. Start with "$c$ is the gcd if it divides $a$ and $b$ and ...", convert to formalism, and negate. $\endgroup$ – Ethan Bolker Nov 27 '17 at 20:00
1
$\begingroup$

Looks good, but I agree with Clive that you'll need to capture the $\le$ using symbols you are allowed to use. But to avoid using a $1$ as well, I propose:

$$d \le c \Leftrightarrow (d =c \lor \exists x \ d +x = c)$$

$\endgroup$
1
$\begingroup$

That looks pretty much correct, except that you've used the symbol $\le$, which is not a logical symbol and is not $+$ or $\cdot$. However, you can express $d \le c$ using only $+$, $\cdot$ and logical symbol by observing that $$d \le c \quad \Leftrightarrow \quad (\exists k)(c+1=d+k)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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