Linearity - Boolean Functions

Boolean Functions

In Boolean algebra, a linear function is a function for which there exist such that

for all

A Boolean function is linear if one of the following holds for the function's truth table:

1. In every row in which the truth value of the function is 'T', there are an odd number of 'T's assigned to the arguments and in every row in which the function is 'F' there is an even number of 'T's assigned to arguments. Specifically, f('F', 'F', ..., 'F') = 'F', and these functions correspond to linear maps over the Boolean vector space.
2. In every row in which the value of the function is 'T', there is an even number of 'T's assigned to the arguments of the function; and in every row in which the truth value of the function is 'F', there are an odd number of 'T's assigned to arguments. In this case, f('F', 'F', ..., 'F') = 'T'.

Another way to express this is that each variable always makes a difference in the truth-value of the operation or it never makes a difference.

Negation, Logical biconditional, exclusive or, tautology, and contradiction are linear functions.