On Wed Apr 9 12:30:28 CDT 2008, "Alexey Beshenov" <al at beshenov.ru> wrote:
> I've done a logic algebra package:
>
> http://beshenov.ru/maxima/logic/
>
> It defines operators "AND", "OR", "NOT" (written in uppercase,
> since "and", "or", "not" are built-in operators for predicates), as well as
> Sheffer stroke ("NAND"), Peirce arrow ("NOR"), implication ("IMPL"),
> equivalence ("EQ") and sum modulo 2 ("XOR").
>
> It does
>
> * truth tables,
> * conversion to the Boolean ({AND, OR, NOT}) and Zhegalkin ({AND, XOR, 1})
basises,
> * test on completeness (by Post's theorem),
> * perfect normal forms,
> * differentiation.
>
> (Also I have some draft code for minimization, but it isn't very useful since
> it represents the pure Quine-McCluskey algorithm and has to be improved.)
>
> Could it be placed in the /share/contrib? Could anyone try and review it?
>
> Thank you in advance.
>
> --
> Alexey Beshenov <al at beshenov.ru>
> http://beshenov.ru/
Hi, Alexey
Currently, the advanced topic in the logic algebra contains the below theories:
### Theory of Advanced Logic Minimization ###:
1. Karnaugh Map (upto ~4 vars, for debugging).
2. Quine-McCluskey (greater vars in tableaux, for medium problems).
3. Espresso-Exact (greater vars than Q-McC, for large problems).
4. Espresso-Signature (vars > (3.), heuristic local optimization, for
very large p.).
5. Boom-II (vars > (4.), heuristic local optimization with G.A., for
very huge p.).
### Theory of Advanced BDD Reduction ###:
1. ROBDDs (Reduced Ordered Binary Decision Diagrams).
2. Minimal ROBDDs (combinatory's problem, dynamic programming).
3. Local-Minimal ROBDDs using heuristics:
3.1 Window (generally not very good).
3.2 Sifting (heuristic very good and efficient).
3.3 Symmetric Sifting (sometimes its effcy is worser than Sifting).
3.4 Sifting with Transformations
(90% better than Sifting in size but it's complex and inefficient).
4. Shared ROBDDs.
5. Many types of BDDs.
The BDDs are so known as Branching Programs, and their purposes
are higher compression of the titanic truth tables, but sometimes
they've penalties as the exponential size of the multiplication's ALU.
Almost BDDs reductions detailed here are NP-Complete in the computation.
Sincerely, J.C.Pizarro