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:
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é.
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:
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.
Cette suite de 4 valeurs est appelé évaluation
de p q q.
Pour la détermination de p q
q, il y a 24 é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 = IdC : 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 P1 Ú P2 ... Ú Pn, où chaque Pi ( 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...