Talk:Disjunctive normal form

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Bad grammar

The grammar given at the end of the article is incorrect. Specifically:

conjunct -> term conjunct -> ( conjunct and term )

needs to be rewritten as

conjunct_clause -> literal conjunct_clause -> conjunct_clause and term conjunct -> literal conjunct -> ( conjunct_clause )

...although as a matter of convention, conjunction has higher precedence than disjunction, and therefore DNF expressions need never use brackets.

incomplete definition?

I was taught that DNF was more than simply a sum of products. I was taught that each clause of products must contain every literal - thus making every equivelant function expand to the *same* DNF form (in other words, equivalent DNF forms do not exist, there is one per independant function). Please let me know if we should include this in the definition. Fresheneesz 21:04, 6 February 2006 (UTC)[reply]

History

Who introduced the use of DNF? Where are the early references to it in research? —The preceding unsigned comment was added by Kpturvey (talk • contribs) 15:36, 23 December 2006 (UTC).[reply]

It currently talks about a disjunction of clauses. Following the link of 'clauses' tells us that a clause is a disjunction of literals. So obviously this is wrong. It should be 'a disjunction of terms'. Indeed, a few lines lower it indeed mentions terms. Whoever is willing - please fix it. Thanks, Ofer —Preceding unsigned comment added by 132.68.247.49 (talk) 19:32, 14 October 2007 (UTC)[reply]

WikiProject class rating

This article was automatically assessed because at least one WikiProject had rated the article as stub, and the rating on other projects was brought up to Stub class. BetacommandBot 03:56, 10 November 2007 (UTC)[reply]

Bad example of "exponential explosion of the formula".

The formula given as an example cannot be reduced. If you eliminated the subscripts on the X's it would be reducable, but I'm still not seeing an exponential reduction. Perhaps a series of nested OR's alternated with AND's would make it complex enough. c.pergiel (71.117.211.59 (talk) 22:39, 13 February 2010 (UTC))[reply]

Would you care to explain what do you mean by "reduced"? The formula in question has length O(n), it's not in DNF, and when converted to DNF it indeed has 2ⁿ terms:

\bigvee _{I\subseteq \{1,\dots ,n\}}{\Bigl (}\bigwedge _{i\in I}X_{i}\land \bigwedge _{i\notin I}Y_{i}{\Bigr )}.

It thus perfectly illustrates the point being made.—Emil J. 11:25, 15 February 2010 (UTC)[reply]

Normal Form

The 2nd sentence starts with "As a normal form, ...". However, I would question whether DNF is (despite the name) a normal form. As per the Wikipedia defn, a normal form is a standard way of representing an object. However DNF does not give you a standard way of representing equivalent formulas. E.g. $p\wedge q$ and $(p\wedge q)\vee (p\wedge q)$ are two different DNF representations of equivalent formulas. The same argument applies to CNF Houseofwealth (talk) 07:18, 20 February 2010 (UTC)[reply]