Gradient Logic
Notes on Gradient Logic

by Joseph Goguen

1. Introduction

This note considers a very strange logic, one that is closer to ideas of Newton than to those of Boole, and that is suitable for use in designing and building interactive multimedia systems, such as interactive museums, computer games, adaptive educational tools, interactive novels, etc. One basic aspect of such systems is their dynamics: as users interact with the system, its predicates may have different values, with different effects in different contexts, and especially at different times.

The evolution of the ideas in these notes is rather complex, and much of the history will be obscure to computer scientists. The creation of structural linguistics by the Swiss linguist Ferdinand de Saussure around the turn of the century is probably a better starting point than most. His work was of course followed up by linguists, but more interestingly, also by the French anthropologist Claude Levi-Strauss. After that comes a whole school of structuralist and poststructuralist thought in France, including (at least) the disciplines of sociology and literature, as well as anthropology and linguistics; often the term semiotics is used as an umbrella name for this work (though that term is also used in many other more specialized ways). Skipping over Roland Barthes and many others, we come to Algirdas Greimas, who became interested in the dynamics of stories, drawing on a tradition that goes back to the Russian folklorist Vladimir Propp, as well as on poststructuralism. His work was, to some extent, formalized by Jean Petitot, using ideas from catastrophe theory in the form popularized by Rene Thom. (Petitot's ideas are not yet available in English, so my notion of what he did comes mainly from secondary sources.)

Finally we come to the work of Peter Bøgh Andersen on (what he calls) computer semiotics, which directly addresses the applications mentioned in the first sentence of this section. His two exciting papers, "Multimedia Phase Spaces" and "Dynamic Logic," directly inspired these notes, which were written for a course on user interface design at UCSD. Andersen's work is very innovative, and yet seems quite practical for a kind of computer application that may become extremely important over the next few years. This work is also interesting for the connections that it builds between the sciences and the humanities.

This whole area of investigation is still at an early stage; therefore formalizations should be considered tentative, and are also likely to be incomplete; in particular, there are likely to be some bugs in the following, and there are certain to be some gaps.

2. Basic Ideas

We represent "predicates" by real-valued "potential functions," which generate "force fields" over a space X, defined to be their gradient vector fields. These will be used to move "actants" (which may be people, cars, cats, icons, windows, etc. - of course, not real ones, but their representations on a computer screen, in a movie or a multimedia environment, etc.), represented as points in X, in proportion to the gradient, in practice at discrete intervals of time.

To get started, let's restrict to X the real line (or an interval), so we have real valued functions of a real variable, which we will assume are piecewise continuously differentiable. Let's also adopt the convention that a "predicate" (or potential function) P has derivative denoted P' (sorry, this is as close as i can get to Newton's notation for derivative in pure ascii), which is piecewise defined. It follows that adding a constant to P makes no difference to the dynamics of actants under P, and so it makes sense to define equality in this logic to indicate that two potential functions differ only by an additive constant (except possibly on a set of isolated points).

Note also that multiplying a potential function by a positive constant will only change the time scale; let's write P ~ Q iff P(x) = c*Q(x) + d, for c any positive constant and d an arbitrary constant. More generally we will use ~~ to indicate equivalence under nonlinear change of time, i.e., multiplication by a positive function, plus addition of an arbitrary constant.

Throughout these notes, it will be worthwhile to consider a simple "standard" example with P(x) = (x - a)^2 and Q(x) = (x - b)^2 (where ^ indicates superscript). These predicates move actants towards their minima, at a and b, respectively. To be more concrete, let X be the real interval of visible pure colors, and let a and b correspond to red and yellow, respectively.

Andersen has given (what i consider) a brilliant definition of negation,

     (not P)' = -1/P'
This is easily shown to satisfy the double negation law
    not not P = P
(where we really do need equality defined only up to an additive constant).

Andersen also defined conjunction and disjunction as

     (P and Q)(x) = max{P(x),  Q(x)}

     (P or Q)(x)  = min{P(x),  Q(x)} .
These definitions are exactly the duals of those that are usual in fuzzy logic. However, these definitions are somewhat less convincing than that of negation, because they can introduce new discontinuities, and moreover the value of the gradient at each point only depends on one of the constituents, not both.

3. Disjunction

Some work I did long ago on fuzzy logic (Synthese 1968) suggested using multiplication for conjunction. So if we again dualize, this suggests defining disjunction by
     (P or Q)(x) = P(x) * Q(x) .
This varies smoothly with both arguments. Moreover, for our "standard" example, P(x) = (x-a)^2 and Q(x) = (x-b)^2, we get valleys ("basins of attraction" in the dynamical systems jargon) at a and b, with a ridge between them, and high walls on each side - which is exactly what disjunction should do. These assertions use the product rule for differentiation,
    (P or Q)' = P*Q' + Q*P' .
In our color example, P or Q is red or yellow.

Of course, this disjunction is associative and commutative, but not idempotent, since in fact

    (P or P) = P^2 ,
which is an "intensification" of P, and in an interesting way, since in our standard example, it flattens the potential function near a (since the squares of numbers < 1 go down) while making the walls (outside a +/- 1) steeper. If we form the disjunction of even more copies of P, the resulting curve flattens even more near the zero, and the walls get even steeper a bit away from the zero, because
    (P or P or ... P) = P^n ,
for n copies of P.

4. Conjunction

For a couple of days I was stumped by conjunction. One idea was to believe de Morgan, in which case a small exercise in the calculus gives
    P and Q = not(not P or not Q) = -(P * Q) ,
as a candidate for conjunction. This isn't too bad for the standard example, because there is a nice valley between a and b, with peaks on each side (at a and b); but unfortunately, the sides go sharply down after that, not up.

However, this logic is so strange that i dont see any reason to suppose we should believe de Morgan. Walking home one evening, an extremely simple and very reasonable definition dawned on me that I should have seen in the first place,

     P and Q = P + Q .
For the standard test case, this has derivative
     2x - a - b
which has just one zero, at (a+b)/2, which is exactly where we want it to be, since in our color example, P and Q is red and yellow, which will have minimum at orange.

It is interesting to note that since the slope is the sum of the slopes of the components, the valley will be steeper than that of either component. In paticular, we do NOT have

     P and P = P ,
because P and P is an "intensified" version of P; instead
     P and P = 2 * P .
This isn't as unreasonable it might seem at first; e.g., think of examples like which show that natural language conjunction really isn't like conjunction in mathematical logic. In the color example, "red and red" gives a narrower range of color frequencies centered at red.

It is pleasant that we get one distributive law for and/or,

     P or (Q and R) = (P or Q) and (P or R) .
However, we dont get the other distributive law, of which i still dont know quite what to make.

5. Truth Constants

If we define a "truth constant" to be a function whose derivative is zero, then there is just one, since additive constants dont matter; the constant function roughly speaking means "anywhere" or in modern slang "whatever"; let's denote it A. It has no dynamics - it represents an actant that just rests wherever it happens to be.

In the color example, A just means "any color at all".

This notion of constant isn't very interesting, so let's redefine a truth constant to be a function whose derivative is a constant; this makes sense because only the derivative affects dynamics. The result is that our strange logic gets more truth constants than you might expect, and none of them are much very like the "true" or "false" of traditional mathematical logic (or Boolean algebra).

The function with derivitive -1 (or any negative value) can be thought of as "less" or "down" or maybe "bottom", since actants are always drawn towards minus infinity, while +1 (or any positive value) can be thought of as "more" or "up" or maybe "top". Let's write M for the +1 case and L for the -1 case.

In the color example, L takes us off the scale towards infrared, while M takes us off scale towards ultraviolet.

We now get some strange "laws of thought":

     (P or M)(x) = P(x) * x

     (P or L)(x) = - P(x) * x

     A or P ~ P
(so A behaves rather like false here.) Plus we have
     not L = M

     not M = L
which seems good. We can do similar calculations for conjunction,
     P and M ~~ P
provided P is always positive (since P(x) + x = P(x)(1 + x/P(x)) and (1 + x/P(x)) is always positive. (More generally, if P has some isolated zeroes, then "P and M" may have isolated singularities that are not shared by P.)

Similarly, we can get

     P and L ~~ P
provided P(x) is greater than or equal to x + c everywhere, for some constant c. And of course (quite easily),
     P and A = P
(so A behaves like true here.)

The strangest "truth value" arises from the desire to have the system closed under the various logical operations; in particular, we want "not A" to have some value: but because this requires dividing by zero everywhere, the result can only be the totally undefined function. Let's denote it by U; it means "annihilation" - it throws actants out of the game entirely; there is no place at all where they can have a well defined gradient. The following hold because doing airthmetic with undefined values cannot ever yield defined values.

     not A = U

     not U = U

     P and U = U

     P or U = U
If we allow U then we might think undefined values could be allowed in other functions wherever we like; this would certainly give more truth constants, though they would all be rather boring; but i think undefined values should only be allowed for proper singularities in otherwise continuous functions. (In which case, it could be argued that we shouldnt allow U at all.)

In the color example, U mean no color at all.

It should be emphasized that this is a complete classification of all possible constants in our logic.

6. Miscellaneous

Our notion of equality is a congruence for conjunction and disjunction, in the sense that if P1 = P2 and Q1 = Q2, then P1 + P2 = Q1 + Q2 and P1 * P2 = Q1 * Q2; equality is also a congruence for negation, in that P1 = P2 implies not P1 = not P2. However, ~ and ~~ are not congruences for conjunction and disjunction, which means that they have to be handled carefully. For example, L ~ 2L and of course M ~ M, but L + M ~ 2L + M is not true, since the left and right sides are A and L, respectively. However, ~ is a congruence for negation. The relation ~~ is even less of a congruence than ~ is, since not even negation works.

We gave been using at least 3 different oppositions; in particular, Andersen's negation is composed from two other opositions, namely arithmatic negation and reciprocal, and we have already seen arithmatic negation appear in some of our formulae. This observation is interesting because of Greimas's famous semiotic square, each vertical side of which is an application of one kind of negation, and each horizontal side of a second:

              P ---------- P'
              |            |
              |            |
              |            |
              |            |
             -P --------- -P'
Thinking a little more about the equivalence ~, any function whose derivative is always positive is equivalent to M, and any whose derivative is always negative is equivalent to L. Catastrophe theory provides a more sophisticated approach to this kind of equivalence whereby functions just have to have the same pattern of derivatives; something like this might be of use in the future.

7. Notes

We should be able to do pretty much the same things for multivariate functions, using partial derivatives etc, and all results should be pretty much the same.

There are almost certainly bugs in the above, both in calculations and interpretations; also some other interesting calculations just havent been done yet. Thanks to Prof. Andersen for catching some bugs and unclarities.

Question: would it be better to use something like =~ for our equality relation on potential functions?

Question: changes of time scale should really concern the arguments of a potential function, not its values. Is this worth bothering about?

To CSE 271 homepage
To CSE 171 homepage
To my homepage
This draft was mainly written in November 1997, and was lightly edited on 11 March 2000.