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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Dec 6, 2016 at 23:44
  • $\begingroup$ @TimothyChow ah yes, that's it. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Dec 7, 2016 at 0:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .