Search

[EN]We study the complexity of the valued CSP (VCSP, for short) over arbitrary templates, taking the general framework of integral bounded linearly order monoids as valuation structures. The class of problems considered here subsumes and generalizes the most common one in VCSP literature, since both monoidal and lattice conjunction operations are allowed in the formulation of constraints. Restricting to locally finite monoids, we introduce a notion of polymorphism that captures the pp-definability in the style of Geiger’s result. As a consequence, sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Finally, we establish the dichotomy conjecture for the VCSP, modulo the dichotomy for classical CSP., The work was partly supported by the grant No. GA17-04630S of the Czech Science Foundation and partly by the long-term strategic development financing of the Institute of Computer Science (RVO:67985807).

[eng] This memoir is divided into two parts, devoted to two topics in (ab-stract) algebraic logic. In the first part we develop a hierarchy in which propositional logics “L” are classified according to the definability conditions enjoyed by the truth sets of the matrix semantics Mod* L. More precisely, we focus on conditions belonging to the conceptual framework of the Leibniz hierarchy, meaning that they can be characterized by means of the order-theoretic behaviour of the Leibniz operator. We study the class of logics such that truth is definable in Mod* L by means of universally quantified equations leaving one variable free. Then we study logics for which truth is implicitly definable in Mod* L and show that the injectivity of the Leibniz operator does not transfer in general from theories to filters over arbitrary algebras. Finally we consider an intermediate condition on the truth sets in Mod* L that corresponds to the order-reflection of the Leibniz operator. We conclude this part of the memoir by taking a computational glimpse to the Leibniz and Frege hierarchies. In the second part of this memoir we present an algebraic description of right adjoint functors between generalized quasi-varieties, inspired by the work of McKenzie. This result is achieved by developing a correspondence between the concept of adjunction and a new notion of translation between relative equational consequences. This correspondence provides a general explanation of the correspondence that appears in some well-known trans-lations between logics, e.g., Godel's translation of intuitionistic logic into the gobal modal logic 84 corresponds to the functor that takes an interior algebra to the Heyting algebra of its open elements and Kolmogorov's translation of classical logic into intuitionistic logic corresponds to the functor that takes a Heyting algebra to the Boolean algebra of its regular elements.

L'articolo si pone l'obiettivo di studiare un metodo per categorizzare la realtà che ci circonda e analizzarne le relazioni con il linguaggio in cui intendiamo parlarne. Vengono poi discussi i problemi filosofici che la formalizzazione comporta e le loro relazioni con il nostro processo di chiarificazione e conoscenza del mondo. Dopo aver mostrato come tutto ci si risolve nello studio dei rapporti che intercorrono tra la nozione di realtà, quella di linguaggio e quella di logica vengono presentate alcune possibili interpretazioni filosofiche, alcune confutate altre accettate, di questi rapporti. Infine si cerca di caratterizzare brevemente la relazione che il nostro pensiero deve instaurare con il linguaggio formale nel corso dei suoi processi deduttivi cercando così di legare questa nozione a quelle precedentemente introdotte., Rivista Italiana di Filosofia Analitica Junior, Vol 1, No 0.1 (2010): Tra linguaggio e pensiero / Between Language and Thought

Treballs Finals del Màster de Lògica Pura i Aplicada, Facultat de Filosofia, Universitat de Barcelona, Curs: 2019-2020, Tutor: Ramon Jansana i Tommaso Moraschini, The purpose of this work is to investigate what is the algebraic counterpart of the inconsistency lemma. This question already has an answer in [29]. We have only put together in this monograph all the results and concepts that are necessary to understand the whole building.

In this thesis we study completeness properties of infinitary propositional logics from the perspective of abstract algebraic logic. The goal is to under- stand how the basic tool in proofs of completeness, the so called Linden- baum lemma, generalizes beyond finitary logics. To this end, we study few properties closely related to the Lindenbaum lemma (and hence to com- pleteness properties). We will see that these properties give rise to a new hierarchy of infinitary propositional logic. We also study these properties in scenarios when a given logic has some (possibly very generally defined) connectives of implication, disjunction, and negation. Among others, we will see that presence of these connectives can ensure provability of the Lin- denbaum lemma. Keywords: abstract algebraic logic, infinitary logics, Lindenbaum lemma, disjunction, implication, negation