You are here
Homepropositional calculus
Primary tabs
propositional calculus
A propositional calculus is a formal system whose expressions represent formal objects known as propositions and whose distinguished 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 booleanvalued function, that is, a mapping of the type $X\to\mathbb{B}$, where $X$ is some set and $\mathbb{B}=\{0,1\}$.
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 wellformed 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:
 1 Abstraction and application
 2 Generic description of a propositional calculus
 3 Example 1. Simple axiom system
 4 Example 2. Natural deduction system
 5 Document history
1 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 trialanderror 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.
2 Generic description of a propositional calculus
A propositional calculus is a formal system $\mathcal{L}=\mathcal{L}(A,\Omega,Z,I)$, whose formulas are constructed in the following manner:

The alpha set $A$ is a finite set of elements called proposition symbols or propositional variables. Syntactically speaking, these are the most basic elements of the formal language $\mathcal{L}$, otherwise referred to as atomic formulas or terminal elements. In the examples to follow the elements of $A$ are typically the letters $p$, $q$, $r$, and so on.

The omega set $\Omega$ is a finite set of elements called operator symbols or logical connectives. The set $\Omega$ is partitioned into disjoint subsets as follows:
$\Omega=\bigcup_{{j=0}}^{m}\Omega_{j}$.
In the more familiar propositional calculi, $\Omega$ is typically partitioned as follows:
$\Omega_{1}=\{\lnot\}$,
$\Omega_{2}\subseteq\{\land,\lor,\Rightarrow,\Leftrightarrow\}$.$\Omega_{0}=\{0,\ 1\}$.
Some writers use the tilde $(\text{\char 126})$ instead of $(\lnot)$ and some use the ampersand $(\&)$ instead of $(\land)$. Notation varies even more for the set of logical values, with symbols like $\{\mathrm{false},\mathrm{true}\}$, $\{\mathrm{F},\mathrm{T}\}$, $\{0,1\}$, and $\{\bot,\top\}$ all being seen in various contexts.

The zeta set $Z$ is a finite set of transformation rules that are called inference rules when they acquire logical applications.

The iota set $I$ is a finite set of initial points that are called axioms when they receive logical interpretations.
3 Example 1. Simple axiom system
Let $\mathcal{L}_{1}=\mathcal{L}(A,\Omega,Z,I)$, where $A,\Omega,Z,I$ are defined as follows:
The alpha set $A$ is a finite set of symbols that is large enough to supply the needs of a given discussion, for example:
$A=\{p,q,r,s,t,u\}$.
The omega set $\Omega$ is a set of two symbols $\{\lnot\ ,\Rightarrow\}$ that partitions as follows:
$\Omega_{1}=\{\lnot\}$,
$\Omega_{2}=\{\Rightarrow\}$.
Under the usual interpretation of these symbols, this choice amounts to adopting negation and implication as the primitive operations of the propositional calculus $\mathcal{L}_{1}$.
Of the three connectives for conjunction $(\land)$, disjunction $(\lor)$, and implication $(\Rightarrow)$, one can be taken as primitive and the other two can be defined in terms of it and negation $(\lnot)$. The equivalence $(\Leftrightarrow)$ is defined in terms of conjunction and implication, with $p\Leftrightarrow q$ defined as $(p\Rightarrow q)\land(q\Rightarrow p)$.
The zeta set $Z$ formalizes the inference rule known as modus ponens:
From $p$, $(p\Rightarrow q)$, infer $q$.
The iota set $I$ abstracts an axiom system for propositional logic that was discovered by Jan Łukasiewicz:
$p\Rightarrow(q\Rightarrow p)$
$(p\Rightarrow(q\Rightarrow r))\Rightarrow((p\Rightarrow q)\Rightarrow(p% \Rightarrow r))$
$(\lnot p\Rightarrow\lnot q)\Rightarrow(q\Rightarrow p)$
We have the following auxiliary definitions:
$p\lor q\ :=\ \lnot p\Rightarrow q$.
$p\land q\ :=\ \lnot(p\Rightarrow\lnot q)$.
4 Example 2. Natural deduction system
Let $\mathcal{L}_{2}=\mathcal{L}(A,\Omega,Z,I)$, where $A,\Omega,Z,I$ are defined as follows:
The alpha set $A$ is a finite set of symbols that is large enough to supply the needs of a given discussion, for example:
$A=\{p,q,r,s,t,u\}$.
The omega set $\Omega=\Omega_{1}\cup\Omega_{2}$ partitions as follows:
$\Omega_{1}=\{\lnot\}$,
$\Omega_{2}=\{\land,\lor,\Rightarrow,\Leftrightarrow\}$.
In the following example of a propositional calculus, the transformation rules are intended to be interpreted as the inference rules of a socalled natural deduction system. The particular system presented here has no initial points, which means that its interpretation for logical applications derives its theorems from an empty axiom set.
To be continued $\ldots$
5 Document history
Mathematics Subject Classification
03F03 no label found03C05 no label found03B22 no label found03B05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections