Boolean function: Difference between revisions

Revision as of 18:39, 12 March 2006

Revision as of 21:21, 12 March 2006

Line 16:

|-

|<math>f(x_1, x_2, \ldots , x_n) = </math>

|<math>a_0 \oplus+</math>

|-

|

|<math>a_1x_1 \oplus+ a_2x_2 \oplus+ \ldots \oplus+ a_nx_n \oplus+</math>

|-

|

|<math>a_{1,2}x_1x_2 \oplus+ a_{n-1,n}x_{n-1}x_n \oplus+</math>

|-

|

|<math>\ldots \oplus+</math>

|-

|

Line 31:

|}

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 \oplus+ x_3</math> has degree 1 (linear), whereas <math>f(x_1,x_2,x_3) = x_1 \oplus+ x_1x_2x_3</math> has degree 3 (cubic).

==See also==