Motivation
In the field of hardware security, you often need to convert between boolean and arithmetic masking (e.g. Coron et al, CHES 2014). As a result, you often need to verify an algorithm mixing arithmetic and boolean operations. One specific usecase I had, was verifying whether \(a \oplus (b \land c) == (a \oplus b) \land (a \oplus c)\) holds true in \(\mathbb{Z}/{16}\mathbb Z\).
Mixing such operations essentially means you don’t know these laws by heart and resort to generating truthtables to verify your claims. In this blogpost, we do it systematically. It answers questions like:

Is XOR distributive over AND?

Is AND distributive over XOR?

Is OR distributive over XOR?
The law of distributivity
The law of distributivity is easy to state: Let x and y be any two elements of a given set S. Let \(\odot\) and \(\oplus\) be two binary operations. We call \(\odot\) leftdistributive over \(\oplus\) if and only if …
We call \(\odot\) rightdistributive over \(\oplus\) if and only if …
We call \(\odot\) distributive over \(\oplus\) if it is leftdistributive and rightdistributive.
Usually, you know this property from rings which establish distributivity between addition and multiplication.
A set of operations
Let us denote all numbers in binary, e.g. \(10_2\) for decimal 2. Let \(n\) define \(2^n\) as the number of elements in the set. Now, we consider various operations:
 ADD

\(a + b\) is the common addition in \(\mathbb Z/2^n \mathbb Z\), e.g. \(2 + 3\) is \(5\) in \(\mathbb Z/2^3 \mathbb Z\)
 SUB

\(a  b\) is subtraction in \(\mathbb Z/2^n \mathbb Z\), e.g. \(2  3\) is \(7\) in \(\mathbb Z/2^3 \mathbb Z\)
 MUL

\(a \cdot b\) is the common multiplication in \(\mathbb Z/2^n \mathbb Z\), e.g. \(2 \cdot 3\) is \(6\) in \(\mathbb Z/2^3 \mathbb Z\)
 DIV

\(a / b\) is division in \(\mathbb Z/2^n \mathbb Z\) with the result \(0\) in special case \(b = 0\), e.g. \(6 / 3\) is \(2\) in \(\mathbb Z/2^3 \mathbb Z\)
 XOR

\(a \oplus b\) is a bitwise XOR, e.g. \(5 \cdot 1\) is \(4\)
 AND

\(a \land b\) is a bitwise AND, e.g. \(5 \land 1\) is \(1\)
 OR

\(a \lor b\) is a bitwise OR, e.g. \(6 \lor 1\) is \(7\)
 IF

\(a \rightarrow b\) is an implication between two bits, e.g. if a then (b) else (false)
 XNOR

\(\neg (a \oplus b)\) is the negation of bitwise XOR, e.g. 1 and 1 gives 1
 NAND

\(\neg (a \land b)\) is the negation of bitwise AND, e.g. 1 and 1 gives 0
You can think of {ADD, SUB, MUL, DIV} as arithmetic operations and {XOR, AND, OR, IF, XNOR, NAND} as boolean operations.
Evaluation
Now, we generate a table for \(n = 1\) where l stands for leftdistributivity and r stand for rightdistributivity. We always consider the row operation to be distributive over the column operation.
↓ is distributive over →  ADD  SUB  MUL  DIV  XOR  AND  OR  IF  XNOR  NAND 

ADD 

SUB 

MUL 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 

DIV 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 

XOR 

AND 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 

OR 
l,r 
l,r 
l,r 
l,r 
l,r 
l,r 

IF 
l 
l 
l 
l 
l 
l 

XNOR 

NAND 
Apparently, …

{ADD, SUB, XOR, XNOR, NAND} is not distributive over any other operation.
For example, ADD is not distributive over ADD because \(x + (y + z) \neq (x + y) + (x + z)\).
For example, ADD is not distributive over XOR because \(x 1 + (1 \oplus 1) = 1 \neq 0 = (1 + 1) \oplus (1 + 1)\) 
MUL is distributive over MUL because \(x \cdot (y \cdot z) = (x \cdot y) \cdot (x \cdot z)\) and \((y \cdot z) \cdot x = (y \cdot x) \cdot (z \cdot x)\) in \(\mathbb Z/2\mathbb Z\). Why? Because either all values are one (then both sides are one) or one value is zero (then both sides are zero).

I call IF “leftbiased” because IF returns 0 whenever the left argument is 0. This the reason why IF is leftdistributive, but never rightdistributive.
… in \(\mathbb Z/2\mathbb Z\).
So, what about other n?
n == 2
↓ is distributive over →  ADD  SUB  MUL  DIV  XOR  AND  OR  IF  XNOR  NAND 

ADD 

SUB 

MUL 
l,r 
l,r 
l,r 

DIV 
r 

XOR 

AND 
l,r 
l,r 
l,r 

OR 
l,r 
l,r 

IF 
l 
r 
r 
r 

XNOR 

NAND 
l,r 
l,r 
l,r 
n == 3
↓ is distributive over →  ADD  SUB  MUL  DIV  XOR  AND  OR  IF  XNOR  NAND 

ADD 

SUB 

MUL 
l,r 
l,r 

DIV 

XOR 

AND 
l,r 
l,r 
l,r 

OR 
l,r 
l,r 

IF 
l 
r 
r 
r 

XNOR 

NAND 
l,r 
l,r 
l,r 
n == 4
↓ is distributive over →  ADD  SUB  MUL  DIV  XOR  AND  OR  IF  XNOR  NAND 

ADD 

SUB 

MUL 
l,r 
l,r 

DIV 

XOR 

AND 
l,r 
l,r 
l,r 

OR 
l,r 
l,r 

IF 
l 
r 
r 
r 

XNOR 

NAND 
l,r 
l,r 
l,r 
n == 5
↓ is distributive over →  ADD  SUB  MUL  DIV  XOR  AND  OR  IF  XNOR  NAND 

ADD 

SUB 

MUL 
l,r 
l,r 

DIV 

XOR 

AND 
l,r 
l,r 
l,r 

OR 
l,r 
l,r 

IF 
l 
r 
r 
r 

XNOR 

NAND 
l,r 
l,r 
l,r 
python3 source code
The following source code was used to generate these results:
#!/usr/bin/env python3
import itertools
import collections
# convenience utilities
bit = lambda bits, i: (bits >> i) & 1
def op_per_bit(op, n):
"""Apply a binary operation to the ith bits ∀i in ibits vectors"""
def per_bit(a, b):
acc = 0
for i in range(n):
acc = op(bit(a, i), bit(b, i))
return acc
return per_bit
# definition of operations
OP = collections.namedtuple('OP', 'name func')
OPS = lambda n: [
OP('ADD ', lambda a, b: (a + b) % 2**n),
OP('SUB ', lambda a, b: (a  b) % 2**n),
OP('MUL ', lambda a, b: (a * b) % 2**n),
OP('DIV ', lambda a, b: (a // b) % 2**n if b != 0 else 0),
OP('XOR ', lambda a, b: a ^ b),
OP('AND ', lambda a, b: a & b),
OP('OR ', lambda a, b: a  b),
OP('IF ', op_per_bit(lambda bit1, bit2: int(not bit1 or bit2), n)),
OP('XNOR', op_per_bit(lambda bit1, bit2: int(not (bit1 ^ bit2)), n)),
OP('NAND', op_per_bit(lambda bit1, bit2: int(not (bit1 & bit2)), n))
]
def result_repr(left, right):
if left and right:
return "l,r "
elif left:
return "l "
elif right:
return "r "
return " "
def print_human_readable_table(tbl_left, tbl_right, n):
ops = OPS(n)
print(" " * 5 + "│", end='')
for op in ops:
print(op[0] + "│", end='')
print()
print("–" * 56)
for op_1 in ops:
print(op_1[0] + " │", end='')
for op_2 in ops:
print(result_repr(tbl_left[op_1[0] + op_2[0]], tbl_right[op_1[0] + op_2[0]]), end='')
print()
if __name__ == "__main__":
for n in range(1, 6):
print("\n## n == {}\n".format(n))
# evaluation data
left_distributivity = {}
right_distributivity = {}
# evaluation
for op1, op2 in itertools.product(OPS(n), repeat=2):
left_dist, right_dist = True, True
for arg1, arg2, arg3 in itertools.product(range(2**n), repeat=3):
lhs = op1.func(arg1, op2.func(arg2, arg3))
rhs = op2.func(op1.func(arg1, arg2), op1.func(arg1, arg3))
left_dist = left_dist and (lhs == rhs)
lhs = op1.func(op2.func(arg2, arg3), arg1)
rhs = op2.func(op1.func(arg2, arg1), op1.func(arg3, arg1))
right_dist = right_dist and (lhs == rhs)
left_distributivity[op1.name + op2.name] = left_dist
right_distributivity[op1.name + op2.name] = right_dist
print_human_readable_table(left_distributivity, right_distributivity, n)
Conclusion
It is interesting to see how the operation change with increasing n.

The tables don’t seem to change beyond n>2.

If n=2 …

{DIV, MUL, AND} lose most distributivity properties

MUL is not distributive over MUL anymore, because it does not only matter whether one argument is zero, but x occurs two times on the righthand side. Thus for values like 2, we get a firstorder expression on the lefthand side and a secondorder expression on the righthand side.

IF was sometimes leftdistributive in the case of n=1. In n=2, it is only rightdistributive over IF and XNOR. Rightdistributivity over NAND is a new property.

The table n=2 is not a subset of n=1 because the properties of IF change a lot.


If n>2 …

DIV loses rightdistributivity over AND

MUL is not distributive over XOR anymore

Update 20210826: I fixed formatting issues and a bug in the python script.