Talk:Algebraic normal form/Archive 1

Archive 1

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)

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)

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_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}+\!$
	$a_{1,2}x_{1}x_{2}+a_{1,3}x_{1}x_{3}+\ldots +a_{n-1,n}x_{n-1}x_{n}+\!$
	$\ldots +\!$
	$a_{1,2,\ldots ,n}x_{1}x_{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).

Obtaining the ANF

As far as I can tell, there doesn't seem to be a known algorithm for obtaining the algebraic normal form of a Boolean function (except for deriving the truth tables of every possible polynomial in n inputs and comparing the truth table of your function to those.) Does anyone know anything about algorithms for/research into deriving ANFs? 144.32.80.201 (talk) 19:06, 8 December 2008 (UTC)

It's not very hard to do it using the standard rules of propositional logic. Whether it will be optimal or minimal is a different question. You can define it recursively. For example, the ANF of a variable $v$ is simply $v$ itself. The negation of an ANF formula $f$ is $1\oplus f$ (If $f$ already had a constant term of 1, they zero out by $1\oplus 1=0$). The conjunction $f\wedge g$ where $f$ and $g$ are ANF formulae is also not very hard, simply distribute $\land$ over $\oplus$, for example for $f=abc\oplus de$ and $g=ae\oplus bc$, you get $f\land g=abcae\oplus abcbc\oplus deae\oplus debc$ (which can be simplified to $abce\oplus abc\oplus dea\oplus debc$ by idempotency). The disjunction $f\vee g$ where $f$ and $g$ are ANF formulae could equivalently be written as $\lnot (\lnot f\land \lnot g)$, and this you can figure out using the rules for $\lnot$ and $\land$. Feel free to write this up properly and put it in the article. 129.240.71.6 (talk) 17:24, 15 March 2011 (UTC)

I've added that to the article — Olathe (talk) 16:26, 3 July 2013 (UTC)

exclusive or

The text says "exclusive or" but the formulas use +. They usually stand for just or. I think that's an error. 138.232.94.205 (talk) 11:00, 9 July 2012 (UTC)

+ stands for addition far more commonly than for OR (which is usually rendered as something like ∨) and it's quite fitting here, as XOR is equivalent to addition (modulo two). Perhaps ⊕ can be used instead, though. —Olathe (talk) 17:47, 7 February 2013 (UTC)

I would also prefer to write ⊕ instead of +. — Preceding unsigned comment added by 2001:638:708:30DA:221:CCFF:FECE:26DB (talk) 06:18, 17 May 2013 (UTC)

OK, I've changed the article to ⊕ — Olathe (talk) 16:50, 3 July 2013 (UTC)

Stale 2013 proposal

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

Removed template and closed merge proposal discussion as no consensus. Anarchyte (work | talk) 10:53, 19 November 2016 (UTC)

---

Given that no-one can be bothered to deal with the July 2013 proposal, nor comment on it on the talk page, I propose closing it as stale with no consensus, no case made, no support over more than 3 years. Perhaps Jochen Burghardt or Macrakis could act boldly on this one way or another, given their recent edits on the page. Klbrain (talk) 13:06, 7 November 2016 (UTC)

OK, I'll do it next weekend if no one else does. --Macrakis (talk) 15:32, 7 November 2016 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Merger with Zhegalkin polynomial

The algebraic normal form and the Zhegalkin polynomial are two names for the same thing, one emphasizing its roots in logic and the other its roots in algebra. They should be merged. There is useful and complementary content in the two articles. --Macrakis (talk) 17:37, 23 April 2019 (UTC)

@Macrakis: Before merging, we should cite some reliable sources to verify this. Jarble (talk) 20:53, 1 May 2019 (UTC)

@Jarble: Generally, different communities (logicians, algebraists, circuit designers, Russians, etc.) use different names, but there are plenty of sources which explicitly say that they're the same thing (and there are more names!):

• "A canonical form due to Zhegalkin, known in the U.S. as the Reed-Muller form..." -- Frank Markham Brown, Boolean Reasoning [1]
• "...the algebraic normal form <formula>. This representation in the form of Zhegalkin's polynomial..." -- A.S.Ambrosimov, "On the Distribution of the Weights of the Random Reed-Muller Codewords" [2]
• "...boolean functions represented in Algebraic Normal Form. This form was invented by Zhegalkin... From the algebraic point of view, ANF is a polylinear multivariate polynomial over the finite field of order 2 (Zhegalkin/boolean polynomials, Reed-Muller canonical form, Positive Polarity Form)" -- Pavel Emelyanov, "AND-Decomposition of Boolean Polynomials with Prescribed Shared Variables" [3]
• "...the linear XOR-operation was used to define an algebraic normal form with the structure of a polynomial of conjunctions. This normal form is widely called Reed-Muller expansion. The basic decomposition of this normal form, however, was given by Davio... the positive and the negative Davio decomposition, two fixed polarity and 2k − 2 mixed polarity Reed-Muller normal forms can be specified. It should be mentioned that Zhegalkin suggested such a polynomial." -- Bernd Steinbach, Christian Posthoff, "An Extended Theory of Boolean Normal Forms" [4]
• "Zhegalkin proposed to define a Boolean operation as what we now call variously a Zhegalkin polynomial, algebraic normal form, or Reed-Muller expansion" -- Vaughan Pratt, "Aristotle, Boole, and Categories" in Rohit Parikh on Logic, Language and Society [5]
• "The abbreviation ANF is often used for Algebraic Normal Form in cryptographic literature and in the Boolean Domain for Antivalence Normal Form [?!].... An AlgNF is also called positive polarity Reed-Muller form or Zhegalkin polynomial" -- Stuart W. Schneider, Jon T. Butler, "Bent Function Enumeration by a Circular Pipeline Implemented on an FPGA" in Bernd Steinback, ed., Further Improvements in the Boolean Domain [6]

--Macrakis (talk) 20:14, 2 May 2019 (UTC)