Talk:Algebraic normal form

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

Stub Class

Low Priority

Field: Foundations, logic, and set theory

Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

[edit] Zhegalkin-polynomial" (?)

As I remember, the "official" (so used) name of this idea is "Zhegalkin-polynomial" (?). Gubbubu 18:01, 29 May 2005 (UTC)

JA: Can you cite a source for this? Jon Awbrey 04:02, 20 March 2006 (UTC)

[edit] Toward concrete examples

JA: I thought it might help to have some concrete examples of algebraic normal forms, and thought that a good sampler would be to write out the sixteen bivariate boolean functions in ANF, but it took me a week to make a nice table of those in the form that I wanted, which I have included in the article on Zeroth order logic. I think that I have already written this out somewhere, under another name that I was using at the time, so I will go look for that, or else start from scratch, but I hope some interested parties will check my work to see if it's the same thing. Thanks, Jon Awbrey 13:00, 21 March 2006 (UTC)

[edit] Stuff to merge in fromboolean function

I found the following in boolean function, where it doesn't belong (so I removed it). It looks remarkably similar to parts of this article, but the algebraic degree is not defined here. --Hans Adler (talk) 22:29, 30 January 2008 (UTC)

A Boolean function can be written uniquely as a sum (exclusive or) of products (and). This is known as the algebraic normal form (ANF).

$f(x_1, x_2, \ldots , x_n) = \!$	$a_0 + \!$
	$a_1x_1 + a_2x_2 + \ldots + a_nx_n + \!$
	$a_{1,2}x_1x_2 + a_{1,3}x_1x_3 + \ldots + a_{n-1,n}x_{n-1}x_n + \!$
	$\ldots + \!$
	$a_{1,2,\ldots,n}x_1x_2\ldots x_n \!$

where $a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^*$ .

The values of the sequence $a_0,a_1,\ldots,a_{1,2,\ldots,n}$ can therefore also uniquely represent a Boolean function. The algebraic degree of a Boolean function is defined as the highest number of $x i$ that appear in a product term. Thus $f (x 1, x 2, x 3) = x 1 + x 3$ has degree 1 (linear), whereas $f (x 1, x 2, x 3) = x 1 + x 1 x 2 x 3$ has degree 3 (cubic).