Changes

Boolean function (view source)

Revision as of 13:10, 22 October 2008

919 bytes removed , 13:10, 22 October 2008

trim

Line 5: Line 5:

A '''boolean mask operation''' on boolean-valued functions combines values point-wise, for example, by [[exclusive disjunction|XOR]], or other [[boolean operator]]s.

−

~~==Algebraic normal form==~~

−

~~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).~~

−

~~{| cellpadding="4"~~

−

|-

−

~~|<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).

==See also==

Jon Awbrey

12,080

edits