Changes

MyWikiBiz, Author Your Legacy — Wednesday May 01, 2024
Jump to navigationJump to search

Boolean function (view source)

Revision as of 20:24, 5 November 2015

1,617 bytes added ,  20:24, 5 November 2015
update
Line 1: Line 1: −
In [[mathematics]], a '''finitary boolean function''' is a [[function (mathematics)|function]] of the form ''f''&nbsp;:&nbsp;'''B'''<sup>''k''</sup>&nbsp;&rarr;&nbsp;'''B''', where '''B'''&nbsp;=&nbsp;{0,&nbsp;1} is a ''[[boolean domain]]'' and where ''k'' is a nonnegative integer.  In the case where ''k''&nbsp;=&nbsp;0, the "function" is simply a constant element of '''B'''.
+
<font size="3">&#9758;</font> This page belongs to resource collections on [[Logic Live|Logic]] and [[Inquiry Live|Inquiry]].
   −
More generally, a function of the form ''f''&nbsp;:&nbsp;''X''&nbsp;&rarr;&nbsp;'''B''', where ''X'' is an arbitrary set, is a ''[[boolean-valued function]]''.  If ''X'' = '''M''' = {1,&nbsp;2,&nbsp;3,&nbsp;&hellip;}, then ''f'' is a ''binary sequence'', that is, an infinite [[sequence]] of 0's and 1's.  If ''X'' = [''k''] = {1,&nbsp;2,&nbsp;3,&nbsp;&hellip;,&nbsp;''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]]
Jon Awbrey
12,080

edits

Retrieved from "https://mywikibiz.com/Special:MobileDiff/50603...466830"

Navigation menu