CS Paper Radar

On Three-Valued Dependence-Like Logics

Yaroslav Petrukhin

cs.LO math.LO ·submitted 2026-10-06 13:00 UTC · v1
published

Abstract

In this paper, we investigate connections between dependence logics, viewed as a subclass of relating logics, and three-valued logics. More specifically, we identify common features of Epstein's subject-matter semantics and the variable-inclusion conditions characteristic of some infectious many-valued logics. Inspired by Del Cerro and Lugardon's sequent calculi for dependence logics, in which classical connectives are combined with connectives satisfying Epstein-style conditions, we introduce two three-valued dependence-like logics that combine classical conjunction and disjunction with infectious negation and implication. We also provide sound, complete, and cut-free bisequent calculi for these logics.

Journal ref
Logic and Logical Philosophy, 2026
DOI
10.12775/LLP.2026.016

Closest papers

Nearest neighbours by meaning across the whole index.

Connecting Extended Modal Dependence Logics

cs.LO ·2026-11-16 ·Johan van Benthem, Chenwei Shi, Wenfei Ouyang
similarity 0.65
Abstract

We consider three natural extensions of the basic decidable dependence logic LFD, adding, respectively, conditional dependence atoms, independence atoms, and identity atoms between variables. We show that these systems are all connected to first-order logic with identity by SAT reductions and in several cases also faithful translations. In particular, this implies that all these extended modal-style dependence logics are undecidable. This solves a number of problems left open in the original publication [1] introducing the LFD framework. The definitions and proofs presented here were found by ChatGPT and checked and streamlined as needed by the authors. At the end, we provide some discussion of what new things we learnt about dependence logics and about the methodology of using AI in logical research.

0.27

Tracking relevance syntactically: A nested approach to weak relevant logic

cs.LO ·2026-11-12 ·Fabio De Martin Polo, Han Gao
theory similarity 0.64
Abstract

The variable-sharing property (VSP) is regarded as a key feature of relevant logics, while the Craig interpolation property (CIP), formulated with respect to relevant implication, implies the VSP in constant-free propositional languages. However, to the best of our knowledge, no constant-free distributive relevant logic has previously been shown to enjoy the CIP. This absence of positive results has contributed to a widespread impression among relevant logicians that relevance and Craig interpolation are incompatible. In this work, we address this tension by proving that the negation-free fragment of base relevant logic B, denoted B+, enjoys both properties. Our proof is purely syntactic and is based on a novel nested sequent calculus featuring binary relevant blocks as primitive structural constructs. Unlike conventional nested sequent calculi, where unary nesting reflects the binary accessibility relation of Kripke semantics, our calculus employs a binary nesting operator that directly reflects the ternary relational structure of Routley-Meyer semantics for relevant logics. After establishing soundness and cut-free completeness of the calculus, we prove several meta-logical properties for the logic. Most notably, we provide the first syntactic proof of the VSP (along with a variety of its stronger variants) and the first proof of the CIP for B+, both derived directly from the cut-free system using a structural notion internalized within nested sequents.

0.27

A generalised and modular proof-theoretic semantics for sequent systems

cs.LO math.LO ·2026-10-16 ·Victor Barroso-Nascimento, Arghya Chakrabarty, Elaine Pimentel
similarity 0.59
Abstract

Base-extension semantics explains logical consequence via derivability in atomic systems. Extending this approach across logics requires careful control of structural principles and contexts. We present a modular sequent-based framework in which support is indexed by multisets of atomic resources and the semantic clauses for connectives are guided by their left introduction rules. The framework separates additive from multiplicative behaviour and makes explicit the contributions of structural rules and restrictions on sequents. We establish soundness and completeness for classical and intuitionistic propositional logic and for multiplicative-additive fragments of classical and intuitionistic linear logic. We then investigate axiomatic extensions of intuitionistic logic through Jankov logic. Two classes of atomic bases yield sound and complete semantics. Completeness is proven using two novel and modular methods using simulation bases, one of which is constructive. These results provide a common semantic treatment of several logical systems while identifying the additional conditions needed to extend the framework beyond structural variations.

0.16

Approximate Functional Dependencies---Implication Problem Revisited

cs.LO cs.DB ·2026-08-17 ·Nicolas Fröhlich, Matilda Häggblom, Åsa Hirvonen, Minna Hirvonen
similarity 0.57
Abstract · 11 pages

Functional dependencies are an important and well-studied class of database constraints that correspond to a notion expressed by dependence atoms in team logic. In practice, data often contain errors, so in some cases it might be useful to allow the database to have a small number of tuples that violate the desired dependency. Väänänen (2017) studied the axiomatisation of a notion of approximate dependence that specifies for each dependence atom how much of the database can be disregarded. We demonstrate that the interaction of approximate dependence atoms is more complicated than previously thought in the sense that there is a semantic consequence that is not captured by the inference rules introduced before. We show that Väänänen's axiomatisation is still complete in the restricted case of unary dependencies. We also consider the complexity of model checking for approximate dependence: it is NP-complete for disjunctions of two atoms and LOGSPACE-hard for individual atoms.

0.21

Paraclassical Logics with Two Negations

cs.LO ·2026-10-29 ·Pawel Pawlowski, Pietro Vigiani
publishedhot direction similarity 0.56
Abstract · In Proceedings NCL'26, arXiv:2610.34489

We study three paraclassical propositional logics with two negations, CLoaN, CLouN, and CLauN, obtained by pairwise combining the one-negation systems CLuN, CLaN, and CLoN. CLuN's negation is glut-tolerant and paraconsistent, CLaN's negationis gap-tolerant and paracomplete, and CLoN's negation is both paraconsistent and paracomplete. We provide sound and complete two-valued non-deterministic semantics for each of the two-negations systems. We then focus on CLauN, the system containing the primitive dual pair of CLaN and CLuN negations. In this setting, we show deductive relationships between different negations expressible in CLauN; we show two diferent ways to recapture classical logic by means of translations, locally and globally; and we show a duality results for the multiple conclusion consequence relation of the logic.

0.48

On Some Logics Intermediate Between S4.2 and S4.3 Defined by the Notion of Independence

cs.LO ·2026-10-29 ·Maciej A. Hałapacz
published similarity 0.55
Abstract · In Proceedings NCL'26, arXiv:2610.34489

Hamkins and Loewe described modal logic S4.2 through the notion of sets of independent buttons - statements that are possibly necessary - and switches - necessarily contingent statements. In this article we investigate logics intermediate between S4.2 and S4.3 that are defined through a different notion of independence. We provide an axiomatic description of such logics, state some basic facts and prove various completeness and decidability results.

0.43

Three Types of Negation of Triple and its Elements and an Extension of Triple

cs.AI ·2026-09-08 ·Zhenghua Pan
similarity 0.54
Abstract · 29 papers, 9 figures

In various data models, the classical triple is a typical semantic data model. However, due to the design of the triple as a simple structure for representing positive assertions, it cannot sufficiently express different forms of negation present in the triple and its elements. This paper conceptually proposes that there are three distinct forms of negation within triples and their elements: contradictory negation, opposite negation and intermediary negation. Based on the the set SCOI and the logic LCOI+PLCOI with three kinds of negation, we propose an extension of triple that can distinguish and express these three different negations in the triple and its elements, called the TCOI triple with contradictory negation, opposite negation and intermediary negation. The TCOI triple is a semantic and structural extension of the classical triple. While retaining the ability to express positive assertions, it systematically introduces the three semantic dimensions of three negations, allowing these negations to independently act on the elements of the triple and on the whole triple. This significantly enhances the triple model capability to represent and reasoning about complex negative information. This paper also explores the expressive power and reasoning of the TCOI triple, as well as the application of TCOI triple implication reasoning in counterfactuals and counterfactual reasoning. We propose a truth-value (continuous value) algorithm for TCOI triple implication reasoning and perform its calculation through an example of the counterfactuals and counterfactual reasoning.

0.23

Essence and accident modalities meet Belnapian truth values

cs.LO math.LO ·2026-10-06 ·Yaroslav Petrukhin
published similarity 0.53
Abstract

This paper investigates many-valued generalisations of the classical essence and accident modalities. In two-valued logic, a proposition is essentially true (resp. false) if, whenever it is true (resp. false), it is necessarily true (resp. false); it is accidentally true (resp. false) if it is true (resp. false) but not necessarily so. Many-valued logics provide a natural setting for introducing further modalities of this kind. We focus on Belnap-Dunn's First-Degree Entailment (FDE), a four-valued system that generalises the classical truth values. More precisely, we consider an extension of FDE with Boolean negation and implication. In addition to modalities of essential and accidental truth and falsity, we define modalities of essential and accidental inconsistency and indeterminacy. We present a four-valued S5-based Kripke semantics and cut-free hypersequent calculi for the resulting logics. We then prove semantic and syntactic embedding theorems for these logics into a four-valued version of S5 with necessity and possibility modalities. These embeddings clarify the intended interpretation of the Belnapian essence and accident modalities and yield soundness, completeness, and cut-admissibility results.

0.39