Line 1: |
Line 1: |
− | In [[mathematics]], a '''finitary boolean function''' is a [[function (mathematics)|function]] of the form <math>f : \mathbb{B}^k \to \mathbb{B},</math> where <math>\mathbb{B} = \{ 0, 1 \}</math> is a [[boolean domain]] and where <math>k\!</math> is a nonnegative integer. In the case where <math>k = 0,\!</math> the function is simply a constant element of <math>\mathbb{B}.</math>
| + | <font size="3">☞</font> This page belongs to resource collections on [[Logic Live|Logic]] and [[Inquiry Live|Inquiry]]. |
| | | |
− | More generally, a function of the form ''f'' : ''X'' → '''B''', where ''X'' is an arbitrary set, is a ''[[boolean-valued function]]''. If ''X'' = '''M''' = {1, 2, 3, …}, then ''f'' is a ''binary sequence'', that is, an infinite [[sequence]] of 0's and 1's. If ''X'' = [''k''] = {1, 2, 3, …, ''k''}, then ''f'' is ''binary sequence'' of length ''k''.
| + | A '''finitary boolean function''' is a [[function (mathematics)|function]] of the form <math>f : \mathbb{B}^k \to \mathbb{B},</math> where <math>\mathbb{B} = \{ 0, 1 \}</math> is a [[boolean domain]] and where <math>k\!</math> is a nonnegative integer. In the case where <math>k = 0,\!</math> the function is simply a constant element of <math>\mathbb{B}.</math> |
| | | |
− | There are <math>2^{2^k}</math> such functions. These play a basic role in questions of [[complexity theory]] as well as the design of circuits and chips for [[digital computer]]s. The properties of boolean functions play a critical role in [[cryptography]], particularly in the design of [[symmetric key algorithm]]s (see [[S-box]]). | + | There are <math>2^{2^k}</math> such functions. These play a basic role in questions of [[complexity theory]] as well as the design of circuits and chips for digital computers. |
| | | |
− | A '''boolean mask operation''' on boolean-valued functions combines values point-wise, for example, by [[exclusive disjunction|XOR]], or other [[boolean operator]]s.
| + | ==Syllabus== |
| | | |
− | ==Algebraic normal form== | + | ===Focal nodes=== |
| | | |
− | A boolean function can be written uniquely as a sum ([[exclusive disjunction|XOR]]) of products ([[logical conjunction|AND]]). This is known as the [[algebraic normal form]] (ANF).
| + | * [[Inquiry Live]] |
| + | * [[Logic Live]] |
| | | |
− | {| cellpadding="4"
| + | ===Peer nodes=== |
− | |-
| |
− | |<math>f(x_1, x_2, \ldots , x_n) = \!</math>
| |
− | |<math>a_0 + \!</math>
| |
− | |-
| |
− | |
| |
− | |<math>a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!</math>
| |
− | |-
| |
− | |
| |
− | |<math>a_{1,2}x_1x_2 + a_{n-1,n}x_{n-1}x_n + \!</math>
| |
− | |-
| |
− | |
| |
− | |<math>\ldots + \!</math>
| |
− | |-
| |
− | |
| |
− | |<math>a_{1,2,\ldots,n}x_1x_2\ldots x_n \!</math>
| |
− | |}
| |
| | | |
− | The values of the sequence <math>a_0, a_1, \ldots, a_{1, 2, \ldots, n}</math> can therefore also uniquely represent a boolean function. The algebraic degree of a boolean function is defined as the highest number of <math>x_i</math> that appear in a product term. Thus <math>f(x_1, x_2, x_3) = x_1 + x_3</math> has degree 1 (linear), whereas <math>f(x_1, x_2, x_3) = x_1 + x_1 x_2 x_3</math> has degree 3 (cubic).
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Boolean_function Boolean Function @ InterSciWiki] |
| + | * [http://mywikibiz.com/Boolean_function Boolean Function @ MyWikiBiz] |
| + | * [http://ref.subwiki.org/wiki/Boolean_function Boolean Function @ Subject Wikis] |
| + | * [http://en.wikiversity.org/wiki/Boolean_function Boolean Function @ Wikiversity] |
| + | * [http://beta.wikiversity.org/wiki/Boolean_function Boolean Function @ Wikiversity Beta] |
| + | |
| + | ===Logical operators=== |
| | | |
− | ==See also==
| |
| {{col-begin}} | | {{col-begin}} |
| {{col-break}} | | {{col-break}} |
− | * [[Algebra of sets]] | + | * [[Exclusive disjunction]] |
− | * [[Boolean algebra]] | + | * [[Logical conjunction]] |
− | * [[List of Boolean algebra topics|Boolean algebra topics]] | + | * [[Logical disjunction]] |
| + | * [[Logical equality]] |
| + | {{col-break}} |
| + | * [[Logical implication]] |
| + | * [[Logical NAND]] |
| + | * [[Logical NNOR]] |
| + | * [[Logical negation|Negation]] |
| + | {{col-end}} |
| + | |
| + | ===Related topics=== |
| + | |
| + | {{col-begin}} |
| {{col-break}} | | {{col-break}} |
| + | * [[Ampheck]] |
| * [[Boolean domain]] | | * [[Boolean domain]] |
− | * [[Boolean logic]] | + | * [[Boolean function]] |
− | * [[Boolean value]] | + | * [[Boolean-valued function]] |
| + | * [[Differential logic]] |
| + | {{col-break}} |
| + | * [[Logical graph]] |
| + | * [[Minimal negation operator]] |
| + | * [[Multigrade operator]] |
| + | * [[Parametric operator]] |
| + | * [[Peirce's law]] |
| {{col-break}} | | {{col-break}} |
− | * [[Boolean-valued function]] | + | * [[Propositional calculus]] |
− | * [[Logical connective]] | + | * [[Sole sufficient operator]] |
− | * [[Truth function]] | + | * [[Truth table]] |
| + | * [[Universe of discourse]] |
| * [[Zeroth order logic]] | | * [[Zeroth order logic]] |
| {{col-end}} | | {{col-end}} |
| | | |
− | ==External links== | + | ===Relational concepts=== |
| + | |
| + | {{col-begin}} |
| + | {{col-break}} |
| + | * [[Continuous predicate]] |
| + | * [[Hypostatic abstraction]] |
| + | * [[Logic of relatives]] |
| + | * [[Logical matrix]] |
| + | {{col-break}} |
| + | * [[Relation (mathematics)|Relation]] |
| + | * [[Relation composition]] |
| + | * [[Relation construction]] |
| + | * [[Relation reduction]] |
| + | {{col-break}} |
| + | * [[Relation theory]] |
| + | * [[Relative term]] |
| + | * [[Sign relation]] |
| + | * [[Triadic relation]] |
| + | {{col-end}} |
| | | |
− | * [http://www.isi.qut.edu.au/people/fuller/ Boolean Planet] — boolean functions in cryptography. | + | ===Information, Inquiry=== |
| + | |
| + | {{col-begin}} |
| + | {{col-break}} |
| + | * [[Inquiry]] |
| + | * [[Dynamics of inquiry]] |
| + | {{col-break}} |
| + | * [[Semeiotic]] |
| + | * [[Logic of information]] |
| + | {{col-break}} |
| + | * [[Descriptive science]] |
| + | * [[Normative science]] |
| + | {{col-break}} |
| + | * [[Pragmatic maxim]] |
| + | * [[Truth theory]] |
| + | {{col-end}} |
| + | |
| + | ===Related articles=== |
| + | |
| + | {{col-begin}} |
| + | {{col-break}} |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Cactus_Language Cactus Language] |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Futures_Of_Logical_Graphs Futures Of Logical Graphs] |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Propositional_Equation_Reasoning_Systems Propositional Equation Reasoning Systems] |
| + | {{col-break}} |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_:_Introduction Differential Logic : Introduction] |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Differential_Propositional_Calculus Differential Propositional Calculus] |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_and_Dynamic_Systems_2.0 Differential Logic and Dynamic Systems] |
| + | {{col-break}} |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Prospects_for_Inquiry_Driven_Systems Prospects for Inquiry Driven Systems] |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Introduction_to_Inquiry_Driven_Systems Introduction to Inquiry Driven Systems] |
| + | * [http://intersci.ss.uci.edu/wiki/index.php/Inquiry_Driven_Systems Inquiry Driven Systems : Inquiry Into Inquiry] |
| + | {{col-end}} |
| | | |
| ==Document history== | | ==Document history== |
Line 56: |
Line 116: |
| Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders. | | Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders. |
| | | |
− | * [http://www.getwiki.net/-Boolean_function Boolean function], [http://www.getwiki.net/ GetWiki]. | + | * [http://intersci.ss.uci.edu/wiki/index.php/Boolean_function Boolean Function], [http://intersci.ss.uci.edu/ InterSciWiki] |
− | | + | * [http://mywikibiz.com/Boolean_function Boolean Function], [http://mywikibiz.com/ MyWikiBiz] |
− | * [http://wikinfo.org/index.php/Boolean_function Boolean function], [http://wikinfo.org/index.php/Main_Page Wikinfo]. | + | * [http://planetmath.org/BooleanValuedFunction Boolean Function], [http://planetmath.org/ PlanetMath] |
− | | + | * [http://wikinfo.org/w/index.php/Boolean_function Boolean Function], [http://wikinfo.org/w/ Wikinfo] |
− | * [http://en.wikipedia.org/wiki/Boolean_function Boolean function], [http://en.wikipedia.org/ Wikipedia]. | + | * [http://en.wikiversity.org/wiki/Boolean_function Boolean Function], [http://en.wikiversity.org/ Wikiversity] |
| + | * [http://beta.wikiversity.org/wiki/Boolean_function Boolean Function], [http://beta.wikiversity.org/ Wikiversity Beta] |
| + | * [http://en.wikipedia.org/w/index.php?title=Boolean_function&oldid=60886833 Boolean Function], [http://en.wikipedia.org/ Wikipedia] |
| | | |
− | [[Category:Boolean algebra]] | + | [[Category:Inquiry]] |
− | [[Category:Cryptography]] | + | [[Category:Open Educational Resource]] |
| + | [[Category:Peer Educational Resource]] |
| + | [[Category:Combinatorics]] |
| + | [[Category:Computer Science]] |
| + | [[Category:Discrete Mathematics]] |
| [[Category:Logic]] | | [[Category:Logic]] |
| [[Category:Mathematics]] | | [[Category:Mathematics]] |