Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T13:40:06.170Z Has data issue: false hasContentIssue false

What is an inference rule?

Published online by Cambridge University Press:  12 March 2014

Ronald Fagin
Affiliation:
IBM Almaden Research Center, San Jose, California 95120-6099, E-mail: fagin@almaden.ibm.com
Joseph Y. Halpern
Affiliation:
IBM Almaden Research Center, San Jose, California 95120-6099, E-mail: halpern@almaden.ibm.com
Moshe Y. Vardi
Affiliation:
IBM Almaden Research Center, San Jose, California 95120-6099, E-mail: vardi@almaden.ibm.com

Abstract

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference (σ ⊦vφ for every substitution τ, the validity of τ[σ] entails the validity of τ[φ]), and truth inference (σ⊦l φ if for every substitution τ, the truth of τ[σ] entails the truth of τ[φ]). In this paper we introduce a general semantic framework that allows us to investigate the notion of inference more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable