[Minimal disjunctive normal form] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Minimal disjunctive normal form
(Click here to view the original thread with full colors/images)
Posted by: Todd Rowland
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.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings