Registered: Oct 2003
Posts: 103

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