Finite-valued Logics for Information Processing

• Autorzy: Avron A. , Konikowska B.
• Języki publikacji: EN

Abstrakty

EN

We examine the issue of collecting and processing information from various sources, which involves handling incomplete and inconsistent information. Inspired by the framework first proposed by Belnap, we consider structures consisting of information sources which provide information about the values of formulas of classical propositional logic, and a processor which collects that information and extends it by deriving conclusions following from it according to the truth tables of classical logic, applied forward and backward. Our model extends Belnap’s in allowing the sources to provide information also about complex formulas. As that framework cannot be captured using finite ordinary logical matrices, if we want to represent each of the relevant logics with a single matrix, we employ Nmatrices for that purpose. In opposition to the approach proposed in our earlier work, we assume that the information sources are reasonable, i.e. that they provide information consistent with certain coherence rules. We provide sound and complete sequent calculi admitting strong cut elimination for the logic of a single information source, and (several variants of) the logic generated by the source and processor structures described above. In doing this, we also provide new characterizations for some known logics. We prove that, in opposition to the variantwith unconstrained information sources considered earlier, the latter logic cannot be generated by structures with any bounded number of sources.

Słowa kluczowe

EN

information processing; incomplete information systems; inconsistent information; finite logics; many-valued logics; non-deterministic logical matrices; sequent calculi

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 1
• Strony: 1--30
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Avron A.

autor

Konikowska B.

• Institute of Computer Science, Polish Academy of Sciences Ordona 21, 01-237 Warsaw, Poland,

Bibliografia

• [1] A. R. Anderson and N. D. Belnap, First Degree Entailments, Mathematische Annalen, Vol. 149 (1963), 302-319.
• [2] A. R. Anderson and N. D. Belnap, Entailment., Vol.1, Princeton University Press, Princeton N.J., 1975.
• [3] O. Arieli and A. Avron, Reasoning with logical bilattices, Journal of Logic, Language and Information 5 (1996), 25-63.
• [4] F.G. Asenjo, A Calculus of Antinomies, Notre Dame Journal of Formal Logic 7 (1966), 103-6.
• [5] A. Avron, Natural 3-valued Logics- Characterization and Proof Theory, Information and Computation 92 (1991), 105-139.
• [6] A. Avron, Logical Non-determinism as a Tool for Logical Modularity: An Introduction, in We Will Show Them: Essays in Honor of Dov Gabbay, Vol 1 (S. Artemov, H. Barringer, A. S. d'Avila Garcez, L. C. Lamb, and J. Woods, eds.), College Publications (2005), 105-124.
• [7] A. Avron, Multi-valued Semantics: Why and How, Studia Logica 92 (2009), 163-182.
• [8] A. Avron, J. Ben-Naim, and B. Konikowska, Processing Information from a Set of Sources, in Towards Mathematical Philosophy, (D. Makinson, J. Malinowski, and H. Wansing, eds.), Trends in Logic 28 (2009), Springer, 165-186.
• [9] A. Avron, and I. Lev, Non-deterministicMultiple-valued Structures, Journal of Logic and Computation, Vol.15 (2005), 241-261. A partial conference version in Proceedings of the 1st International Joint Conference on Automated Reasoning (IJCAR 2001) (R. Goré, A Leitsch, T. Nipkow, Eds), LNAI 2083, Springer Verlag (2001), 529-544.
• [10] A. Avron and A. Zamansky, Non-deterministic Semantics for Logical Systems - A survey, Forthcoming in Handbook of Philosophical Logic, Vol. 18 (D. Gabbay and F. Guenthner, eds).
• [11] N. D. Belnap, How computers should think, In G. Ryle, editor, Contemporary Aspects of Philosophy, 30-56. Oriel Press, Stocksfield, England, 1977.
• [12] N. D. Belnap, A useful four-valued logic, In G. Epstein and J. M. Dunn, editors,Modern Uses ofMultiple- Valued Logic, 7-37. Reidel, Dordrecht, 1977.
• [13] W. A. Carnielli and J. Marcos and S. de Amo, Formal inconsistency and evolutionary databases, Logic and Logical Philosophy, Vol. 8 (2000), 115-152.
• [14] W. A. Carnielli and M. Lima-Marques, Society semantics for multiple-valued logics, in Proceedings of the XII EBL- Advances in Contemporary Logic and Computer Science (Walter A. Carnielli and Itala M. L. D'Ottaviano, eds.), American Mathematical Society, Series Contemporary Mathematics, Volume 235 (1999), 33-52.
• [15] F. Dietrich and C. List, Strategy-Proof Judgment Aggregation, Economics and Philosophy, Vol.23 (2007), 269-300.
• [16] J. M. Dunn, Intuitive Semantics for First Degree Entailments and "coupled trees", Philosophical Studies 29 (1976), 149-168.
• [17] J.M. Dunn Relevant logic and entailment. Handbook of Philosophical Logic, vol.III (D. Gabbay, F. Guenthner - eds.), 1984.
• [18] M. Fitting, Kleene's three-valued logics and their children, Fundamenta Informaticae 20 (1994), 113-131.
• [19] M. L. Ginsberg, Multi-valued logics: A uniform approach to reasoning in AI, Computer Intelligence 4 (1988), 256-316.
• [20] I.M.L. D'Ottaviano and N.C.A. da Costa, Sur un problème de Jaśkowski. In Comptes Rendus de l'Académie des Sciences de Paris, Vol. 270 (1970), 1349-1353.
• [21] I. L.M. D'Ottaviano, The completeness and compactness of a three-valued first-order logic, Revista Colombiana de Matematicas, vol. XIX (1985), 31-42.
• [22] G. Priest, Reasoning about truth, Artificial Intelligence 39 (1989), 231-244.
• [23] D. J. Shoesmith and T. J. Smiley, Deducibility and Many-valuedness, Journal of Symbolic Logic 36 (1971), 610-622.