Author's Note. This entry will develop a distinct approach to the material of propositional logic, focusing on parameterized families of concrete propositional calculi that are developed formally, with a higher degree of abstraction from their intended interpretations.

A propositional calculus is a formal system whose expressions represent formal objects known as propositions and whose elective relations among expressions represent existing relations among propositions. Many different propositional calculi represent what is recognizably the same subject matter of propositions and their relations, which more generic subject matter is conveniently described as propositional logic. For the purposes of mathematical discussion, and especially in computational applications, it is sufficient to identify a proposition with a boolean-valued function, that is, a mapping of the type , where is some set and .

As a general consideration, a calculus is a formal system that consists of a set of syntactic expressions, a distinguished subset of these expressions, plus a set of transformation rules that define a binary relation on the space of expressions.

When the expressions are interpreted for mathematical purposes, the transformation rules are typically intended to preserve some type of semantic equivalence relation among the expressions. In particular, when the expressions are intepreted as a logical system, the semantic equivalence is typically intended to be logical equivalence. In this setting, the transformation rules can be used to derive logically equivalent expressions from any given expression. These derivations include as special cases (1) the problem of simplifying expressions and (2) the problem of deciding whether a given expression is equivalent to an expression in the distinguished subset, typically interpreted as the subset of logical axioms.

The formal language component of a propositional calculus consists of (1) a set of primitive symbols, variously referred to as atomic formulas, placeholders, proposition letters, or variables, and (2) a set of operator symbols, variously interpreted as logical operators or logical connectives. A well-formed formula (wff) is any atomic formula or any formula that can be built up from atomic formulas by means of operator symbols.

The following outlines a standard propositional calculus. Many different formulations exist which are all more or less equivalent but differ in (1) their language, that is, the particular collection of primitive symbols and operator symbols, (2) the set of axioms, or distingushed formulas, and (3) the set of transformation rules that are available.

Contents

• Abstraction and application
• Generic description of a propositional calculus

Abstraction and application

Although it is possible to construct an abstract formal calculus that has no immediate practical use and next to nothing in the way of obvious applications, the very name calculus indicates that this species of formal system owes its origin to the utility of its prototypical members in practical calculation. Generally speaking, any mathematical calculus is designed with the intention of representing a given domain of formal objects, and typically with the aim of facilitating the computations and inferences that need to be carried out in this representation. Thus some idea of the intended denotation, the formal objects that the formulas of the calculus are intended to denote, is given in advance of developing the calculus itself.

Viewed over the course of its historical development, a formal calculus for any given subject matter normally arises through a process of gradual abstraction, stepwise refinement, and trial-and-error synthesis from the array of informal notational systems that inform prior use, each of which covers the object domain only in part or from a particular angle.

Generic description of a propositional calculus

A propositional calculus is a formal system , whose formulas are constructed in the following manner:

• The alpha set is a finite set of elements called proposition symbols or propositional variables. Syntactically speaking, these are the most basic elements of the formal language , otherwise referred to as atomic formulas or terminal elements. In the examples to follow the elements of are typically the letters , , , and so on.
• The omega set is a finite set of elements called operator symbols or logical connectives. The set is partitioned into disjoint subsets as follows:

  .

  In this partition, is the set of operator symbols of arity .

  In the more familiar propositional calculi, is typically partitioned as follows:

  ,

  .

  A frequently adopted option treats the constant logical values as operators of arity zero, thus:

  .

  Some writers use the tilde ( ) instead of and some use the ampersand (&) instead of . Notation varies even more for the set of logical values, with symbols like , , , and all being seen in various contexts.

• Depending on the precise formal grammar or the grammar formalism that is being used, syntactic auxiliaries like the left parenthesis, , and the right parentheses, , may be necessary to complete the construction of formulas.