Two Forms of Dependence in Propositional Logic: Controllability and Definability

Jérôme Lang, Pierre Marquis

We investigate two forms of dependence between variables and/or formulas within a propositional knowledge base: controllability (a set of variables C controls a formula G if there is a way to fix the truth value of the variables in C in order to achieve G to have a prescribed truth value) and definability (C defines a variable y if every truth assignment of the variables in C enables us finding out the truth value of y). Several characterization results are pointed out, complexity issues are analyzed, and some applications of both notions, including decision under incomplete knowledge and/or partial observability, and hypothesis discrimination, are sketched.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.