# Boolean Functions

## Contents

# Introduction

Let be the vector space of dimension *n* over the finite field with two elements.
The vector space can also be endowed with the structure of the field, the finite field with .
A function is called a *Boolean function* in dimenstion *n* (or *n-variable Boolean function*).

Given , the support of *x* is the set .
The Hamming weight of *x* is the size of its support ().
Similarly the Hamming weight of a Boolean function *f* is the size of its support, i.e. the set .
The Hamming distance of two functions *f,g* is the size of the set .

# Representation of a Boolean function

There exist different ways to represent a Boolean function.
A simple, but often not efficient, one is by its truth-table.
For example consider the following truth-table for a 3-variable Boolean function *f*.

x |
f(x) |
||
---|---|---|---|

0 | 0 | 0 | 0 |

0 | 0 | 1 | 1 |

0 | 1 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 0 | 0 |

1 | 0 | 1 | 1 |

1 | 1 | 0 | 0 |

1 | 1 | 1 | 1 |

## Algebraic normal form

An *n*-variable Boolean function can be represented by a multivariate polynomial over of the form

Such representation is unique and it is the * algebraic normal form* of *f* (shortly ANF).

The degree of the ANF is called the * algebraic degree* of the function, <math>d^0 f=\max \{ |I| : a_I\ne0 \}.

## Trace representation

In this case we identify the vector space with the finite field.