Function to check truth value of a specific statement
Make the function return True or False.
You can use all and a generator comprehension instead of returning early.
You should make the range have the same input.


Putting these together you can get:

def check_truth(bits):
    return all(
        x + y == (x | y) + (x &amp; y)
        for x in range(bits ** 2)
        for y in range(bits ** 2)
    )

print("{} for {} bits".format(check_truth(bits), bits))


The simplest way to prove:

$$x + y = (x \land y) + (x \lor y)$$

Is to think of integers as a bunch of wires that are passed to an infinite full adder. Due to how full adders work, they will not care how the bits are placed, as it makes no logical difference to its functionality.
So \$010 + 101 = 111 + 000\$, which means as long as we know there are the same amount of bits on each section of the equation, then we know they are the same.
Since we know \$a = x \lor y\$ and \$b = x \land y\$, we can test if there are any missing or new bits.
And so using the following 'table' shows that each level will have the same amount of bits:

$$
x, y, a, b\\
0, 0, 0, 0\\
1, 0, 1, 0\\
0, 1, 1, 0\\
1, 1, 1, 1\\
$$

And so to get the best performance we can re-write check_truth:

def check_truth(bits):
    return True




To make a more compelling argument, we could sub \$a\$ and \$b\$ into a full adder equation, and show there's no difference, but if you think about this logically you should notice it's always true.

$$
S = C \oplus (A \oplus B)\\
C_1 = ((A \oplus B) \land C) \lor (A \land B)
$$

Sub \$A = x \lor y\$ and \$B = x \land y\$:

$$
S = C \oplus ((x \lor y) \oplus (x \land y))\\
C_1 = (((x \lor y) \oplus (x \land y)) \land C) \lor ((x \lor y) \land (x \land y))
$$

Simplify some things:

$$
(x \lor y) \oplus (x \land y) = x \oplus y\\
(x \lor y) \land (x \land y) = x \land y
$$

Sub simplified versions into main function:

$$
S = C \oplus (x \oplus y)\\
C_1 = ((x \oplus y) \land C) \lor (x \land y)
$$

See that it works the same way.