Re: Generalized Quine-McCluskey



sashaDOTmal wrote:

I just posted a reply, which seems to have disappeared into
the aether, g-dammit, so I've rewritten it. Sorry if a repetition
appears.

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 values. Why not let your values be
{1,...,2^d) ?

As it happens, the number of elements in any finite Boolean algebra
is 2^m for m > 0 (Huntington 1904).

For example, for a Boolean algebra of 8 = 2^3 elements we can
pick 3 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 gcf(a, b)

(or vice versa).

Under this scheme we have elements F and T (1 and 30) such that
for any element a

a v F = a and a ^ T = a

so we also have negation: for any element a there is an
element ~a such that

a v ~a = T and a ^ ~a = F.

Any axiom set for a Boolean algebra will be satisfied by
this 8-member model.

This suggests that the prime implicants of a formula
(whatever those may be) will be the same, regardless
of what 2^d valued model we may have in mind.

If we wish to have a model with d elements (2^m < d < 2^(m + 1))
we will have to add some non-tautologous axioms to specifically
exclude some of the 2^(m + 1) elements. We may put these axioms
in a normal form so as to make clear what elements we are
excluding, e.g.

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

I'm guessing that you are looking 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 do not vary
in different models of 2^d elements:

The first problem is that there are equivalent formulae, e.g.

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

All of these imply each other, and so are not prime by your
definition.

If we disallow repetitions of atomic formula, but allow
negation, we have as prime implicants of, say, a --

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

but not

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

etc., each of which implies one or more of the previous group, as
well as a.

When we are dealing with conjunctions of reduced formulae (so
that there are no equivalent formulae) then implication is
the same as inclusion, i.e. A implies B if every conjunct
of B is a conjunct of A; that is, the conjuncts of A
include the conjuncts of B.

So the problem reduces to finding formulae that include
as a conjunct the target formula phi, but do not include
a subformula that includes phi as a conjunct.


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

I doubt that what I have said above addresses your concerns,
but I'm not really sure what your concerns are.

--
hz
.