Propositional connective

From Encyclopedia of Mathematics
Jump to: navigation, search

A symbol in a formal language used for denoting a logical operation by means of which a new statement can be obtained from given statements. The most important propositional connectives are: the conjunction $\&$ (or $\land$), the disjunction $\lor$, the implication $\supset$ (or $\to$, or $\Rightarrow$), the negation $\neg$ (or $\sim$), and equivalence $\equiv$ (or $\leftrightarrow$, or $\Leftrightarrow$). These propositional connectives correspond in the English language to the expressions "and", "or", "implies", "it is not true that", and "is equivalent with". Sometimes one considers other propositional connectives; for example, the Sheffer stroke.

The symbol $\equiv$ is usually not introduced as an independent propositional connective, but as an abbreviation:

$$A\equiv B\Leftrightarrow((A\supset B)\mathbin{\&}(B\supset A)).\tag{1}$$

If a language contains the propositional constant $\bot$, denoting "untruth", then negation can be regarded as an abbreviation: $\neg A\Leftrightarrow(A\supset\bot)$.

The propositional connectives $\&,\lor,\supset$, and $\neg$ are not independent in classical logic, since the following equivalences hold:

$$A\mathbin{\&}B\equiv\neg(\neg A\lor\neg B)\equiv\neg(A\supset\neg B),\tag{2}$$

$$A\lor B\equiv\neg(\neg A\mathbin{\&}\neg B)\equiv(\neg A\supset B)\equiv((A\supset B)\supset B),\tag{3}$$

$$A\supset B\equiv(\neg A\lor B)\equiv\neg(A\mathbin{\&}\neg B).\tag{4}$$

Thus, each of the propositional connectives $\&,\lor,\supset$ can be expressed in terms of $\neg$ and one of the others. Therefore, in formulating the classical propositional calculus of expressions, one can choose two propositional connectives as primitive: $\neg$ and one of $\&,\lor,\supset$; the others are regarded as abbreviations, according to (1)–(4). In intuitionistic logic, $\&,\lor\supset$, and $\neg$ are independent.



[a1] J.L. Bell, M. Machover, "A course in mathematical logic" , North-Holland (1977)
How to Cite This Entry:
Propositional connective. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by S.K. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article