KIT | KIT-Bibliothek | Impressum | Datenschutz

Simplification of many-valued logic formulas using anti-links

Beckert, Bernhard ORCID iD icon; Haehnle, Reiner; Escalada-Imaz, Gonzalo

Abstract:

We present the theoretical foundations of the many-valued
generalization of a technique for simplifying large non-clausal
formulas in propositional logic, that is called "removal of
anti-links". Possible applications of anti-links include computation
of prime implicates of large non-clausal formulas as required, for
example, in diagnosis. Anti-links do not compute any normal form of a
given formula themselves, rather, they remove certain forms of
redundancy from formulas in negation normal form (NNF). Their main
advantage is that no clausal normal form has to be computed in order
to remove redundant parts of a formula. In this paper, we define an
anti-link operation on a generic language for expressing many-valued
logic formulas called "signed NNF" and we show that all interesting
properties of two-valued anti-links generalize to the many-valued
setting, although in a non-trivial way.


Volltext §
DOI: 10.5445/IR/14997
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik – Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Buch
Publikationsjahr 1997
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA149976
KITopen-ID: 14997
Erscheinungsvermerk Karlsruhe 1997. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1997,11.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page