What is Redlog?
Redlog is an integral part of the interactive computer algebra system Reduce. It supplements Reduce's comprehensive collection of powerful methods from symbolic computation by supplying more than 100 functions on first-order formulas. Redlog has been publicly available since 1995 and is constantly being improved. The name Redlog stands for Reduce Logic System.
Interpreted First-Order Logic
Redlog generally works with interpreted first-order logic in contrast to free first-order logic. Each first-order formula in Redlog must exclusively contain atoms from one particular Redlog-supported domain, which corresponds to a choice of admissible functions and relations with fixed semantics. Redlog-supported domains include nonlinear real arithmetic (Tarski Algebra), Presburger arithmetic, parametric quantified Boolean formulas, and many more.
Connectivity
Reduce has been designed as an interactive computer algebra system. The Reduce source distribution includes a C library for managing Reduce processes and communicating with these processes. Besides communication via Reduce command strings, e.g., an XML-based communication protocol can be easily realized.
License
Both Reduce and Redlog are open-source and freely distributed under a very liberal FreeBSD License.
Quantifier Elimination Procedures
Effective quantifier elimination procedures for the various supported
theories play a central role in Redlog: Given a first-order
formula φ, Redlog computes an equivalent
formula φ′ that does not contain any quantifier. Here
is an example in the real domain:
Decision Methods
Redlog's quantifier elimination procedures are also decision procedures.
For instance, Redlog's quantifier elimination computes "false" for the
decision problem ∀a∃b(φ) with φ as
above. Some further decision methods in Redlog are not based on quantifier
elimination.
Formulas, Normal Forms, and Simplification
Redlog provides a productive environment for constructing, analyzing, and manipulating formulas. There are various normal form computations and advanced logical and algebraic simplification techniques available.