Content deleted Content added
No edit summary |
m avoid unnec redirect |
||
Line 3:
[[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>
Line 61 ⟶ 62:
* [[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
| |||