Propositional and predicate logics of incomplete information

Autor: Leonid Libkin, Marco Console, Paolo Guagliardo
Přispěvatelé: Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), University of Edinburgh, Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), This work was partly supported by EPSRC grants M025268 and N023056.
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Console, M, Guagliardo, P & Libkin, L 2022, ' Propositional and predicate logics of incomplete information ', Artificial Intelligence, vol. 302, 103603 . https://doi.org/10.1016/j.artint.2021.103603
University of Edinburgh-PURE
Artificial Intelligence
Artificial Intelligence, 2022, 302, pp.103603. ⟨10.1016/j.artint.2021.103603⟩
Console, M, Guagliardo, P & Libkin, L 2018, Propositional and Predicate Logics of Incomplete Information . in Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning (KR-18) . Principles of Knowledge Representation and Reasoning, Tempe, Arizona, USA, pp. 592-601, 16th International Conference on Principles of Knowledge Representation and Reasoning, Tempe, United States, 30/10/18 . < https://www.aaai.org/ocs/index.php/KR/KR18/paper/view/18068 >
ISSN: 0004-3702
Popis: International audience; One of the most common scenarios of handling incomplete information occurs in relational databases. They describe in-complete knowledge with three truth values, using Kleene’s logic for propositional formulae and a rather peculiar exten-sion to predicate calculus. This design by a committee from several decades ago is now part of the standard adopted by vendors of database management systems. But is it really the right way to handle incompleteness in propositional and pred-icate logics?Our goal is to answer this question. Using an epistemic ap-proach, we first characterize possible levels of partial knowl-edge about propositions, which leads to six truth values. We impose rationality conditions on the semantics of the connec-tives of the propositional logic, and prove that Kleene’s logic is the maximal sublogic to which the standard optimization rules apply, thereby justifying this design choice. For exten-sions to predicate logic, however, we show that the additional truth values are not necessary: every many-valued extension of first-order logic over databases with incomplete informa-tion represented by null values is no more powerful than the usual two-valued logic with the standard Boolean interpreta-tion of the connectives. We use this observation to analyze the logic underlying SQL query evaluation, and conclude that the many-valued extension for handling incompleteness does not add any expressiveness to it.
Databáze: OpenAIRE
Externí odkaz: