Namespaces
Variants
Actions

Difference between revisions of "Propositional calculus(2)"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
p0754801.png
 +
$#A+1 = 37 n = 0
 +
$#C+1 = 37 : ~/encyclopedia/old_files/data/P075/P.0705480 Propositional calculus
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A [[Logical calculus|logical calculus]] in which the derivable objects are propositional formulas (cf. [[Propositional formula|Propositional formula]]). Every propositional calculus is given by a set of axioms (particular propositional formulas) and derivation rules (cf. [[Derivation rule|Derivation rule]]). A formula that is derivable in a given propositional calculus is called a theorem of this propositional calculus. One usually takes the rules of [[Modus ponens|modus ponens]] and substitution (of arbitrary propositional formulas for variables) as the derivation rules. Sometimes a propositional calculus is given not by axioms, but by axiom schemes (cf. [[Axiom scheme|Axiom scheme]]). The rule of substitution then becomes superfluous.
 
A [[Logical calculus|logical calculus]] in which the derivable objects are propositional formulas (cf. [[Propositional formula|Propositional formula]]). Every propositional calculus is given by a set of axioms (particular propositional formulas) and derivation rules (cf. [[Derivation rule|Derivation rule]]). A formula that is derivable in a given propositional calculus is called a theorem of this propositional calculus. One usually takes the rules of [[Modus ponens|modus ponens]] and substitution (of arbitrary propositional formulas for variables) as the derivation rules. Sometimes a propositional calculus is given not by axioms, but by axiom schemes (cf. [[Axiom scheme|Axiom scheme]]). The rule of substitution then becomes superfluous.
  
 
The classical propositional calculus is given by the following axioms:
 
The classical propositional calculus is given by the following axioms:
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754801.png" />;
+
1) p \supset  ( q \supset p ) $;
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754802.png" />;
+
2) $  ( p \supset ( q \supset r ) )  \supset  ( ( p \supset q ) \supset ( p \supset r ) ) $;
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754803.png" />;
+
3) $  ( p \& q )  \supset  p $;
  
4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754804.png" />;
+
4) $  ( p \& q )  \supset  q $;
  
5) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754805.png" />;
+
5) p \supset  ( q \supset ( p \& q ) ) $;
  
6) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754806.png" />;
+
6) p \supset  ( p \lor q ) $;
  
7) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754807.png" />;
+
7) $  q  \supset  ( p \lor q ) $;
  
8) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754808.png" />;
+
8) $  ( p \supset r )  \supset  ( ( q \supset r ) \supset ( ( p \lor q ) \supset r ) ) $;
  
9) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p0754809.png" />;
+
9) $  ( p \supset q )  \supset  ( ( p \supset \neg q ) \supset \neg p ) $;
  
10) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548010.png" />.
+
10) $  \neg \neg p \supset  p $.
  
In this propositional calculus the propositional connectives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548011.png" /> (cf. [[Propositional connective|Propositional connective]]) are not independent. It can also be given by 1), 2), 9), and 10), taking the connectives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548012.png" /> as primitive ones. The connectives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548014.png" /> are then abbreviations:
+
In this propositional calculus the propositional connectives $  \& , \lor , \supset , \neg $(
 +
cf. [[Propositional connective|Propositional connective]]) are not independent. It can also be given by 1), 2), 9), and 10), taking the connectives $  \supset , \neg $
 +
as primitive ones. The connectives $  \& $
 +
and $  \lor $
 +
are then abbreviations:
  
<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/p075480/p07548015.png" /></td> </tr></table>
+
$$
 +
A \& B  \iff  \neg ( A \supset \neg B ) ,\ \
 +
A \lor B  \iff  \neg A \supset B ,
 +
$$
  
 
while 3)–8) become theorems. The classical propositional calculus is also called the complete propositional calculus, since the addition of any formula not derivable in it as a further axiom leads to a contradictory propositional calculus, i.e. one in which all propositional formulas are derivable. The classical propositional calculus is often simply called propositional calculus.
 
while 3)–8) become theorems. The classical propositional calculus is also called the complete propositional calculus, since the addition of any formula not derivable in it as a further axiom leads to a contradictory propositional calculus, i.e. one in which all propositional formulas are derivable. The classical propositional calculus is often simply called propositional calculus.
Line 31: Line 50:
 
The intuitionistic (constructive) propositional calculus can be obtained from the classical propositional calculus by replacing 10) by the weaker axiom
 
The intuitionistic (constructive) propositional calculus can be obtained from the classical propositional calculus by replacing 10) by the weaker axiom
  
11) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548016.png" />.
+
11) $  \neg p \supset  ( p \supset q ) $.
  
 
A propositional calculus that is obtained from the intuitionistic propositional calculus by the addition of a finite (or recursive) set of axioms is called intermediate, superintuitionistic or superconstructive. See also [[Intermediate logic|Intermediate logic]].
 
A propositional calculus that is obtained from the intuitionistic propositional calculus by the addition of a finite (or recursive) set of axioms is called intermediate, superintuitionistic or superconstructive. See also [[Intermediate logic|Intermediate logic]].
Line 39: Line 58:
 
An interpretation of a propositional calculus is given by an algebra (matrix) of the form
 
An interpretation of a propositional calculus is given by an algebra (matrix) of the form
  
<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/p075480/p07548017.png" /></td> </tr></table>
+
$$
 +
\mathfrak M  = < M , D ; \&  ^ {*} ,\
 +
\lor  ^ {*} , \supset  ^ {*} , \neg  ^ {*} > .
 +
$$
  
Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548018.png" /> is the set of truth values (cf. [[Truth value|Truth value]]), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548019.png" /> is the set of distinguished truth values, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548020.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548021.png" /> are the operations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548022.png" /> corresponding to the connectives <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548023.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548024.png" /> must satisfy the following condition: For any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548025.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548027.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548028.png" /> (compatibility with the rule of modus ponens). A formula is said to be universally valid on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548029.png" /> if it takes values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548030.png" /> for every interpretation of its variables as elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548031.png" />. The simplest matrix is the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548032.png" />, consisting of two elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548034.png" /> ( "false" ,  "true" ) and the single distinguished value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548035.png" />; the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548036.png" /> are defined in the usual way (cf. [[Algebra of logic|Algebra of logic]]). A propositional formula that is universally valid on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p075/p075480/p07548037.png" /> is called a tautology. A formula is a tautology if and only if it is a theorem of the classical propositional calculus.
+
Here $  M $
 +
is the set of truth values (cf. [[Truth value|Truth value]]), $  D $
 +
is the set of distinguished truth values, $  D \subset  M $,  
 +
and $  \&  ^ {*} , \lor  ^ {*} , \supset  ^ {*} , \neg  ^ {*} $
 +
are the operations on $  M $
 +
corresponding to the connectives $  \& , \lor , \supset , \neg $.  
 +
The set $  D $
 +
must satisfy the following condition: For any $  a , b \in D $,  
 +
if $  a \in D $
 +
and $  ( a \supset  ^ {*} b ) \in D $,  
 +
then $  b \in D $(
 +
compatibility with the rule of modus ponens). A formula is said to be universally valid on $  \mathfrak M $
 +
if it takes values in $  D $
 +
for every interpretation of its variables as elements of $  M $.  
 +
The simplest matrix is the matrix $  \mathfrak M _ {2} $,  
 +
consisting of two elements 0 $
 +
and $  1 $(  
 +
"false" ,  "true" ) and the single distinguished value $  1 $;  
 +
the operations $  \&  ^ {*} , \lor  ^ {*} , \supset  ^ {*} , \neg  ^ {*} $
 +
are defined in the usual way (cf. [[Algebra of logic|Algebra of logic]]). A propositional formula that is universally valid on $  \mathfrak M _ {2} $
 +
is called a tautology. A formula is a tautology if and only if it is a theorem of the classical propositional calculus.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A. Church,  "Introduction to mathematical logic" , '''1''' , Princeton Univ. Press  (1956)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A. Church,  "Introduction to mathematical logic" , '''1''' , Princeton Univ. Press  (1956)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 08:08, 6 June 2020


A logical calculus in which the derivable objects are propositional formulas (cf. Propositional formula). Every propositional calculus is given by a set of axioms (particular propositional formulas) and derivation rules (cf. Derivation rule). A formula that is derivable in a given propositional calculus is called a theorem of this propositional calculus. One usually takes the rules of modus ponens and substitution (of arbitrary propositional formulas for variables) as the derivation rules. Sometimes a propositional calculus is given not by axioms, but by axiom schemes (cf. Axiom scheme). The rule of substitution then becomes superfluous.

The classical propositional calculus is given by the following axioms:

1) $ p \supset ( q \supset p ) $;

2) $ ( p \supset ( q \supset r ) ) \supset ( ( p \supset q ) \supset ( p \supset r ) ) $;

3) $ ( p \& q ) \supset p $;

4) $ ( p \& q ) \supset q $;

5) $ p \supset ( q \supset ( p \& q ) ) $;

6) $ p \supset ( p \lor q ) $;

7) $ q \supset ( p \lor q ) $;

8) $ ( p \supset r ) \supset ( ( q \supset r ) \supset ( ( p \lor q ) \supset r ) ) $;

9) $ ( p \supset q ) \supset ( ( p \supset \neg q ) \supset \neg p ) $;

10) $ \neg \neg p \supset p $.

In this propositional calculus the propositional connectives $ \& , \lor , \supset , \neg $( cf. Propositional connective) are not independent. It can also be given by 1), 2), 9), and 10), taking the connectives $ \supset , \neg $ as primitive ones. The connectives $ \& $ and $ \lor $ are then abbreviations:

$$ A \& B \iff \neg ( A \supset \neg B ) ,\ \ A \lor B \iff \neg A \supset B , $$

while 3)–8) become theorems. The classical propositional calculus is also called the complete propositional calculus, since the addition of any formula not derivable in it as a further axiom leads to a contradictory propositional calculus, i.e. one in which all propositional formulas are derivable. The classical propositional calculus is often simply called propositional calculus.

The intuitionistic (constructive) propositional calculus can be obtained from the classical propositional calculus by replacing 10) by the weaker axiom

11) $ \neg p \supset ( p \supset q ) $.

A propositional calculus that is obtained from the intuitionistic propositional calculus by the addition of a finite (or recursive) set of axioms is called intermediate, superintuitionistic or superconstructive. See also Intermediate logic.

Other examples of propositional calculi are: the implicative propositional calculus; the minimal propositional calculus; and the positive propositional calculus.

An interpretation of a propositional calculus is given by an algebra (matrix) of the form

$$ \mathfrak M = < M , D ; \& ^ {*} ,\ \lor ^ {*} , \supset ^ {*} , \neg ^ {*} > . $$

Here $ M $ is the set of truth values (cf. Truth value), $ D $ is the set of distinguished truth values, $ D \subset M $, and $ \& ^ {*} , \lor ^ {*} , \supset ^ {*} , \neg ^ {*} $ are the operations on $ M $ corresponding to the connectives $ \& , \lor , \supset , \neg $. The set $ D $ must satisfy the following condition: For any $ a , b \in D $, if $ a \in D $ and $ ( a \supset ^ {*} b ) \in D $, then $ b \in D $( compatibility with the rule of modus ponens). A formula is said to be universally valid on $ \mathfrak M $ if it takes values in $ D $ for every interpretation of its variables as elements of $ M $. The simplest matrix is the matrix $ \mathfrak M _ {2} $, consisting of two elements $ 0 $ and $ 1 $( "false" , "true" ) and the single distinguished value $ 1 $; the operations $ \& ^ {*} , \lor ^ {*} , \supset ^ {*} , \neg ^ {*} $ are defined in the usual way (cf. Algebra of logic). A propositional formula that is universally valid on $ \mathfrak M _ {2} $ is called a tautology. A formula is a tautology if and only if it is a theorem of the classical propositional calculus.

References

[1] A. Church, "Introduction to mathematical logic" , 1 , Princeton Univ. Press (1956)

Comments

Sometimes the propositional calculus is also called the sentential calculus, [a3].

References

[a1] J.L. Bell, M. Machover, "A course in mathematical logic" , North-Holland (1977)
[a2] R. Wójcicki, "Theory of logical calculi" , Kluwer (1988)
[a3] A. Tarski, "Introduction to logic and to the methodology of deductive sciences" , Oxford Univ. Press (1946)
[a4] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1959) pp. Chapts. IX; XI, §54
[a5] P.F. Strawson, "Introduction to logical theory" , Methuen (1952)
How to Cite This Entry:
Propositional calculus(2). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Propositional_calculus(2)&oldid=16031
This article was adapted from an original article by S.K. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article