An Expert System Devoted to Automated Music Identification and Recognition - Intelligent Music Information Systems: Tools and Methodologies - page 93

and a polynomial of M, is also an ideal. Moreover,
it is the minimum ideal containing L ∪ M.
A process of reduction modulo an ideal L,
denoted “normal form” (NF), can be applied to
any polynomial, g, in A ; g can then be expressed
as a polynomial in L plus the normal form of g.
In the simple example of the multiples of 5
and the ring of integer numbers, the normal form
of an integer would be the remainder of dividing
it by 5.
Bruno Buchberger was able to build in 1965
a constructive method for calculating normal
forms in polynomial rings using very particular
“bases” (set of generators) of ideals (Gröbner
Bases, named after his PhD advisor, Professor
Gröbner) (Buchberger, 1965). If “L” denotes a
polynomial ideal, the main result is:

They allow translation of any logical formula
into a polynomial. The coefficients of these poly-
nomials are just 0 and 1 (more formally, the coef-
ficients of the polynomial ring A are in Z/Z2) and
the maximum power of variables is 1, as greater
powers are reduced to 1 (more formally, we are
working in the quotient ring A /I, that is, simpli-
fying modulo I, where I is the ideal generated by
the polynomials of the form variable 2 -variable ).
The inference engine is based on the follow-
ing theorem, which is illustrated in Figure 2. The
theorem is here referred to our ES, but is totally
general.

Theorem: A formula (here a musical style
assignation) “α”, is a tautological consequence
of the formulae in the union of the two sets {A1,
A2, ..., Am} ∪ {B1, B2, ..., Bk} that represent,
respectively, a maximal consistent subset A of the
set F of potential facts (the subset that describes
a melody) and the set of all production rules of
ES1, if and only if the polynomial translation of
the negation of “α” belongs to the ideal, sum of
the three ideals, I+K+J generated, respectively,
by the set of the polynomials {x1 2 -x1, x2 2 -x2, ...,
i1 2 i12-i1, …, z4 2 -z4}, by the set of the polynomial
translations of the negations of A1, A2, ..., Am
and by the set of the polynomial translations of
the negations of B1, B2, ..., Bk.
This result can be introduced almost directly
in CoCoA as will be detailed below.
That “α” is a tautological consequence of the
formulae in {A1,A2,...,Am} ∪ {B1,B2,...,Bk}, can
be checked in CoCoA by typing:

g ∈ L if and only if NF(g, L) = 0

and therefore the “ideal membership problem”
was solved!

Definition: A logical formula α is a “tauto-
logical consequence” of a set S of formulae if
and only if whenever all formulae in S are true,
α is also true.

application to automated extraction
of tautological consequences

The basic two-valued logical formulae can be
translated into polynomials the following way:

¬X1 is translated into the polynomial 1+x1
X1 ∨ X2 is translated into the polynomial
x1+x2+x1*x2
X1 ∧ X2 is translated into the polynomial
x1*x2
X1 → X2 is translated into the polynomial
1+x1+x1*x2

NF(NEG(alpha),I+K+J);

where NF is the command “normal form”. If the
output is 0, the answer is “yes”; if the output is
different from 0, the answer is “no”.