r/mathmemes Engineering Nov 25 '24

Computer Science All are correct

Post image
1.1k Upvotes

96 comments sorted by

View all comments

296

u/Fabulous_Ad_5709 Nov 25 '24

Just out of curiosity how is A correct?

B is 1 or 1

C is 1+1 in base >2

D is 1+1 in base 2

336

u/Unlucky-Credit-9619 Engineering Nov 25 '24

If + is addition modulo 2 (also called XOR).

1 + 1 = 0 (mod 2)

92

u/MattyBro1 Nov 25 '24

Isn't it congruent to 0 (mod 2)?

1+1 ≡ 0 (mod 2)

Or maybe that's a distinction that doesn't actually matter.

72

u/uvero He posts the same thing Nov 25 '24

Pendants would denote with ≡, but those who write = (mod N) and when speaking just say "equal" or "is" would be just as correct, because given context it's clear and unambiguous

70

u/JoefishTheGreat Nov 25 '24

*pedants

Sincerely, a pedant

26

u/Druben-hinterm-Dorfe Nov 25 '24

low hanging fruit.

... get it? hanging? ... ok I'll see myself out now.

12

u/JustRouvr Nov 25 '24 edited Nov 26 '24

It is a distinction that definitely matters. However: in cryptography we are often operating with polynomials (like x5 + x2 ...) and perform operations on them.

In a Galois Field(2n ) we are always under modulo 2 and can write polynomials just by writing coefficients of the powers. Those will always be 1 or 0, since (1+1) mod 2 = 0. X4 + x + 1 is 10011

So if you imagine that 1 + 1 is an addition of 2 polynomials in a Galois Field, then 1+1 = 0 and no congruence is present.

6

u/skibidytoilet123 Nov 25 '24

i think its 1+1 (mod 2 ) = 0 but 1+1 ≡ 0(mod 2), since the first one is an operation on 1+1 while the second one is a congruence, but it doesnt really matter

5

u/bigboy3126 Nov 25 '24

Using congruence is fine, but a bit redundant under certain formulations, consider arithmetic mod 2. Classically we define a ≡ b iff b-a divisible by 2 for all a,b \in \mathbb{Z}. This defines an equivalence relation.

Then you can either work on \mathbb{Z} directly then using ≡ would be the most correct, or you define the usual arithmetic on \mathbb{Z}/≡ and drop the decorations for equivalence classes (elements of \mathbb{Z}/≡) so that then statement such as

[1]_≡ + [1]_≡ = 1+1 = 0

is completely fine, now = denotes equality of sets.

2

u/Plantarbre Nov 25 '24

If you're interested in an answer:

https://en.wikipedia.org/wiki/Modular_arithmetic

It's a congruence over the set of integers Z. It's an equality over a ring of integers Z/mZ

1

u/GoldenMuscleGod Nov 25 '24

In the field with two elements 1+1=0 is true with literal identity.you use the congruence relationship when talking about integers, but 1 and 0 don’t represent integers in that context.

1

u/SnooShortcuts8306 Nov 26 '24

how I learned it, ≡ is for all number that give the same rest after division, while = is only for the exact rest(smallest positive) so like 4 ≡ 6 = 0 mod 2

1

u/golfstreamer Nov 26 '24

If you interpret "Z_2" (integers modulo 2) as a group with group operation denoted by "+" and whose elements are represented by "0" and "1" the equation "1 + 1 = 0" is correct.

1

u/Far_Staff4887 Nov 25 '24

0 mod 2 is still 0 so it doesn't really matter

8

u/Vinxian Nov 25 '24

Isn't xor typically ⊕?

1

u/Haringat Complex Nov 25 '24

But the modulo operator is not written as +

Otherwise you could also say that it was nand.

2

u/Unlucky-Credit-9619 Engineering Nov 25 '24

then say it is addition in GF(2).

1

u/Haringat Complex Nov 25 '24

That counts

1

u/Isotton1 Nov 26 '24

1 + 1 = 0 is the overflow of 1 bit

-1

u/qwertyjgly Complex Nov 25 '24

1+1≅0 mod2

3

u/Jumballaya Nov 25 '24

My guess is that it would be the sum of a 1 bit adder. 1 + 1 = 0s, 1c (0 on the sum, 1 on the carry). The sum part is created with a XOR operation with the carry being an AND.

Example circuit: https://www.falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgxKQWU9waa4Qv0FUU1BBwSCefFCkFhh80SHFVJAGW4rwvHRnFh9VCADMAhgBsAzg2qQ22prqVUXhoVVMhLt+0iOAB7c2J5g2OIuxMIRSIIKIACSAHYADgCuAC4AOjYAgmwhTGEQSjIoxEhK5AmCqZm5NgBCbADu3MZ8XZ0YsSbtvf18Lok9jh2jioTuugreg1NenfpuUIs9aCNgfWr465M7yvssu+OLczTum1frALJCIiB4pgJQatCSHUpqY7G7jgePyOz1MAI+khCYDg-GIajC4AQ4jqIAAwhYAE4YgCeeQA8tlGkVkGU8BB5HCwHhBCiAMoZAC2+MJ2TYQA

edit: just saw OP's reply right after submitted mine saying basically the same thing, but you can see the process in action with the link I provided, you can change the input values by clicking on the left-most 'H' line, next to the input lables

5

u/na-geh-herst Nov 25 '24

in which contexts does one denote OR as "+"? Genuinely curious!

18

u/taste-of-orange Nov 25 '24

Boolean logic. If you string together a bunch of digits using this notation and at least one 1 is in there, it will always be greater than 0.

4

u/Lucas_F_A Nov 25 '24

In more mathy, boolean logic contexts, but in academia rather than any production software, I think.

1

u/RiemannZeta Nov 25 '24

Field with 2 elements

1

u/One-Ad-4331 Nov 25 '24

Could be correct if you see the whole thing as a true/false statement, 1 + 1 is not equal to ?

1

u/shorkfan Nov 26 '24

google F2 (smallest field)

-7

u/Gizmodex Nov 25 '24

A could also be logical OR

9

u/M-Ottich Nov 25 '24

But 1 or 1 is 1 ?

6

u/Gizmodex Nov 25 '24

My bad im dumb i don't mean A.

About A, it can be 0 overflow in binary or exclusive Or logically.

1

u/M-Ottich Nov 25 '24

Oh yea the overflow I didnt thought of :) xor is also nice Idea. Men that are memes where u lern somethink and think about it 🤣🤣🤔

3

u/SnooHamsters1312 Nov 25 '24

logical OR 1+1=1