Re: Generalized Quine-McCluskey



sashaDOTmal wrote:

Dear all,

I'm looking for the generalization of the Quine-McCluskey algorithm in
case the underlying domain is not two-valued but d-valued (d is a
natural number).

More precise below.
Let x1,...,xn be n variables with range {1,...,d}. At atomic proposition
is "xi in A" for some 1<=i<=n and a subset A of {1,...,d}.

There are 2^d subsets of d elements. Why not let your range of
values be {1,...,2^d} ?

As it happens, the number of elements of a finite Boolean algebra
is 2^m for m > 0. What this means is that all tautologies remain
tautologies whatever the number of values the variables can
assume, i.e. whatever the number of elements of the (finite) model
(as long as they're a power of two).

For example, for a model of 8 = 2^3 elements, we can take
three prime numbers, form their product A, and the factors
of A will be a Boolean algebra under the operations of
least common multiple and greatest common factor, e.g.:

Let A = 2 * 3 * 5 = 30. The eight factors of 30 are:

{1, 2, 3, 5, 6, 10, 15, 30}

Let a v b =df lcm(a,b)
a ^ b =df gcm(a, b)

(or vice versa).

Then there are elements f and t (1 and 30) such that for
any element a

a v f = a and a ^ t = a

so we have negation: for each element a there is an element a'
such that a v a' = t and a ^ a' = f.

The axioms, and hence theorems, for a Boolean algebra are
satisfied by this 8-member model.


This suggests that the "prime implicants" (whatever that is) of
a given formula remain the same, whatever 2^d valued model you
have in mind.

If the model is not a natural power of 2, then some of the elements
must be specifically excluded by the use of non-tautologous axioms
which may be put in a normal form like:

~(a ^ b ^ c) ^ ~(~a ^ b ^ ~c) ^ ~(a ^ ~b ^ ~c) etc.

which tells us specifically which elements are to be excluded.

I take it that what you're looking for is how to reduce such
contingent formulae in an efficient manner.

A formula is
a boolean combination of atomic propositions. An implicant of a formula
f is a conjunction of atomic propositions that implies f. A prime
implicant g of f is an implicant of f so that there is no other
implicant f' of f so that g implies f'.

Assuming that the prime implicants of a formula are the same
whatever the number 2^d of elements/values of the model:

First of all is the problem of equivalent formulae. For example

a = (a ^ a) = (a ^ a ^ a) = (a ^ (b v b') = etc, etc.

These all imply each other, and are not prime by your definition.
If we disallow repetitions but allow negation, we have as
prime implicants of a:

a, (a ^ b), (a ^ ~b), (a ^ c), (a ^ ~c), (a ^ d), etc.

but not:

(a ^ b ^ c) (a ^ b ^ ~c) (a ^ ~b ^ c) (a ^ ~b ^ ~c) etc

since each of these imply one or more of the previous set of
prime implicants, as well as implying a.

When we're dealing with formulae that are conjunctions of formulae
in some reduced form (so no equivalent formulae), implication
is the same as inclusion: A implies B if each conjunct of B is a
conjunct of A, i.e., if the conjuncts of A include the conjuncts
of B.

Decision problem: given a formula, find its all prime implicants.
Combinatorial question: give a sharp upper bound on the number of prime
implicants of a formula.

Any help, references, ideas are appreciated.
Thanks a lot
Sasha

Probably what I wrote above doesn't really address your concerns,
but I'm not really sure what they are.

--
hz
.