Logical inference and polyhedral projection

From MaRDI portal





If a (medical diagnosis) knowledge base contains atomic propositions \(x_ 1,\dots, x_ n\), and \(x_ 1,\dots, x_ k\) are the disease propositions, then finding all implies propositions that contain no other atoms but \(x_ 1,\dots, x_ k\) is a problem of projecting the knowledge base onto the variables \(x_ 1,\dots, x_ k\), and that is problem closely related to projecting a polyhedron. The main result of the paper is that polyhedral projection obtains precisely the inferences derived by a certain form of unit resolution, called unit \(K\)-resolution, which becomes unit resolution if all atoms in \(x_ 1,\dots, x_ k\) are erased. Unit \(K\)-resolution is proved to completely solve the logical projection problem for Horn clauses, that resolution algorithm is exponential when \(\underline n\) is proportional to \(\underline k\), but (quadratic) polynomial when \(\underline k\) is fixed. A number of new satisfiability algorithms are defined on the basis of polyhedral projection interpretation as inference method in propositional logic. For the entire collection see [Zbl 0772.68004].











This page was built for publication: Logical inference and polyhedral projection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4202942)