# [Maxima] Logic algebra

Stavros Macrakis macrakis at alum.mit.edu
Thu Apr 10 16:50:29 CDT 2008

```Alexey,

Thanks again for your package.  In playing with it to see how I could
integrate it with my code, I found a few more bugs (see below).

-s

-----------------------------

(a AND b[1]) parses as (a AND b)[1] -- this is what causes the
previous bug (a AND a[1]) => a[1].

Similarly (f AND g(x)) parses as (f AND g)(x), which gives an error.

The binding strengths need to be adjusted.

---------

logicexprp(%pi) => true

---------

Various elementary simplifications are missing:

x EQ NOT x doesn't simplify to 0
x IMPL x doesn't simplify to 1
NOT x IMPL x doesn't simplify to x
x NAND x  etc. doesn't simplify to NOT x
etc.

---------

functionallycompletep seems to be inconsistent about whether constant
symbols/nullary functions need to be included:

fp(NOT x AND NOT y) => true (apparently doesn't require constant symbols)
fp(NOT x AND NOT y,0) => true
fp(NOT x AND NOT y,1) => true
but
fp(x AND NOT y) => false          ?? requires constant symbols?
fp(x AND NOT y,0) => false       ??
fp(x AND NOT y,1) => true         OK

----------

demorgan is indented incorrectly, implying that you intended something

demorgan (expr) := (
if not logicexprp (expr) then
false
else
expr : apply2 (expr,demorgor,demorgand),
apply (apply1, cons(expr,generalrules))
)\$

but in Maxima syntax, the apply(apply1...) is not part of the else
clause.  Correct indentation is:

demorgan (expr) := (
if not logicexprp (expr) then
false
else
expr : apply2 (expr,demorgor,demorgand),
apply (apply1, cons(expr,generalrules))
)\$

Is this what you intended?  It is equivalent to:

demorgan (expr) := (
applyrules( if logicexprp(expr)
then apply2 (expr,demorgor,demorgand)
else expr,
generalrules)\$

where applyrules(ex,r):=apply('apply1,cons(expr,generalrules))\$

If you change the parenthesization to reflect the indentation, you get
the incorrect result demorgan(g(x)) => false instead of g(x)

---------

In dualfunction, same indentation problem, but here the indentation is
correct and the parenthesization needs to be changed for the function
to make sense: dualfunction(h(x)) currently gives NOT g (this is an
internal g!); with corrected parenthesization it gives unknown, but
this is not correct either; shouldn't it be NOT h(NOT x) ?

--------

Same sort of problem in zhegalkin.

In general, the use of logicexprp seems to be problematic, because it
excludes functions. It also prevents simplification from reaching
inside functional expressions, e.g. booleanbasis(f(a XOR b)) doesn't
rewrite the XOR. Of course, you can use scanmap....

Why is this necessary at all?

----------

zhegalkin is extremely slow in some cases.  On my machine, zhegalkin(a
AND b AND (NOT c) AND (NOT d) OR a AND (NOT b) AND c AND (NOT d) OR a
AND (NOT b) AND (NOT c) AND d OR (NOT a) AND b AND c AND (NOT d) OR
(NOT a) AND b AND (NOT c) AND d OR (NOT a) AND (NOT b) AND c AND d)
takes 4.5 secs. Is this normal?

The problem seems to be that it is using the pattern-matching system
repeatedly which requires the expression to be rescanned many many
times.

-----------

You need to quote function names when you apply them, e.g.
apply(ev,...).  Otherwise, if someone assigns a value to a variable
called ev (I did this unintentionally! -- I wasn't trying to break

ev: 23\$
charvec(a,a) => error

Anyway, as I mentioned before, the ev function should almost *never*
be used in programming.

--------------
"NOT"() => NOT false

"IMPL"(a) => IMPL(a)  (should be an error)

----------

Using 0 and 1 for false and true is incompatible with Maxima
conventions so you have to do something like logical(oddp(x)) (where
logical converts) instead of simply oddp(x). This seems pointless.
```