On propositional definability

doi:10.1016/j.artint.2007.12.003

On propositional definability

2008-05-01

15

OA

AI

DOI：10.1016/j.artint.2007.12.003

原文链接

查看原文

摘要

En 中文

In standard propositional logic, logical definability is the ability to derive the truth value of some propositional symbols given a propositional formula and the truth values of some propositional symbols. Although appearing more or less informally in various AI settings, a computation-oriented investigation of the notion is still lacking, and this paper aims at filling the gap. After recalling the two definitions of definability, which are equivalent in standard propositional logic (while based on different intuitions), and defining a number of related notions, we give several characterization results, and many complexity results for definability. We also show close connections with hypothesis discriminability and with reasoning about action and change. (C) 2008 Elsevier B.V. All rights reserved.

Keyword:

knowledge representation

propositional logic

computational complexity

definability

hypothesis discriminability

reasoning about action and change

On propositional definability

摘要

AI总结

期刊

机构