Algebraic normal form

Recursively deriving multiargument Boolean functions

There are only four functions with one argument:

• ${\displaystyle f(x)=0}$
• ${\displaystyle f(x)=1}$
• ${\displaystyle f(x)=x}$
• ${\displaystyle f(x)=1\oplus x}$

To represent a function with multiple arguments one can use the following equality:

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})}$, where

• ${\displaystyle g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})}$
• ${\displaystyle h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})\oplus f(1,x_{2},\ldots ,x_{n})}$

Indeed,

• if ${\displaystyle x_{1}=0}$ then ${\displaystyle x_{1}h=0}$ and so ${\displaystyle f(0,\ldots )=f(0,\ldots )}$
• if ${\displaystyle x_{1}=1}$ then ${\displaystyle x_{1}h=h}$ and so ${\displaystyle f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )}$

Since both ${\displaystyle g}$ and ${\displaystyle h}$ have fewer arguments than ${\displaystyle f}$ it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of ${\displaystyle f(x,y)=x\lor y}$ (logical or):

• ${\displaystyle f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))}$
• since ${\displaystyle f(0,y)=0\lor y=y}$ and ${\displaystyle f(1,y)=1\lor y=1}$
• it follows that ${\displaystyle f(x,y)=y\oplus x(y\oplus 1)}$
• by distribution, we get the final ANF: ${\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}$