Three-valued logics blend dependence and classical connectives
On Three-Valued Dependence-Like Logics
Logic in Computer Science
Summary
Some logical systems need values beyond just true and false to handle uncertainty or incomplete information. The authors studied ways to combine classical logic with a three-valued logic that includes an 'infectious' negation and implication, which means some truth values spread in specific ways. They designed two new logical systems following this idea and created a way to prove all statements in these systems correctly and efficiently without extra steps. This helps better understand how different logic types relate and can work together.
What this means in practice
- •For automated reasoning teams: Use the new proof systems to handle reasoning tasks involving uncertainty and variable dependencies in knowledge bases.
- •For logic-based software verification teams: Incorporate three-valued dependence-like logics to better model programs with uncertain or incomplete information during verification.
A theory result. No direct application yet.
Authors
Yaroslav Petrukhin
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.