Hacker News Reader

Hacker News

Comment by dananabread | Hacker News Reader

Parent Full thread

dananabread

Is there an intuition for this correspondence otherwise I don't think it's very helpful

View on HN

There is:

The neutral element for + is 0 (x + 0 = x for any x).

The neutral element for * is 1 (x * 1 = x for any x).

Furthermore, you have arithmetic properties like x * 0 = 0 for any x (annulation) or (x + y) * z = (x * z) + (y * z) for any x, y, z (distributivity).

Similarly:

The neutral element for OR is false (x OR false = x for any x).

The neutral element for AND is true (x AND true = x for any x).

Furthermore, x AND false = false for any x, and (x OR y) AND z = (x AND z) OR (y AND z) for any x, y, z.

So OR works very much like + algebraically, and AND works very much like *.

When using 0 and 1 for false and true, AND is exactly the same as multiplication, and OR is like addition with saturation arithmetics (i.e. 1 + 1 = 1).

The common precedence rules stem from those parallels.

I've never heard of saturation arithmetic and now it all makes sense. Otherwise I thought it was more common to think of XOR as boolean addition, and OR would be represented as xy + x + y.

Yes, true and false with AND and XOR form a mathematical ring [0]. Still, OR is also an additive operation. IMO one could give OR and XOR the same precedence.

On the other hand, there is no strict need to have a dedicated boolean XOR operator, as it works the same as = (equals).

[0] https://en.wikipedia.org/wiki/Ring_(mathematics)

More than just a ring, it is the simplest finite field.

Saturation is actually the wrong way to think about bools when other operations get involved:

saturate(0 - 1) = 0

bool(0 - 1) = 1

Fun (but not particularly useful fact) is you can also represent x OR y as 1 - (1 - x)(1 - y). This shouldn't be too weird since x OR y is equal to NOT ((NOT x) AND (NOT y)).

There's also a connection to probability: if you want the probability of A and B and C happening and they're independent, it's P(A) * P(B) * P(C). If you want the probability of A or B or C happening and they're mutually exclusive, it's P(A) + P(B) + P(C).

Similar analogue for set theory, as another commenter pointed out.

I always remember it in terms of set operations. && corresponds to set intersection, while || corresponds to set union. The union operation is similar to "adding" two sets together. You also have the distributive property: a && (b || c) == (a && b) || (a && c).

The analogy isn't perfect, because || is also distributive over &&, but addition isn't distributive over multiplication. I think this is actually one of the essential properties that distinguishes a Boolean algebra from a ring. Someone with more knowledge of abstract algebra could probably provide more insight here, though.

Conjunction used to be called logical product, and disjunction logical sum, for the reason the other commenters pointed out.

a * b * c is only nonzero if all of a, b, c are nonzero. That's AND, and should be pretty intuitive.

a + b + c is nonzero if any of them are nonzero. (Remember each value is either 0 or 1.) So that's the intuition for OR.

a+b+c is nonzero if any of a or b or c are nonzero.

Yeah I just added that. I was hesitant initially cause you have to also note they're nonnegative, and that you're treating them like real numbers rather than mod 2.

Natural numbers are the natural numbers for me! (ISO 80000-2, of course)

IMO the intuition is to not use any intuition at all: there aren't built-in booleans in C, true is a #define for 1 and false is a #define for 0. For C conditionals, 0 = false, nonzero = true. So

a+b != 0 <=> a!=0 or b!=0

a*b != 0 <=> a!=0 and b!=0

Of course this intuition also reveals the pitfall behind this correspondence! You'd better make sure those are unsigned ints or #defined booleans, so you're not using general C expressions. 1 || -1 is true but 1 + (-1) is false.

Edit: forgot to mention: INT_MAX || 1 is true, but what about INT_MAX + 1 :)

"true is a #define for 1" is bad idea. Because when `x` is, say, `2` then `if x` is not the same as `if x==true`.

That's just the way C is. If you want to check "truthiness" (as much as you can in C), just do 'if x'.

Something nice in C is that "if (x)" is always equivalent to "if (x != 0)". NULL is a macro for 0, and so is false. Boolean expressions evaluate to 0 if they don't hold. This isn't true in C++, though.

Then what is _Bool, if not a built in boolean type?

I genuinely forgot stdbool.h existed, I don't actually write that much C myself.

My point was more around the conditionals being weakly typed around unsigned ints rather than a specific lack of built-ins. A lot of commenters were going into arithmetic mod 2 or philosophical issues, neither of which actually apply here.

_Bool isn't part of stdbool. It's a language keyword. C23 introduces full support for bool with true and false as keywords.

Kudos to the people that responded to explain why the correspondence is helpful.

Yes, sometimes logical AND called logical multiplication and logical OR called logical summation.

It seems clear for me, because I remember learning De Morgan's Laws in electronics class and from one specific level of Turing Complete game.

this is the notation used in the chapters about boolean algebra in my digital design course. I think it's pretty neat. I honestly never looked into operator precedence in any language enough to notice the relation.

Reply on news.ycombinator.com