8
$\begingroup$

The J Programming langauge has an operator which acts as both the GCD and boolean Or. The J Primer has this note about it:

The GCD is a useful extension of the domain of the or function to non-boolean arguments.

As J is a highly mathematical language, I assume this extension has a basis in mathematics as well.

In what sense, if any, can the the GCD be considered an "extension" of boolean "Or"?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Boundary cases of the gcd function are usually (but not always) defined like gcd$(0,0)=0$ and gcd$(0,1)=1$. And of course gcd$(1,1)=1$. So if boolean is mapped to integer as F=0,T=1, gcd agrees with OR. $\endgroup$
    – Brendan McKay
    Dec 6, 2016 at 6:51
  • 5
    $\begingroup$ GCD is the meet (max) of the exponents of primes, and meet, union, OR are synonymous in lattice theory. $\endgroup$
    – Fan Zheng
    Dec 6, 2016 at 7:08
  • $\begingroup$ @FanZheng Are you making a separate point or a point related to the one Bjorn makes in his answer? $\endgroup$
    – Jonah
    Dec 6, 2016 at 13:39

2 Answers 2

Reset to default
18
$\begingroup$

In the ordering $\preceq$ of nonnegative integers by divisibility, 1 is the least element and 0 is the greatest, and we have for instance $$ 1\preceq 2\preceq 6\preceq 12\preceq\dots\preceq 0.$$ In this ordering, gcd is the same as meet (greatest lower bound), which is dual to least upper bound, which is what boolean OR is for $\{0,1\}$.

So it makes sense if you think of numbers as "degrees of truth", where multiplicative factors are evidence of falsehood.

See also: What is gcd(0,0)?

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Great answer. Is the idea of degrees of truth and factors as evidence of falsehood used in any formal theory you know of -- perhaps fuzzy logic or something related? $\endgroup$
    – Jonah
    Dec 6, 2016 at 14:07
  • $\begingroup$ @Jonah I kind of doubt anyone would use it that way except as an example $\endgroup$
    – Bjørn Kjos-Hanssen
    Dec 6, 2016 at 16:09
  • $\begingroup$ @Jonah : Forcing in set theory employs partially ordered sets whose elements could be thought of as "degrees of truth" but I am not aware of applications of forcing that use the partial ordering of nonnegative integers by divisibility. $\endgroup$
    – Timothy Chow
    Dec 6, 2016 at 23:42
1
$\begingroup$

I don't think there is anything deeper here than that J gives gcd the same values as OR when the arguments are 0 or 1. That is all it says on the web page you link to. It just means that J computes gcd$(1,1)=1$, gcd$(0,1)=1$ and gcd$(0,0)=0$. Only the last one is not standard (gcd$(0,0)$ is often considered as undefined).

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Do you know why gcd(0,0) is often considered as undefined? $\endgroup$
    – Bjørn Kjos-Hanssen
    Dec 6, 2016 at 18:52
  • $\begingroup$ @BjørnKjos-Hanssen : I think it is because if you read the phrase "greatest common divisor" literally, then there is no such thing as the greatest common divisor of 0 and 0 since every positive integer divides 0. $\endgroup$
    – Timothy Chow
    Dec 6, 2016 at 23:44
  • $\begingroup$ @TimothyChow ah yes, that's it. $\endgroup$
    – Bjørn Kjos-Hanssen
    Dec 7, 2016 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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