Talk:Disjunctive normal form

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.— Preceding undated comment added 15:05, 22 January 2008

Yes, far better. If only these expressions were coming from somewhere (conjunct_clause) and going somewhere (term) ...— Preceding undated comment added 12:19, 3 January 2013

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)

The current version of this article does describe this, calling it the full DNF. -- ToE^T 03:02, 10 November 2011 (UTC)

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

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)

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)

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

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)

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)

DNF and NP

An IP editor was right to remove a claim about DNF and the complexity class NP. The problem is that when we convert a CNF to a DNF it gets much, much longer. But once we have a DNF, we can tell if it is satisfiable in time that is linear in the length of the DNF. So "is this DNF satisfiable" is in P. I don't have a good book reference at hand, but here's a page at stackexchange that has some info [1], which is at least enough to see that the material that was in the article is questionable. — Carl (CBM · talk) 14:31, 7 January 2018 (UTC)

@CBM: I agree with you that checking the satisfiability of a DNF is in P. However, the disputed sentence is about checking the universal validity of a DNF.

By the duality principle, we can simultaneously exchange ∧ with ∨, and 0 with 1. A DNF like (x ∧ ¬y ∧ z) ∨ (¬x ∧ ¬z) is 1 for every variable assignment if its "dual" formula, which is a CNF, in the example: (x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬z), is 0 for every variable assignment. Deciding the latter is an NP-complete problem, hence so is deciding the former.

I thought the disputed sentence would convey this argument. For this reason, I'd restored it until 109.252.66.98 would come up with a more detailled explanation. - By the way: the stackexchange page says "DNF-SAT, of course, is efficiently solvable, in the same way that CNF-TAUTOLOGY is efficiently solvable", tacitly using a similar duality argument as I did above. Using this terminology, the disputed sentence was intended to mean "DNF-TAUTOLOGY is NP complete, in the same way that CNF-SAT is NP complete". Best regards - Jochen Burghardt (talk) 18:53, 7 January 2018 (UTC)

I think that the problem of telling whether a DNF formula is a tautology is coNP-complete, though, although I haven't had the time to think it through completely. The reductions in general require negating the formula and applying de Morgan's law; that reduces one problem (e.g. CNF-SAT) to the complement of the other (e.g. DNF-VALID). In any case, I'd be glad to see more about the complexity of DNF-SAT and DNF-VALID in the article, but I would need to sit down for a little while to work it out, since I don't seem to have any good references for it. — Carl (CBM · talk) 19:55, 7 January 2018 (UTC)

The way you phrase it is confusing and the source of misunderstanding. What you mean is falsifiability of DNF, i.e. finding variable assignment that makes formula false. If it was phrased this way I wouldn't remove that sentence, since that's obviously NP, just like satisfiability of CNF (preserving duality, as you put it). 109.252.66.98 (talk) 06:04, 10 January 2018 (UTC)

That's how I read it myself, thank you 109.252.66.98 (talk) 06:04, 10 January 2018 (UTC)

If you have a more understandable way to phrase it, I'd appreciate if you added it to the article. - I tried to find a source, but I didn't succeed. Some slides (p.4) claim NP-completeness of validity of DNFs, but they may have taken this claim, like some of its included pictures, from wikipedia itself. - Also, I'm afraid meanwhile I might have overlooked the distinction between NP- and coNP-completeness. Maybe CBM can help to get this straight? - Jochen Burghardt (talk) 14:47, 10 January 2018 (UTC)

I'm at a conference this week, but I think I can work on this next week once I am back. — Carl (CBM · talk) 17:36, 10 January 2018 (UTC)

Two questions about the conversion to DNF

(1)

Applying the given canonical term rewriting system

${\begin{array}{rcl}(\lnot \lnot x)&\rightsquigarrow &x\\(\lnot (x\lor y))&\rightsquigarrow &((\lnot x)\land (\lnot y))\\(\lnot (x\land y))&\rightsquigarrow &((\lnot x)\lor (\lnot y))\\(x\land (y\lor z))&\rightsquigarrow &((x\land y)\lor (x\land z))\\((x\lor y)\land z)&\rightsquigarrow &((x\land z)\lor (y\land z))\\\end{array}}$

how can the formula

$((\lnot (p\land q))\leftrightarrow (\lnot r\uparrow (p\oplus q)))$

be converted to a DNF?

(2)

Is it worthwhile mentioning that this term rewriting system is valid only in classical logic, as in intuitionistic logic the rewrite rules

${\begin{array}{rcl}(\lnot \lnot x)&\rightsquigarrow &x\\(\lnot (x\land y))&\rightsquigarrow &((\lnot x)\lor (\lnot y))\\\end{array}}$

do not hold?

Marc Schroeder (talk) 15:38, 19 December 2023 (UTC) Marc Schroeder (talk) 15:38, 19 December 2023 (UTC)

As for (1), appropriate "defintion" rules should be added for the remaining junctors, viz. $(x\leftrightarrow y)\rightsquigarrow (((\lnot x)\land (\lnot y))\lor (x\land y))$, etc. This is, however not included in the example from the reference. I'm pretty sure that the rewrite system remains canonical after extension, but I have no proof reference available.

As for (2), I guess the whole article applies only to classical logic. Since $\lnot \lnot x$ is different from $x$ in intuitionistic logic the former formula has no DNF in intuitionistic logic. Mentioning the differences is a good idea. I guess even the use of truth tables is problematic (e.g. for the case that $x$ is false, but $\lnot \lnot x$ is true, which value should be entered in the "x" column?). - Jochen Burghardt (talk) 14:37, 21 December 2023 (UTC)

References