A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Minimal disjunctive normal form
  Last Thread   Next Thread
Thread Post New Thread    Post A Reply
Todd Rowland
Wolfram Research

Registered: Oct 2003
Posts: 116

Minimal disjunctive normal form

A couple NKS updates regarding the minimal disjunctive normal form. There is a demo from Michael Schreiber, and there is a minor typo in the book code.

On p.1095 , in the definition of QM, instead of Length[s] it should be Length[p].

The prime implicants might be more numerous than the number of variables, but often is not, so that typo's consequences are not easily noticed.

The basic idea is to start with all of the true instances of the expression, so the original expression is the same as an Or of the conjunction of those instances. Then the prime implicants are the conjunctions with possibly some of the variables missing to avoid redundancies. The final step is to choose the smallest set of prime implicants necessary.

There is not necessarily a unique choice, so "normal form" is a bit imprecise.

It seems like the original idea was that the minimal expression could have some significance, and later was found to have practical applications. Seems like a very NKS-like notion.

Report this post to a moderator | IP: Logged

Old Post 10-30-2007 12:04 AM
Todd Rowland is offline Click Here to See the Profile for Todd Rowland Click here to Send Todd Rowland a Private Message Click Here to Email Todd Rowland Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-16 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives