3
$\begingroup$

I got one question which says;

Write a formula corresponding to: 1. “a is the greatest common divisor of b and c” 2. “a is the least common multiple of b and c” Use logical symbols, brackets, · and =. Any other symbols need to be defined.

it seems easy but can someone help me with that ?

$\endgroup$
  • $\begingroup$ Don't you need something to represent smaller than, i.e a $<$ or $\le$ symbol? $\endgroup$ – Bram28 Nov 14 '17 at 2:31
7
$\begingroup$

Do it in steps:

  1. "$a$ is a divisor of $b$": $\exists k_1\;a\cdot k_1 = b$.
  2. "$a$ is a divisor of $c$": $\exists k_2\;a\cdot k_2 = c$.
  3. "$a$ is a common divisor of $b$ and $c$": $(\exists k_1\;a\cdot k_1 = b) \land (\exists k_2\;a\cdot k_2 = c)$.
  4. "$a$ is the greatest integer satisfying $P(a)$": $P(a) \land (\forall x\;P(x) \implies x \le a)$.

Substituting the third step into the fourth, we get $$(\exists k_1\;a\cdot k_1 = b) \land (\exists k_2\;a\cdot k_2 = c) \land (\forall x\;((\exists k_1\;x\cdot k_1 = b) \land (\exists k_2\;x\cdot k_2 = c)) \implies x \le a)$$ which represents "$a$ is the greatest common divisor of $b$ and $c$".

There are variations on each of these steps, variations in the notation, and you might be working with a different set of primitives allowed, so you should adjust this to your own needs. For example, if you're not allowed $\le$, then you should proceed from step 3 to trying to write a statement like

  1. "$a$ is a common divisor of $b$ and $c$, and if $x$ is a common divisor of $b$ and $c$, then $x$ divides $a$"

which is an equivalent characterization of GCD.

Writing up LCM is more or less the same, except you stand on your head while you do it.

$\endgroup$
0
$\begingroup$

I don't know what language you are talking about, but here is a little something I wrote up out of boredom. Hope it helps!

Let $a|b$ mean "$a$ divides $b$", let $\geq$ mean "greater than or equal to.

$a |b \wedge a|c \wedge \forall y (y |b \wedge y|c \rightarrow a\geq y))$

"$a$ divides $b$, $a$ divides $c$, and for all $y$, if $y$ divides $b$ and $y$ divides $c$, then $a$ is greater than or equal to $y$"

And for the other one... let $xy=z$ mean $x$ times $y$ equals $z$ and $\leq$ mean less than or equal to.

$\exists n \exists m (bn=a \wedge cm=a) \wedge \forall y \exists x \exists z (bx=y \wedge cz=y \rightarrow a \leq y) $

"there is an $n$ and an $m$ such that $bn=a$ and $cm=a$ (in other words, $a$ is a multiple of $b$ and $c$), and for all $y$, if $y$ is a multiple of $b$ and $c$ then $a$ is less than or equal to $y$."

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