Boolean function

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a Boolean function is a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> whose <a href="/facts/Argument_of_a_function/QkuPc28I">arguments</a> and result assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}). Alternative names are switching function, used especially in older <a href="/facts/Computer_science/lN3pEyPz">computer science</a> literature, and <a href="/facts/Truth_function/aH5kBhQ7">truth function</a> (or logical function), used in <a href="/facts/Logic/8JnpJLtt">logic</a>. Boolean functions are the subject of <a href="/facts/Boolean_algebra/VkCToAmg">Boolean algebra</a> and <a href="/facts/Switching_theory/6ogJWSyx">switching theory</a>.
A Boolean function takes the form 
 
 
 
 f
 :
 {
 0
 ,
 1
 
 }
 
 k
 
 
 →
 {
 0
 ,
 1
 }
 
 
 {\displaystyle f:\{0,1\}^{k}\to \{0,1\}}
 
, where 
 
 
 
 {
 0
 ,
 1
 }
 
 
 {\displaystyle \{0,1\}}
 
 is known as the <a href="/facts/Boolean_domain/9cYq9TC1">Boolean domain</a> and 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is a non-negative integer called the <a href="/facts/Arity/zSVuwHvP">arity</a> of the function. In the case where 
 
 
 
 k
 =
 0
 
 
 {\displaystyle k=0}
 
, the function is a constant element of 
 
 
 
 {
 0
 ,
 1
 }
 
 
 {\displaystyle \{0,1\}}
 
. A Boolean function with multiple outputs, 
 
 
 
 f
 :
 {
 0
 ,
 1
 
 }
 
 k
 
 
 →
 {
 0
 ,
 1
 
 }
 
 m
 
 
 
 
 {\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}
 
 with 
 
 
 
 m
 >
 1
 
 
 {\displaystyle m>1}
 
 is a vectorial or vector-valued Boolean function (an <a href="/facts/S-box/9xKgnLCF">S-box</a> in symmetric <a href="/facts/Cryptography/e94PEVau">cryptography</a>).
There are 
 
 
 
 
 2
 
 
 2
 
 k
 
 
 
 
 
 
 {\displaystyle 2^{2^{k}}}
 
 different Boolean functions with 
 
 
 
 k
 
 
 {\displaystyle k}
 
 arguments; equal to the number of different <a href="/facts/Truth_table/4KsmArDW">truth tables</a> with 
 
 
 
 
 2
 
 k
 
 
 
 
 {\displaystyle 2^{k}}
 
 entries.
Every 
 
 
 
 k
 
 
 {\displaystyle k}
 
-ary Boolean function can be expressed as a <a href="/facts/Propositional_formula/eEV8YrAI">propositional formula</a> in 
 
 
 
 k
 
 
 {\displaystyle k}
 
 variables 
 
 
 
 
 x
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 x
 
 k
 
 
 
 
 {\displaystyle x_{1},...,x_{k}}
 
, and two propositional formulas are <a href="/facts/Logical_equivalence/ysCWmsxA">logically equivalent</a> if and only if they express the same Boolean function.

Boolean function open-in-new

Boolean function