Le calcul des propositions, version moderne de la logique stoïcienne, est une théorie formelle axiomatico-déductive, branche de la logique, visant à déterminer les lois de la déduction (ou dérivation) de propositions à partir d'autre propositions.
Le calcul des propositions est à la base de l'électronique numérique.

Table of contents

1 Nature des propositions 2 Les connecteurs logiques 2.1 Connecteurs unaires 2.2 Connecteurs binaires 2.3 Choix de connecteurs primitifs 3 Théorèmes du calcul propositionnel 4 Voir aussi

Nature des propositions

Il est difficile de donner une définition consensuelle du concept de "proposition". Dans une première approximation, on peut dire qu'il s'agit d'entités abstraites se référant à des états de chose ou des événements.

Les propositions au sens logique peuvent être exprimées par les énoncés du langage ordinaire, mais ne leur sont pas identiques. C'est ainsi que deux énoncés, tels que "il pleut" et "it's raining" correspondent à la même proposition, quoiqu'ils s'agissent de deux énoncés distincts.

D'un point de vue strictement formel, on peut se contenter de considérer comme proposition n'importe quelle entité, (voire, dans une interprétation radicale, n'importe quel symbole) qui satisfasse l'une ou l'autre axiomatique du calcul des propositions.

Comme la plupart des théories logico-mathématiques, il est possible de considérer le calcul des propositions d'un point de vue syntaxique ou sémantique.

Les connecteurs logiques

On se donne deux valeurs prises par les propositions : V et F.
Il existe des connecteurs unaires (qui n'opèrent que sur une proposition), binaires (sur 2), ternaires, etc.

Connecteurs unaires

Il existe quatre connecteurs unaires :

p	1	2	3	4
V	V	V	F	F
F	V	F	F	V

Le premier est la tautologie, le second est l'affirmation (ou l'identité), le troisième est la contradiction et le dernier est la négation, notée ¬.

Connecteurs binaires

Les connecteurs binaires sont tirés des connecteurs du langage courant : et, ou, etc. Voici la liste des seize existants :

p

q

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

V

V

V

V

V

V

V

V

V

V

F

F

F

F

F

F

F

F

V

F

V

V

V

V

F

F

F

F

V

V

V

V

F

F

F

F

F

V

V

V

F

F

V

V

F

F

V

V

F

F

V

V

F

F

F

F

V

F

V

F

V

F

V

F

V

F

V

F

V

F

V

F

1 est la tautologie, 16 la contradiction, 2 est la disjonction (le ou noté ∨), 15 est sa négation (le rejet, ou nor), 8 est la conjonction (le et noté ∧), le 9 est sa négation (l'incompatibilité, ou nand noté |) , 7 est l'équivalence (notée ≡) et 10 est sa négation (ou exclusif, noté w). 5 est l'implication (notée ⊃), 12 est sa négation, 3 est l'implication converse (notée ⊂) et 14 est sa négation. 4 et 6 conservent p et q respectivement, 13 et 11 sont leurs négations, elles n'ont pas de nom particulier.

Choix de connecteurs primitifs

On remarque que tous ces connecteurs peuvent se déduire d'un nombre plus restreint de connecteurs. Ainsi, Whitehead et Russell construisent leur logique sur le ou et la négation, Frege sur l'implication et la négation. On peut aussi utiliser l'incompatibilité (ou le rejet), mais les calculs deviennent vite lourds.

Théorèmes du calcul propositionnel

Pour ne pas surcharger les formules de parenthèses, en leur absence ∧ et ∨ sont plus prioritaires que ≡ et ⊃, qui seront donc lus en dernier.

A ∨ ¬A	principe du tiers exclu
¬(A ∧ ¬A)	loi de non-contradiction
¬(¬A) ≡ A	double négation
¬(A ∧ B) ≡ ¬A ∨ ¬B	lois de De Morgan
¬(A ∨ B) ≡ ¬A ∧ ¬B
(A ⊃ B) ⊃ (¬B ⊃ ¬A)	règle de contraposition
(A ⊃ B) ∧ A ⊃ B	règle du modus ponens
(A ⊃ B) ∧ ¬B ⊃ ¬A	règle du modus tollens
(A ⊃ B) ∧ (B ⊃ C) ⊃ (A ⊃ C)	règle du modus barbara
A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)	règles de distributivité
A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)

Voir aussi

Calcul des propositions standards et calculs non-standards

Calculs multivalents

Calculs des propostions avec opérateurs de modalités