4 ms·

> (oneIsGreater * origArray[0]) + (twoIsGreater * origArray[1]) There is a reason why conjunction (AND) is also called logical multiplication, and disjunction

> (oneIsGreater * origArray[0]) + (twoIsGreater * origArray[1]) There is a reason why conjunction (AND) is also called logical multiplication, and disjunction (OR) logical addition. There is not much difference between this and: (oneIsGreater ? origArray[0] : 0) | (twoIsGreater ? origArray[1] : 0) This is often useful to think about when working on bitset or SIMD algorithms.

thaumasiotes 3y ago
> There is a reason why conjunction (AND) is also called logical multiplication, and disjunction (OR) logical addition. Really? The connection between AND and multiplication is obvious, but disjunction doesn't behave like addition. (For one thing, just like AND, it destroys information, which multiplication does do and addition doesn't.) Addition would usually be XOR. In fact, AND and XOR are what you get when you apply multiplication and addition to the integers (mod 2).
- dvt 3y ago
  It's called logical addition which is different than arithmetic addition, so it's best to not conflate the two. It's called "addition" because you "add" another propostion, creating a disjunction. And by the rules of logic, as long as the original proposition was true, the truth value is preserved no matter how many propositions you introduce (or "add"). A ⊢ ((A ∨ B) ∨ C) ... ∨ n
  - thaumasiotes 3y ago
    > It's called "addition" because you "add" another propostion, creating a disjunction. By that argument, conjunction is also called "addition". Perhaps there's a different reason? The choice of terminology, contrasting "logical addition" with "logical multiplication", obviously indicates that logical addition is supposed to be analogous to addition. What is the analogy?
    - andai 3y ago
      I don't know if this relates to formal logic, but in C a true value is defined as not zero, so all nonzero values are treated as the same value. So the only way to get a false is to OR (or add) two zeroes, making the two operations equivalent as far as boolean logic goes. Actually, you can add 1 and -1 to get 0, which breaks the model... Hmm... Guess it only works on natural numbers / unsigned.
    - EGreg 3y ago
      The analogy is deep. But actually the relationship is as follows: P(A u B) = P(A) + P(B) - P(A^B) P(A ^ B) = P(A u B) - P(A) - P(B) And to the guy who said xor is addition — no it’s not: P(A xor B) = P(A) + P(B) - 2 * P(A^B) In Probability, when you have a space of outcomes, doing a Union on two disjoint events (sets of outcomes) the probabilities add. Whereas doing an Intersection on two non-disjoint events those probabilities multiply. If two events have no outcomes in common, for instance, the probability of them both occurring is zero. When you “condition” probability on an event X happening, you restrict the space of all outcomes to that set X, and intersect every event with it. When you condiition B[n] = A[n] given that (A[n-1] AND … A[1]) having already happened, you have a sales funnel and each step is independent of the previous, so the probabilities multiply. It is also called a Markov Chain if you have a discrete set of possibilities at each step so you can form a matrix.
      - cubefox 3y ago
        Interesting, I never saw the arithmetic probability formula for xor. Though the original topic was truth values, not probabilities. To make it short, conjunctions in probability are multiplicative when they are independent, and disjunctions in probability are additive when they are mutually exclusive.
        EGreg 3y ago
        Well I actually came up with it on the spot. Just think of the venn diagram, and add the areas of A and B, which counts A^B twice, and then just remove it twice. :)
    - 3y ago
- moritzwarhier 3y ago
  Is there a way to express OR (not XOR) using integer arithmetic without case distinction or special functions in the natural numbers mod 2? Meaning, using only elementary arithmetic and modulo? Seems like there should be either an obvious answer or an interesting one :)
  - 201p 3y ago
    The maximum function.
    - moritzwarhier 3y ago
      Yeah that makes sense of course. Should have specified "special function", was aiming at "algebraic" or "polynomial" I guess. Then the answer seems to be no, right? Edit: The abs() function seems to be enough, awesome: https://math.stackexchange.com/a/1641271 https://math.stackexchange.com/a/1641271
      - deleted 3y ago
        [deleted]
      - adrian_b 3y ago
        The abs function works because it is equal to the maximum of x and -x. The logical "and" and logical "or" functions are precisely particular cases of the minimum and maximum functions. The so-called "exclusive or" function is simultaneously a particular case of addition and of subtraction, i.e. addition modulo 2 and subtraction modulo 2 are the same function. Therefore applying the 4 functions minimum, maximum, addition and subtraction to 1-bit numbers produces only 3 functions, AND, OR and XOR. It makes no sense to search other functions for expressing logical "and" and logical "or" except for minimum and maximum, because this is what they are. The search could only find alternative more complicated ways to express minimum and maximum. The minimum and maximum functions also work in logic systems with more than 2 values of truth. Also in hardware, analog circuits for minimum and maximum are one of the 2 ways of implementing the logical "and" and "or" functions, the other way being with series and parallel connections. The main mistake of George Boole was his unsuccessful attempt to find an equivalence between logical "and" and "or" and integer multiplication and addition, because he was not habituated to use minimum and maximum, so he did not see the correct relationships. The functions maximum and minimum are arithmetic functions as important as addition and subtraction. The only reason for which they have not been counted among the basic arithmetic functions is because when computed by a human they required much less effort than even addition, so there was no need for a long training of how to do computations with them, like for the more complex arithmetic functions. Most modern instruction-set architectures now include maximum and minimum instructions, together with the addition and subtraction instructions.
- layer8 3y ago
  OR still forms a semiring with AND, and that semiring operation is still called addition. OR is also like addition in saturation arithmetics. In those senses, it’s an additive operation, and it is indeed called logical addition: https://en.wikipedia.org/wiki/Logical_disjunction https://en.wikipedia.org/wiki/Logical_disjunction https://mathworld.wolfram.com/deMorgansDualityLaw.html https://mathworld.wolfram.com/deMorgansDualityLaw.html
pzmarzly 3y ago
Posting update since it's too late to edit: I confused multiplication with maximum. It's been too long since I took a course in formal logic. Though for binary values, multiplication works as well.

thaumasiotes 3y ago

> There is a reason why conjunction (AND) is also called logical multiplication, and disjunction (OR) logical addition. Really? The connection between AND and multiplication is obvious, but disjunction doesn't behave like addition. (For one thing, just like AND, it destroys information, which multiplication does do and addition doesn't.) Addition would usually be XOR. In fact, AND and XOR are what you get when you apply multiplication and addition to the integers (mod 2).

dvt 3y ago
It's called logical addition which is different than arithmetic addition, so it's best to not conflate the two. It's called "addition" because you "add" another propostion, creating a disjunction. And by the rules of logic, as long as the original proposition was true, the truth value is preserved no matter how many propositions you introduce (or "add"). A ⊢ ((A ∨ B) ∨ C) ... ∨ n
- thaumasiotes 3y ago
  > It's called "addition" because you "add" another propostion, creating a disjunction. By that argument, conjunction is also called "addition". Perhaps there's a different reason? The choice of terminology, contrasting "logical addition" with "logical multiplication", obviously indicates that logical addition is supposed to be analogous to addition. What is the analogy?
  - andai 3y ago
    I don't know if this relates to formal logic, but in C a true value is defined as not zero, so all nonzero values are treated as the same value. So the only way to get a false is to OR (or add) two zeroes, making the two operations equivalent as far as boolean logic goes. Actually, you can add 1 and -1 to get 0, which breaks the model... Hmm... Guess it only works on natural numbers / unsigned.
  - EGreg 3y ago
    The analogy is deep. But actually the relationship is as follows: P(A u B) = P(A) + P(B) - P(A^B) P(A ^ B) = P(A u B) - P(A) - P(B) And to the guy who said xor is addition — no it’s not: P(A xor B) = P(A) + P(B) - 2 * P(A^B) In Probability, when you have a space of outcomes, doing a Union on two disjoint events (sets of outcomes) the probabilities add. Whereas doing an Intersection on two non-disjoint events those probabilities multiply. If two events have no outcomes in common, for instance, the probability of them both occurring is zero. When you “condition” probability on an event X happening, you restrict the space of all outcomes to that set X, and intersect every event with it. When you condiition B[n] = A[n] given that (A[n-1] AND … A[1]) having already happened, you have a sales funnel and each step is independent of the previous, so the probabilities multiply. It is also called a Markov Chain if you have a discrete set of possibilities at each step so you can form a matrix.
    - cubefox 3y ago
      Interesting, I never saw the arithmetic probability formula for xor. Though the original topic was truth values, not probabilities. To make it short, conjunctions in probability are multiplicative when they are independent, and disjunctions in probability are additive when they are mutually exclusive.
      - EGreg 3y ago
        Well I actually came up with it on the spot. Just think of the venn diagram, and add the areas of A and B, which counts A^B twice, and then just remove it twice. :)
  - 3y ago
moritzwarhier 3y ago
Is there a way to express OR (not XOR) using integer arithmetic without case distinction or special functions in the natural numbers mod 2? Meaning, using only elementary arithmetic and modulo? Seems like there should be either an obvious answer or an interesting one :)
- 201p 3y ago
  The maximum function.
  - moritzwarhier 3y ago
    Yeah that makes sense of course. Should have specified "special function", was aiming at "algebraic" or "polynomial" I guess. Then the answer seems to be no, right? Edit: The abs() function seems to be enough, awesome: https://math.stackexchange.com/a/1641271 https://math.stackexchange.com/a/1641271
    - deleted 3y ago
      [deleted]
    - adrian_b 3y ago
      The abs function works because it is equal to the maximum of x and -x. The logical "and" and logical "or" functions are precisely particular cases of the minimum and maximum functions. The so-called "exclusive or" function is simultaneously a particular case of addition and of subtraction, i.e. addition modulo 2 and subtraction modulo 2 are the same function. Therefore applying the 4 functions minimum, maximum, addition and subtraction to 1-bit numbers produces only 3 functions, AND, OR and XOR. It makes no sense to search other functions for expressing logical "and" and logical "or" except for minimum and maximum, because this is what they are. The search could only find alternative more complicated ways to express minimum and maximum. The minimum and maximum functions also work in logic systems with more than 2 values of truth. Also in hardware, analog circuits for minimum and maximum are one of the 2 ways of implementing the logical "and" and "or" functions, the other way being with series and parallel connections. The main mistake of George Boole was his unsuccessful attempt to find an equivalence between logical "and" and "or" and integer multiplication and addition, because he was not habituated to use minimum and maximum, so he did not see the correct relationships. The functions maximum and minimum are arithmetic functions as important as addition and subtraction. The only reason for which they have not been counted among the basic arithmetic functions is because when computed by a human they required much less effort than even addition, so there was no need for a long training of how to do computations with them, like for the more complex arithmetic functions. Most modern instruction-set architectures now include maximum and minimum instructions, together with the addition and subtraction instructions.
layer8 3y ago
OR still forms a semiring with AND, and that semiring operation is still called addition. OR is also like addition in saturation arithmetics. In those senses, it’s an additive operation, and it is indeed called logical addition: https://en.wikipedia.org/wiki/Logical_disjunction https://en.wikipedia.org/wiki/Logical_disjunction https://mathworld.wolfram.com/deMorgansDualityLaw.html https://mathworld.wolfram.com/deMorgansDualityLaw.html

pzmarzly 3y ago

Posting update since it's too late to edit: I confused multiplication with maximum. It's been too long since I took a course in formal logic. Though for binary values, multiplication works as well.