Editing Boolean function (section)

{{Short description|Function returning one of only two values}}
{{distinguish|Binary function}}
[[File:BinaryDecisionTree.svg|thumb|A [[binary decision diagram]] and [[truth table]] of a ternary Boolean function]]
{{Logical connectives sidebar}}

In [[mathematics]], a '''Boolean function''' is a [[function (mathematics)|function]] whose [[Argument of a function|arguments]] and result assume values from a two-element set (usually {true, false}, {0,1} or {−1,1}).<ref>{{Cite web|title=Boolean function - Encyclopedia of Mathematics|url=https://encyclopediaofmath.org/wiki/Boolean_function|access-date=2021-05-03|website=encyclopediaofmath.org}}</ref><ref>{{Cite web|last=Weisstein|first=Eric W.|title=Boolean Function|url=https://mathworld.wolfram.com/BooleanFunction.html|access-date=2021-05-03|website=mathworld.wolfram.com|language=en}}</ref> Alternative names are '''switching function''', used especially in older [[computer science]] literature,<ref>{{Cite web|title=switching function|url=https://encyclopedia2.thefreedictionary.com/switching+function|access-date=2021-05-03|website=TheFreeDictionary.com}}</ref><ref>{{Cite journal|last=Davies|first=D. W.|date=December 1957|title=Switching Functions of Three Variables|url=https://ieeexplore.ieee.org/document/5222038|journal=IRE Transactions on Electronic Computers|volume=EC-6|issue=4|pages=265–275|doi=10.1109/TEC.1957.5222038|issn=0367-9950}}</ref> and '''[[truth function]]''' (or '''logical function)''', used in [[logic]]. Boolean functions are the subject of [[Boolean algebra]] and [[switching theory]].<ref>{{Citation|last=McCluskey|first=Edward J.|title=Switching theory|date=2003-01-01|url=https://dl.acm.org/doi/10.5555/1074100.1074844|encyclopedia=Encyclopedia of Computer Science|pages=1727–1731|place=GBR|publisher=John Wiley and Sons Ltd.|doi=|isbn=978-0-470-86412-8|access-date=2021-05-03}}</ref>

A Boolean function takes the form <math>f:\{0,1\}^k \to \{0,1\}</math>, where <math>\{0,1\}</math> is known as the [[Boolean domain]] and <math>k</math> is a non-negative integer called the [[arity]] of the function. In the case where <math>k=0</math>, the function is a constant element of <math>\{0,1\}</math>. A Boolean function with multiple outputs, <math>f:\{0,1\}^k \to \{0,1\}^m</math> with <math>m>1</math> is a '''vectorial''' or ''vector-valued'' Boolean function (an [[S-box]] in symmetric [[cryptography]]).<ref name=":2" />

There are <math>2^{2^k}</math> different Boolean functions with <math>k</math> arguments; equal to the number of different [[truth table]]s with <math>2^k</math> entries.

Every <math>k</math>-ary Boolean function can be expressed as a [[propositional formula]] in <math>k</math> variables <math>x_1,...,x_k</math>, and two propositional formulas are [[logical equivalence|logically equivalent]] if and only if they express the same Boolean function.