Por Sérgio Marcelino (IST - Universidade de Lisboa).
Why should we consider moving from the standard notion of logical matrix introduced by Łukasiewicz more than a century ago? We will explore the impact of adopting partial and non-deterministic matrices (PNmatrices) as semantical units.
Partial non-deterministic matrices (PNmatrices) embody a generalized notion of truth-functionality by interpreting the connectives in the language through a multi-function rather than a function. The usual semantics over logical matrices smoothly generalizes to PNmatrices by reading the multi-function interpreting each connective as giving a (possibly empty) menu of possible outputs to each input. This menu is interpreted non-deterministically, in the sense that valuations are not completely determined by the values they assign to the variables. Instead, every valuation is built by layers and has the freedom to give each complex formula any of the values from the menu associated with the head connective and the inputs determined by the values of the immediate subformulas.
The initial motivation to step into this generalized setting was to obtain finite presentations of logics that could not be captured by finite matrices [1,2]. For many purposes PNmatrices preserve the good properties of finite matrices. These include important bridges with analytical calculi that enable purely symbolic decision procedures to decide the logic induced by a finite PNmatrix, including proof-search and counter model-generation functionalities [3,4]. Moreover, their greater plasticity has been essential for a number of compositionality results for combined logics [5,6]. We will take some time to illustrate this by showing that PNmatrices naturally emerge when we try to close a certain category of matrices for products [7].
Since there is always a flip side, we will also report on the challenges brought by this larger and richer setting. For instance, some naturally associated computational problems become undecidable, such as the problem of determining if the logic induced by a given finite PNmatrix has a theorem, or if two finite PNmatrices induce the same logic [8].
Finally, we discuss the challenges associated with extending the well established techniques of abstract algebraic logic to deal with PNmatrices [9].
[1] A. Avron and I. Lev. Non-deterministic multiple-valued structures. Journal of Logic and Computation, 2005.
[2] M. Baaz, O. Lahav, and A. Zamansky. Finite-valued semantics for canonical labelled calculi. Journal of Automated Reasoning, 2013.
[3] C. Caleiro, S. Marcelino. Axiomatizing non-deterministic many-valued generalized consequence relations. Synthese, 2021
[4] C. Caleiro, S. Marcelino. Analytic calculi for monadic PNmatrices. WoLLIC, 2019
[5] C. Caleiro, S. Marcelino. Disjoint fibring of non-deterministic matrices. WoLLIC, 2017
[6] C. Caleiro, S. Marcelino. Modular semantics for combined many-valued logics. Submitted
[7] C. Caleiro, S. Marcelino. Rediscovering partial non-deterministic logical matrices. Submitted
[8] P. Filipe, S. Marcelino, C. Caleiro. Computational properties of finite PNmatrices. Journal of Logic and Computation, 2022
[9] C. Caleiro, S. Marcelino, U. Rivieccio. Some more theorems on generalized consequence relations. Submitted
Transmissão via Zoom.
