I- Qu'est-ce qu' une proposition

A) Définition

Commençons par définir ce qu' est une expression mathématique. Une expression mathématique est un assemblage de notions premières posées à priori et de notions dérivées, ayant un sens. Comme certaines associations ne sont pas " permises ", il faut que cette expression soit validée par la théorie mathématique.

ex: on ne pourra écrire AÎA, c' est un non-sens, il faudrait écrire AÎ{A} pour que ce soit une expression mathématique.

Une proposition est une expression mathématique à laquelle on peut accorder de façon certaine une valeur " vraie " ou la valeur " fausse ". Sans vouloir philosopher sur le sens de la vérité mathématique, on pourra dire seulement que c' est un des vestiges de l' empirisme cartésien dans les mathématiques.

ex: Reprenons le même exemple que précédemment. Supposons que{A} = {5}. Alors AÎ{A} est une proposition vraie.

" 8 est un nombre premier " est une proposition fausse

" Je pense qu' il pleuvra demain " n' est pas une proposition ( du moins au moment où je le dis )

B) Eléments sur les propositions

1) Propositions particulières

- axiome: proposition à laquelle on accorde par convention la valeur vraie. Ce n'est pas à proprement parler une proposition indémontrable.

- théorème: proposition dont on peut démontrer qu' elle est vraie

- conjecture: expression mathématique dont on pense qu' elle est une proposition vraie

ex: conjecture de Riemann sur la répartition des nombres premiers

Les propositions n' appartiennent pas à un ensemble mais à une collection, notée usuellement C.

2) Table de valeur ( ou de vérité )

Soit l' ensemble V = { 0 ; 1 } = { F ; V }. Pour toute proposittionde C, il existe une application de C dans V, dont les éléments sont des valeurs de vérités. Si p est vraie, h(p) = 1 = V, sinon h(p) = 0 = F.

Gouvent, on représente ces résultats par un tableau:

p

1

0

Pour deux propositions quelconques p et q, il existe d' après la table de valeurs ci-desssous 2² choix d' attribution de valeurs de vérité.

p	q
1	1
1	0
0	1
0	0

3) Propositions synonymes ( ou logiquement équivalentes )

Pour des éléments plus détaillés cf. article sur les équivalences logiques ( lien hypertexte )

Deux propositions sont dites logiquement équivalentes si elles ont même valeur de vérité. Le sens et le contenu de ces propositions ainsi que leur complexité ne sont donc pas concernés par l' équivalence logique

On note: p q

4) Négation d' une proposition

La négation est un opérateur sur la collection des propositions, qui à toute proposition p, associe la proposition négation de p, vraie si p est fausse, fausse si p est vraie.

On note non-p ou p ou p. En notation polonaise ( utilisé par exemple par les calculatirces HP ), on écrira Np.

Si on écrit la table de valeurs pour p et non-p, en les notant comme deux propositions différentes, on obtient:

p	p
1	1
1	0
0	1
0	0

Ceci contitue deux axiomes de la théorie:

- principe de non-contradiction: p et non-p ne peuvent être simultanément vraies

- principe du tiers exclu: l' une des deux propositions p et non-p est vraie

Remarque: ces axiomes ont des fondements empiriques qui remontent à une logique ancestrale, mais ils sont aujourd' hui invérifiés par certains systèmes expérimentaux, notamment en mécanique quantique. C' est pourquoi certains mathématiciens ont inventé des systèmes extrêmement complexes ( car devant aussi concorder avec la logique telle que tout un chacun la ressent ) tentant de modéliser des systèmes " illogiques ", où p et non-p sont vraies par exemple.

II- Connecteurs

A) Connecteurs logiques

Nous ne considérons que la valeur de vérité de deux propositions. Ainsi, à partir de deux propositions quelconques p et q, on peut déterminer une nouvelle proposition p q q, en cherchant la valeur de vérité de p q q en fonction des valeurs de p et q. Le symbole q est appelé un connecteur logique.

Puisque, pour le couple quelconque ( p , q ), il existe quatre cas possibles ( cf. I-A2 ), il suffit de fixer la suite des quatre valeurs correspondants de p q q pour fixer exactement le sens logique du connecteur correspondant.

p	q	p q q
1	1	?
1	0	?
0	1	?
0	0	?

Cette suite de 4 valeurs est appelé évaluation de p q q.

Pour la détermination de p q q, il y a 2⁴ évaluations, donc, en partant de deux propositions p et q quelconques, il existe 16 connecteurs possibles.

B) Connecteurs usuels

On résumera en fin de paragraphe l' évaluation logique des 16 connecteurs dans un tableau.

1) Conjonction

La conjonction est le conneteur logique et, qui, à tout couple de propositions (p,q) associe la proposition (p et q), vraie si p et q le sont, fausse dans tous les autres cas. Son évaluation est 1000. On la note et, , .

La proposition composée, appelée conjonction de p, q, est notée: p et q, pq, p.q ou en notation polonaise: Kpq.

2) Disjontion inclusive

La disjontion est le conneteur logique et, qui, à tout couple de propositions (p,q) associe la proposition (p ou q), vraie si l' une au moins des propositions p et q est vraie, fausse si p et q le sont. Son évaluation est 1110. On la note ou, , .

La proposition composée, appelée disjonction de p, q, est notée: p et q, pq ou en notation polonaise: Apq.

3) Implication

L' implication est le connecteur logique qui, à tout couple de propositions (p,q) associe la proposition (p implication q), fausse dans le cas où p est vraie et q fausse, vraie dans les autres cas. Son évaluation est 1011. On la note Þ

La proposition composée, appelée aussi une inmplication, est notée p Þ q, ou en notation polonaise: Cpq.

Remarque:

* il est important de noter que dans l' implication logique, il n' y a aucune idée de cause à effet entre p et q

* L' usage répandu en mathématiques est de n' écrire que des propositions vraies. Ainsi pÞq siginifie: p implication q est vraie. Cet usage est aussi fréquent en programmation, notamment en C et C++, lorsqu' on écrit par exemple: si x, alors x++ au lieu de si x<>0, alors x++. _.

* A la proposition implicative (1) : p Þ q, on associe deux autres implications:

- l' implication q Þ p est la réciproque de (1)

- l' implication p Þ q est la contraposée de (1)

Exemple d' application; soit un quadrilatère ABCD. Si ABCD est un rectangle, alors AB=CD!!! Mais si ABCD n' est pas un rectangle, AB peut très bien être égal ou n' être pas égalà CD.

4) Bi-implication

La bi-implication est le connecteur logique qui, à tout couple de propositions (p,q), associe la proposition (p bi-implication q), vraie si p et q ont même valeur de vérité, fuasse dans les autres cas. Son évaluation est 1001. On la note Û.

La proposition composée est notée p Û q ou en notation polonaise: Epq.

5) Compléments et résumé

Donnons les noms de quelques connecteurs peu utilisés avec leur évaluation:

- disjonction exclusive: p w q: 0110

- barre de Sheffer: p q: 0111

- tautologie: p t q: 1111. on note le résultat V

- antilogie: p a q: 0000: on note le résultat F

C) Propositions complexes

1) Définition

A partir de propositions p et q, considérées comme simples, les connecteurs permettent de construire de nouvelles propositions p q q, ( ou P ), que nous disons complexes.

Notations

- on convient que l' opérateur Ø porte sur la proposition simple qui suit immédiatement

- lorsque cela est obligatoire, on emploit des parenthèses autour des propositions simples

2) Propositions complexes logiquement équivalentes

Deux propositions complexes P, Q sont équivalentes si elles ont même évaluation.

D) Propriétés des connecteurs

Toutes ces propriétés sont démontrables de façon immédiate en construisant leurs tables de valeurs.

1) Propriétés fondamentales d' un connecteur

Nous n' allons pas donner toutes les propriétés de chaque connecteur. Au contraire, pour chaque propriété, nous exhiberons un exemple. Ces propriétés sont valables pour tout triplet de propositions p,q et r. On appelle q le connecteur logique vérifiant les propiétés suivantes.

- q involutif; q o q = Id_C : ex: négation : ( p ) p

- q idempotent; p q p p: ex: conjonction : p p p

- q commutatif; p q q q q p: ex: barre de Sheffer ­: p ­ q q ­ p

- q associatif; ( p q q ) q r p q ( q q r ): ex: conjonction : ( p q ) r p ( q r )

Si q est associatif, on peut alors omettre les parenthèses

- V est neutre pour q; p q V p : ex: bi-implication Û: p ÛV p

- F est absorbant pour q; p q F F : ex: conjonction : p V p

2) Propriétés spécifiques des connecteurs usuels

- p ( p ) F : principe de non-contradiction

- p ( p ) V : principe du tiers-exclu

- p Þ p V: tautologie

3) Lois de Morgan

- Ø ( p Ù q ) º ( Ø p ) Ú ( Ø q )

- Ø ( p Ú q ) º ( Ø p ) Ù ( Ø q )

Définition: pour toute proposition complexe P, exprimée à l' aide de Ù et Ú, on appelle forme duale de P la proposition obtenue en remplaçant dans P, Ù par Ú, Ú par Ù, V par F, F par V.

4) Propriétés mixtes ( on ne les étudiera que sur les connecteurs usuels )

* Pour toutes propositions p, q, r

- p Ù ( q Ú r ) ( p Ù q ) Ú ( p Ù r )

- p Ú ( q Ù r ) ( p Ú q ) Ù ( p Ú r )

c' est-à-dire que chacun des connecteurs est distributif sur l' autre

* Pour toutes propositions p, q, on obtient les propriétés suivantes, appelées lois d' absorption

- p Ù ( p Ú q ) p

- p Ú ( p Ù q ) p

* Pour toutes propositions p, q, r

( [ ( p Þ q ) Ù ( q Þ r ) ] Þ ( p Þ r ) ) V: la relation " implique " est transitive

* Pour toutes propositions p et q:

- Lien entre Þ et ( Ø , Ú )

( p Þ q ) ( Ø p Ù q ): ex: pas de fumée sans feu, c' est-à-dire non-fumée ou feu!

- Lien entre Þ et ( Ø , Ù )

( p Þ q ) ( Ø ( p Ù Ø q ) ) : application des lois de Morgan

- Lien entre Ù et ( Ø, Ú )

p Ù q º Ø ( Ø p Ú Ø q )

III- Compléments

A) Systèmes complétifs de connecteurs

Un système de connecteurs, générateur de tous les autres ( par composition et répétition ) est dit complétif. On dira que que ces connecteurs sont des termes primitifs

Par exemple, on peut choisir comme termes primitifs ou, et, non, le système {Ú, Ù, Ø} étant complétif.

En utilisant les lois de Morgan et les propriétés évoquées précédemment, on peut déterminer que le système complétif { Ú, Ø } est faible. On pourrait également chosir { Ù, Ø }. Le système formé de la barre de Sheffer est minimal, il ne comporte qu' un terme primitif!!!

Pour cela, on pourra vérifier les équivalences p ­ q º Ø ( p Ù q ) et en déduire les relations nécessaires.

B) Formes normales

On appelle forme normale disjonctive de P toute proposition équivalente à P, de la forme P₁ Ú P₂ ... Ú P_n, où chaque P_i ( avec 1 i n ) est une conjonction de propositions simples, ou de négations de propositions.

ex: ( p Þ q ) º ( p Ù q ) Ú ( Ø p Ù q ) Ú ( Ø p Ù Ø q )

On démontre que toute proposition se met sous forme normale disjonctive ( mais ce serait trop long à exposer ici ). On peut définir de la même manière une forme normale conjonctive...