Interleaving Logic and Counting

• URL: http://arxiv.org/abs/2507.05219v1
• Date: Mon, 07 Jul 2025 17:30:29 GMT
• Title: Interleaving Logic and Counting
• Authors: Johan van Benthem, Thomas Icard,
• Abstract summary: Reasoning with quantifier expressions in natural language combines logical and arithmetical features.<n>Our topic is this cooperation of styles as it occurs in common linguistic usage.
• Score: 5.71869130799784
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reasoning with quantifier expressions in natural language combines logical and arithmetical features, transcending strict divides between qualitative and quantitative. Our topic is this cooperation of styles as it occurs in common linguistic usage and its extension into the broader practice of natural language plus "grassroots mathematics". We begin with a brief review of first-order logic with counting operators and cardinality comparisons. This system is known to be of high complexity, and drowns out finer aspects of the combination of logic and counting. We move to a small fragment that can represent numerical syllogisms and basic reasoning about comparative size: monadic first-order logic with counting. We provide normal forms that allow for axiomatization, determine which arithmetical notions can be defined on finite and on infinite models, and conversely, we discuss which logical notions can be defined out of purely arithmetical ones, and what sort of (non-)classical logics can be induced. Next, we investigate a series of strengthenings, again using normal form methods. The monadic second-order version is close, in a precise sense, to additive Presburger Arithmetic, while versions with the natural device of tuple counting take us to Diophantine equations, making the logic undecidable. We also define a system that combines basic modal logic over binary accessibility relations with counting, needed to formulate ubiquitous reasoning patterns such as the Pigeonhole Principle. We return to our starting point in natural language, confronting the architecture of our formal systems with linguistic quantifier vocabulary and syntax. We conclude with some general thoughts on yet further entanglements of logic and counting in formal systems, on rethinking the qualitative/quantitative divide, and on connecting our analysis to empirical findings in cognitive science.

Related papers

• Logic-Based Artificial Intelligence Algorithms Supporting Categorical Semantics [0.0]
  We develop forward chaining and normal form algorithms for reasoning about objects in cartesian categories with the rules for Horn logic.<n>We also adapt first-order unification to support multi-sorted theories, contexts, and fragments of first-order logic.
  arXiv  Detail & Related papers  (2025-04-27T18:02:02Z)
• A Complexity-Based Theory of Compositionality [53.025566128892066]
  In AI, compositional representations can enable a powerful form of out-of-distribution generalization.<n>Here, we propose a definition, which we call representational compositionality, that accounts for and extends our intuitions about compositionality.<n>We show how it unifies disparate intuitions from across the literature in both AI and cognitive science.
  arXiv  Detail & Related papers  (2024-10-18T18:37:27Z)
• Empower Nested Boolean Logic via Self-Supervised Curriculum Learning [67.46052028752327]
  We find that any pre-trained language models even including large language models only behave like a random selector in the face of multi-nested logic. To empower language models with this fundamental capability, this paper proposes a new self-supervised learning method textitCurriculum Logical Reasoning (textscClr)
  arXiv  Detail & Related papers  (2023-10-09T06:54:02Z)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  Passage-level logical relations represent entailment or contradiction between propositional units (e.g., a concluding sentence) We propose logic structural-constraint modeling to solve the logical reasoning QA and introduce discourse-aware graph networks (DAGNs) The networks first construct logic graphs leveraging in-line discourse connectives and generic logic theories, then learn logic representations by end-to-end evolving the logic relations with an edge-reasoning mechanism and updating the graph features.
  arXiv  Detail & Related papers  (2022-07-04T14:38:49Z)
• Transfinite Modal Logic: a Semi-quantitative Explanation for Bayesian Reasoning [1.6916260027701393]
  We introduce transfinite modal logic, which combines modal logic with ordinal arithmetic. We suggest that transfinite modal logic captures the essence of Bayesian reasoning in a rather clear and simple form.
  arXiv  Detail & Related papers  (2022-04-02T17:58:14Z)
• Learning Symbolic Rules for Reasoning in Quasi-Natural Language [74.96601852906328]
  We build a rule-based system that can reason with natural language input but without the manual construction of rules. We propose MetaQNL, a "Quasi-Natural" language that can express both formal logic and natural language sentences. Our approach achieves state-of-the-art accuracy on multiple reasoning benchmarks.
  arXiv  Detail & Related papers  (2021-11-23T17:49:00Z)
• On syntactically similar logic programs and sequential decompositions [0.0]
  Rule-based reasoning is an essential part of human intelligence prominently formalized in artificial intelligence research via logic programs. Describing complex objects as the composition of elementary ones is a common strategy in computer science and science in general. We show how similarity can be used to answer queries across different domains via a one-step reduction.
  arXiv  Detail & Related papers  (2021-09-11T15:22:17Z)
• Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
  We give a sound and strongly complete axiomatization that can be parametrized to cover essentially every real-valued logic. Our class of sentences are very rich, and each describes a set of possible real values for a collection of formulas of the real-valued logic.
  arXiv  Detail & Related papers  (2020-08-06T02:13:11Z)
• Higher-order Logic as Lingua Franca -- Integrating Argumentative Discourse and Deep Logical Analysis [0.0]
  We present an approach towards the deep, pluralistic logical analysis of argumentative discourse. We use state-of-the-art automated reasoning technology for classical higher-order logic.
  arXiv  Detail & Related papers  (2020-07-02T11:07:53Z)
• Logical Neural Networks [51.46602187496816]
  We propose a novel framework seamlessly providing key properties of both neural nets (learning) and symbolic logic (knowledge and reasoning) Every neuron has a meaning as a component of a formula in a weighted real-valued logic, yielding a highly intepretable disentangled representation. Inference is omni rather than focused on predefined target variables, and corresponds to logical reasoning.
  arXiv  Detail & Related papers  (2020-06-23T16:55:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.