Content deleted Content added
→Standard Boolean ___domain: General formula |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 302/1032 |
||
| (43 intermediate revisions by 25 users not shown) | |||
Line 1:
{{
{{distinguish|Binary function}}
[[File:BinaryDecisionTree.svg|thumb|A [[binary decision diagram]] and [[truth table]] of a ternary Boolean function]]
{{Logical connectives sidebar}}
{{distinguish|Binary function}}In [[mathematics]], a '''Boolean function''' is a [[function (mathematics)|function]] whose [[Argument of a function|arguments]], as well as the function itself, 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 [[cryptography]]).<ref name=":2" />▼
▲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
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. == Examples ==
[[File:Logical connectives Hasse diagram.svg|alt=Diagram displaying the sixteen binary Boolean functions|thumb|The sixteen binary Boolean functions]]
{{See also|Truth table|Truth function}}
The rudimentary symmetric Boolean functions ([[
* [[Inverter (logic gate)|NOT]], [[negation]] or [[Logical complement|complement]] - which receives one input and returns true when that input is false ("not")
* [[AND gate|AND]] or [[Logical conjunction|conjunction]] - true when all inputs are true ("both")
* [[OR gate|OR]] or [[Logical disjunction|disjunction]] - true when any input is true ("either")
* [[XOR gate|XOR]] or [[Exclusive or|exclusive disjunction]] - true when one of its inputs is true and the other is false ("not equal")
* [[NAND gate|NAND]] or [[Sheffer stroke]] - true when it is not the case that all inputs are true ("not both")
*[[NOR gate|NOR]] or [[Logical NOR|logical nor]] - true when none of the inputs are true ("neither")
Line 28 ⟶ 27:
== Representation ==
[[File:Three input
A Boolean function may be specified in a variety of ways:
Line 35 ⟶ 34:
**[[Binary decision diagram]], listing the truth table values at the bottom of a binary tree
**[[Venn diagram]], depicting the truth table values as a colouring of regions of the plane
Algebraically, as a [[propositional formula]] using rudimentary
* [[Negation normal form]], an arbitrary mix of AND and ORs of the arguments and their complements
Line 44 ⟶ 43:
**''Full'' (canonical) [[disjunctive normal form]], an OR of ANDs each containing every argument or complement ([[minterms]])
**''Full'' (canonical) [[conjunctive normal form]], an AND of ORs each containing every argument or complement ([[maxterms]])
**[[Blake canonical form]], the OR of all the [[
Boolean formulas can also be displayed as a graph:
* [[Propositional directed acyclic graph]]
**[[Circuit (computer science)|Digital circuit]] diagram of [[
**[[And-inverter graph]], using only AND and NOT
In order to optimize electronic circuits, Boolean formulas can be [[Minimization of Boolean functions|minimized]] using the [[Quine–McCluskey algorithm]] or [[Karnaugh map]].
Line 59 ⟶ 58:
* [[Constant function|Constant]]: Is always true or always false regardless of its arguments.
* [[Monotonic function#In Boolean functions|Monotone]]: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be [[Unate function|unate]] in a certain variable if it is monotone with respect to changes in that variable.
* [[Linearity#Boolean functions|Linear]]: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a [[parity function]]).
* [[Symmetric Boolean function|Symmetric]]: the value does not depend on the order of its arguments.
* [[Read-once function|Read-once]]: Can be expressed with [[logical conjunction|conjunction]], [[logical disjunction|disjunction]], and [[negation]] with a single instance of each variable.
*[[Balanced
* [[Bent function|Bent]]: its derivatives are all balanced (the autocorrelation spectrum is zero)
* [[Correlation immunity|Correlation immune]] to ''m''th order: if the output is uncorrelated with all (linear) combinations of at most ''m'' arguments
Line 72 ⟶ 71:
=== Derived functions ===
A Boolean function may be decomposed using [[Boole's expansion theorem]] in positive and negative ''Shannon'' ''cofactors'' ([[Shannon expansion]]), which are the (''k
The ''[[Boolean derivative]]'' of the function to one of the arguments is a (''k
The ''[[Zhegalkin polynomial#Möbius transformation|Möbius transform]]'' (or ''
=== Cryptographic analysis ===
The ''[[Walsh transform]]'' of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into [[Parity function|linear functions]] ([[Walsh function
The ''[[autocorrelation]]'' of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function
The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the [[Wiener–Khinchin theorem]], which states that the autocorrelation and the power spectrum are a Walsh transform pair.<ref name=":1" />
==== Linear approximation table ====
These concepts can be extended naturally to ''vectorial'' Boolean functions by considering their output bits (''coordinates'') individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its ''components''.<ref name=":2">{{Cite web|last=Carlet|first=Claude|title=Vectorial Boolean Functions for Cryptography|url=https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf|url-status=live|website=University of Paris|archive-url=https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf |archive-date=2016-01-17 }}</ref> The set of Walsh transforms of the components is known as a ''
== Real polynomial form ==
===
Any Boolean function <math>f(x): \{0,1\}^n \rightarrow \{0,1\}</math> can be uniquely extended (interpolated) to the [[Real number|real ___domain]] by a [[multilinear polynomial]] in <math>\mathbb{R}^n</math>, constructed by summing the truth table values multiplied by [[Lagrange polynomial|indicator polynomials]]:<math display="block">f^*(x) = \sum_{a \in {\{0,1\}}^n} f(a) \prod_{i:a_i=1} x_i \prod_{i:a_i=0} (1-x_i)</math>For example, the extension of the binary XOR function <math>x \oplus y</math> is<math display="block">0(1-x)(1-y) + 1x(1-y) + 1(1-x)y + 0xy</math>which equals<math display="block">x + y -2xy</math>Some other examples are negation (<math>1-x</math>), AND (<math>xy</math>) and OR (<math>x + y - xy</math>). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated [[Modular arithmetic|modulo 2]] one obtains the [[algebraic normal form]] ([[Zhegalkin polynomial]]).
Line 97:
\end{array}</math>this generalizes as the [[Möbius transform|Möbius inversion]] of the [[partially ordered set]] of bit vectors:<math display="block">f^*(m) = \sum_{a \subseteq m} (-1)^{|a|+|m|} f(a)</math>where <math>|a|</math> denotes the weight of the bit vector <math>a</math>. Taken modulo 2, this is the [[Zhegalkin polynomial|Boolean ''Möbius transform'']], giving the [[algebraic normal form]] coefficients:<math display="block">\hat f(m) = \bigoplus_{a \subseteq m} f(a)</math>In both cases, the sum is taken over all bit-vectors ''a'' covered by ''m'', i.e. the "one" bits of ''a'' form a subset of the one bits of ''m''.
When the ___domain is restricted to the n-dimensional [[hypercube]] <math>[0,1]^n</math>, the polynomial <math>f^*(x): [0,1]^n \rightarrow [0,1]</math> gives the probability of a positive outcome when the Boolean function ''f'' is applied to ''n'' independent random ([[Bernoulli distribution|Bernoulli]]) variables, with individual probabilities ''x''. A special case of this fact is the [[piling-up lemma]] for [[
=== On the symmetric hypercube ===
Often, the Boolean ___domain is taken as <math>\{-1, 1\}</math>, with false ("0") mapping to 1 and true ("1") to
==Applications==
Boolean functions play a basic role in questions of [[Computational complexity theory|complexity theory]] as well as the design of processors for [[digital computer]]s, where they are implemented in electronic circuits using [[
The properties of Boolean functions are critical in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[substitution box]]).
Line 130 ⟶ 131:
*{{citation |last1=Mano |first1=M. M. |last2=Ciletti |first2=M. D. |year=2013 |title=Digital Design |publisher=Pearson}}
{{Mathematical logic}} {{Functions navbox}}
{{DEFAULTSORT:Boolean
[[Category:Boolean algebra]]
[[Category:Binary arithmetic]]
[[Category:Logic gates]]
[[Category:Programming constructs]]
| |||