boolean function

a boolean function is a function $\text{[math]}$ for some $\text{[math]}$ . they are binary functions whose codomain is $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_1999 chapter 1.2 circuit size and depth; definition 1.1]

since we have $\text{[math]}$ vectors in $\text{[math]}$ , the total number of boolean functions $\text{[math]}$ is doubly exponential in $\text{[math]}$ , i.e. $\text{[math]}$ .
[cite:;taken from @complexity_jukna_2012 chapter 1.1 boolean functions]

since we have $\text{[math]}$ vectors in $\text{[math]}$ , we can represent a boolean function $\text{[math]}$ by its $\text{[math]}$ possible outputs corresponding to all possible input vectors.

a family of boolean functions is a sequence $\text{[math]}$ , where $\text{[math]}$ is an $\text{[math]}$ -ary boolean function.
[cite:;taken from @complexity_vollmer_1999 chapter 1.2 circuit size and depth; definition 1.3]

every boolean function defines a corresponding broken link: blk:def-lang. given a function $\text{[math]}$ , we can identify it with the language
$\text{[math]}$ this way we can use boolean function or boolean circuit in the analysis of decision problems and use the theorems interchangably.
[cite:;found in @computability_arora_2009 chapter 0.2 decision problems/languages]

let $\text{[math]}$ denote the set of all $\text{[math]}$ -ary boolean functions.
[cite:;taken from @complexity_vollmer_1999 chapter chapter 1.5 asymptotic complexity]

a boolean function $\text{[math]}$ is degenerated, if there is an $\text{[math]}$ , $\text{[math]}$ , such that for all $\text{[math]}$ we have $\text{[math]}$ . in this case $\text{[math]}$ is called an inessential variable of $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_1999 definition 3.2]

when we want to give lower bounds for the complexity of a function $\text{[math]}$ measured in $\text{[math]}$ , it suffices to consider only non-degenerated functions.
let $\text{[math]}$ be non-degenerated. then $\text{[math]}$ .
[cite:;taken from @complexity_vollmer_1999 theorem 3.3]

for a boolean function $\text{[math]}$ that depends on all of its inputs, we have $\text{[math]}$ .

let $\text{[math]}$ . a subfunction $\text{[math]}$ of $\text{[math]}$ is a function obtained by assigning values to some of the input variables of $\text{[math]}$ , assigning (not necessarily unique) variable names to the rest, deleting andor permuting some of its output variables. we say that $\text{[math]}$ is a reduction to $\text{[math]}$ via the subfunction relationship/.
[cite:;taken from @computation_savage_1998 chapter 2.4 reductions between functions; definition 2.4.2]

a boolean function is symmetric if it depends only on the number of ones in the input, and not on positions in which these ones actually reside. we thus have only $\text{[math]}$ such functions of $\text{[math]}$ variables, examples of symmetric boolean functions are:

threshold function $\text{[math]}$ .
majority function $\text{[math]}$ .
parity function $\text{[math]}$ .
modular functions $\text{[math]}$ .

[cite:;taken from @complexity_jukna_2012 chapter 1.1 boolean functions]