Namespaces
Variants
Actions

Difference between revisions of "Propositional connective"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
A symbol in a [[Formal language|formal language]] used for denoting a [[Logical operation|logical operation]] by means of which a new statement can be obtained from given statements. The most important propositional connectives are: the conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754901.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754902.png" />), the disjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754903.png" />, the implication <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754904.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754905.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754906.png" />), the negation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754907.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754908.png" />), and equivalence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p0754909.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549010.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549011.png" />). 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|Sheffer stroke]].
+
{{TEX|done}}
 +
A symbol in a [[Formal language|formal language]] used for denoting a [[Logical operation|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|Sheffer stroke]].
  
The symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549012.png" /> is usually not introduced as an independent propositional connective, but as an abbreviation:
+
The symbol $\equiv$ is usually not introduced as an independent propositional connective, but as an abbreviation:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$A\equiv B\Leftrightarrow((A\supset B)\&(B\supset A)).\tag{1}$$
  
If a language contains the propositional constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549014.png" />, denoting  "untruth" , then negation can be regarded as an abbreviation: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549015.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549016.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549017.png" /> are not independent in classical logic, since the following equivalences hold:
+
The propositional connectives $\&,\lor,\supset$, and $\neg$ are not independent in classical logic, since the following equivalences hold:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$A\&B\equiv\neg(\neg A\lor\neg B)\equiv\neg(A\supset\neg B),\tag{2}$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$A\lor B\equiv\neg(\neg A\&\neg B)\equiv(\neg A\supset B)\equiv((A\supset B)\supset B),\tag{3}$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$A\supset B\equiv(\neg A\lor B)\equiv\neg(A\&\neg B).\tag{4}$$
  
Thus, each of the propositional connectives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549021.png" /> can be expressed in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549022.png" /> and one of the others. Therefore, in formulating the classical [[Propositional calculus|propositional calculus]] of expressions, one can choose two propositional connectives as primitive: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549023.png" /> and one of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549024.png" />; the others are regarded as abbreviations, according to (1)–(4). In intuitionistic logic, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549025.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075490/p07549026.png" /> are independent.
+
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|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.
  
  

Revision as of 18:17, 22 September 2014

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)\&(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\&B\equiv\neg(\neg A\lor\neg B)\equiv\neg(A\supset\neg B),\tag{2}$$

$$A\lor B\equiv\neg(\neg A\&\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\&\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.


Comments

References

[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: http://encyclopediaofmath.org/index.php?title=Propositional_connective&oldid=33362
This article was adapted from an original article by S.K. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article