On appelle proposition un énoncé mathématique qui peut être vrai ou faux.
Exemple
Deux propositions simples.
«1+1=2» est une proposition vraie.
«7 est un entier pair» est une proposition fausse.
Définition—Négation
A une proposition P, on peut associer sa négation notée non P qui est vraie si P est fausse et fausse si P est vraie.
1.2. Conjonction et disjonction
Définition—Conjonction
A deux propositions P et Q, on peut associer la conjonction de P et Q notée P et Q qui est
vraie si les deux propositions P et Q sont vraies;
fausse si l'une au moins des deux propositions P ou Q est fausse.
1.3. Implication et équivalence
Définition—Implication
A deux propositions P et Q, on peut associer la proposition P⟹Q qui est
vraie si P est fausse ou si P et Q sont vraies;
fausse si P est vraie et Q fausse.
1.4. Formule propositionnelle
Définition—Formule propositionnelle
On appelle formule propositionnelle une combinaison de propositions logiques et de connecteurs logiques.
Définition—Tautologie
Une formule propositionnelle est appelée une tautologie si elle est vraie quelles que soient les valeurs de vérité des propositions logiques qui la composent.
Exemple
Si P est une proposition logique, P ou (non P) est une tautologie.
1.5. Conditions nécessaires et/ou suffisantes
Remarque—Conditions nécessaires et conditions suffisantes
Soient P et Q deux propositions.
On dit que Q est une condition nécessaire pour avoir P si, dès que P est vraie alors nécessairement forcément Q est vraie. Autrement dit, P⟹Q est vraie.
On dit que Q est une condition suffisante pour avoir P s'il suffit que Q soit vraie pour que P soit vraie. Autrement dit, Q⟹P est vraie.
On dit que Q est une condition nécessaire et suffisante pour avoir P quand P est vraie si et seulement si Q est vraie. Autrement dit, P⟺Q est vraie.
1.6. Règles de calcul propositionnel
Proposition—Distributivité
Soient P, Q et R trois propositions logiques. Alors on a :
((P ou Q) et R)≡((P et R) ou (Q et R))
((P et Q) ou R)≡((P ou R) et (Q ou R))
1.7. En pratique
Méthode—Montrer qu'une implication est vraie
Pour montrer que P⟹Q est vraie, il suffit de montrer que si P est vraie, alors Q est vraie. Remarque. La notation logique P⟹Q correspond en français à la phrase «si P alors Q».
Soit ABCD un rectangle. La proposition «l'angle ABC est droit et les diagonales [AC] et [BD] se coupent en leur milieu» est vraie. Soit ABC un triangle. La proposition «AB>AC+BC et ABC+CAB+BCA=π» est fausse.
Définition—Disjonction
A deux propositions P et Q, on peut associer la disjonction P ou Q qui est
vraie si l'une au moins des deux propositions P ou Q est vraie;
fausse si les deux propositions P et Q sont fausses.
Remarque
Le «ou» considéré ici est un «ou» non exclusif. La proposition P ou Q est vraie si l'une au moins des deux propositions P ou Q est vraie et non si exactement une des propositions est vraie.
Exemple
Soit ABC un triangle. La proposition «AB>AC+BC ou ABC+CAB+BCA=π» est vraie.
Remarques
Si P et P⟹Q sont vraies, alors nécessairement Q est vraie.
L'implication Q⟹P s'appelle la réciproque de l'implication P⟹Q. Si une implication est vraie, sa réciproque n'est pas forcément vraie.
Exemple
Soient a et b deux réels. Alors a=b⟹a2=b2 est vraie mais a2=b2⟹a=b est fausse en général.
Contre-exemple—La réciproque d'une implication vraie peut être fausse
L'implication n≥2⟹n2≥4 est vraie pour n∈Z : si n≥2, alors n2≥4.
Sa réciproque n2≥4⟹n≥2 est fausse : pour n=−3, on a n2=9≥4 mais n=−3<2.
Ainsi, une implication vraie n'entraîne pas la vérité de sa réciproque.
Définition—Équivalence
A deux propositions P et Q, on peut associer la proposition P⟺Q qui est
vraie si P et Q sont vraies ou si P et Q sont fausses;
fausse sinon.
Exemple
Soient a et b deux réels. Alors a=b⟺ea=eb.
Encadré—Notation 1.1
Si F et G sont des formules propositionnelles, on notera F≡G si la proposition F⟺G est une tautologie.
Proposition—Reformulations
Soient P et Q des propositions logiques.
(P⟹Q)≡((non P) ou Q).
(P⟺Q)≡((P⟹Q) et (Q⟹P)).
(P ou Q)≡((non P)⟹Q).
Démonstration
Par la Notation 1.1, montrer F≡G revient à montrer que F⟺G est une tautologie, c'est-à-dire vraie pour toutes valeurs de vérité des propositions qui la composent (Définition 1.8). On procède donc par tables de vérité pour chacune des trois identités.
Première identité :(P⟹Q)≡((non P) ou Q).
On dresse la table de vérité des deux formules en parcourant les 4 cas possibles :PVVFFQVFVFP⟹QVFVVnon PFFVV(non P) ou QVFVVLes colonnes P⟹Q et (non P) ou Q sont identiques (d'après la Définition 1.5 pour l'implication et la Définition 1.2 et 1.4 pour les colonnes de droite). Donc (P⟹Q)⟺((non P) ou Q) est vraie dans tous les cas : c'est une tautologie.
Deuxième identité :(P⟺Q)≡((P⟹Q) et (Q⟹P)).
On dresse la table de vérité :PVVFFQVFVFP⟺QVFFVP⟹QVFVVQ⟹PVVFV(P⟹Q) et (Q⟹P)VFFVLes colonnes P⟺Q et (P⟹Q) et (Q⟹P) sont identiques (d'après la Définition 1.6 pour l'équivalence, la Définition 1.5 pour les deux implications, et la Définition 1.3 pour la conjonction). Donc la formule est une tautologie.
Troisième identité :(P ou Q)≡((non P)⟹Q).
On dresse la table de vérité :PVVFFQVFVFP ou QVVVFnon PFFVV(non P)⟹QVVVFLes colonnes P ou Q et (non P)⟹Q sont identiques (d'après la Définition 1.4 pour la disjonction, la Définition 1.2 pour la négation, et la Définition 1.5 pour l'implication). Donc la formule est une tautologie.
Les trois identités étant vérifiées par tables de vérité exhaustives, la proposition est démontrée.
Application
Soient P et Q des propositions logiques. Montrer que (P et (P⟹Q))⟹Q est une tautologie.
Correction
On veut montrer que (P et (P⟹Q))⟹Q est une tautologie, c'est-à-dire vraie pour toutes valeurs de vérité de P et Q (d'après la Définition 1.8).
On dresse la table de vérité :PVVFFQVFVFP⟹QVFVVP et (P⟹Q)VFFF(P et (P⟹Q))⟹QVVVVLes valeurs de chaque colonne sont calculées d'après les Définitions 1.5 (implication), 1.3 (conjonction) et 1.5 à nouveau (implication extérieure). La dernière colonne est vraie dans tous les cas : (P et (P⟹Q))⟹Q est donc une tautologie. □
Application
Soit x∈R. La proposition «x≥1» est-elle une condition nécessaire de la proposition «x2+x+2≥3» ? Même question avec suffisante.
Correction
Soient P la proposition «x≥1» et Q la proposition «x2+x+2≥3», c'est-à-dire «x2+x−1≥0».
P est-elle une condition nécessaire de Q ? Cela revient à se demander si Q⟹P est vraie (d'après la définition des conditions nécessaires). Or x=−2 vérifie (−2)2+(−2)+2=4−2+2=4≥3 (donc Q est vraie) mais −2<1 (donc P est fausse). Ainsi Q⟹P est fausse dans ce cas. P n'est pas une condition nécessaire de Q.
P est-elle une condition suffisante de Q ? Cela revient à se demander si P⟹Q est vraie. Supposons x≥1. Alors x2≥x≥1 et x≥1, donc x2+x+2≥1+1+2=4≥3. Ainsi Q est vraie dès que P est vraie : P⟹Q est vraie. P est une condition suffisante de Q. □
Démonstration
Par la Notation 1.1, montrer F≡G revient à montrer que F⟺G est une tautologie (Définition 1.8). On procède par tables de vérité à trois variables P, Q, R : il y a 23=8 cas possibles.
Première identité :((P ou Q) et R)≡((P et R) ou (Q et R)).PVVVVFFFFQVVFFVVFFRVFVFVFVFP ou QVVVVVVFF(P ou Q) et RVFVFVFFFP et RVFVFFFFFQ et RVFFFVFFF(P et R) ou (Q et R)VFVFVFFFLes colonnes 5 et 8 sont identiques dans tous les cas (chaque cellule est calculée d'après les Définitions 1.3 et 1.4 de la conjonction et de la disjonction). La formule est donc une tautologie.
Deuxième identité :((P et Q) ou R)≡((P ou R) et (Q ou R)).PVVVVFFFFQVVFFVVFFRVFVFVFVFP et QVVFFFFFF(P et Q) ou RVVVFVFVFP ou RVVVVVFVFQ ou RVVVFVVVF(P ou R) et (Q ou R)VVVFVFVFLes colonnes 5 et 8 sont identiques dans tous les cas. La formule est donc une tautologie.
Les deux identités de distributivité étant vérifiées exhaustivement, la proposition est démontrée.
Remarque
On dit que la conjonction (resp. la disjonction) est distributive sur la disjonction (resp. conjonction).
Exemple
{x2=1y=−3⟺{x=1 ou x=−1y=−3⟺({x=1y=−3 ou {x=−1y=−3)
Proposition—Négation
Soient P et Q deux propositions logiques. Alors on a :
non(P et Q)≡((non P) ou (non Q))
non(P ou Q)≡((non P) et (non Q))
non(P⟹Q)≡(P et (non Q))
Démonstration
Par la Notation 1.1, il s'agit dans chaque cas de montrer que la formule F⟺G est une tautologie (Définition 1.8). On traite les deux premières identités par tables de vérité, et la troisième en utilisant la Proposition 1.1.
Première identité (première loi de De Morgan) :non(P et Q)≡((non P) ou (non Q)).PVVFFQVFVFP et QVFFFnon(P et Q)FVVVnon PFFVVnon QFVFV(non P) ou (non Q)FVVVLes colonnes 4 et 7 sont identiques dans les 4 cas (d'après la Définition 1.3 pour la conjonction, la Définition 1.2 pour la négation, et la Définition 1.4 pour la disjonction). La formule est une tautologie.
Deuxième identité (deuxième loi de De Morgan) :non(P ou Q)≡((non P) et (non Q)).PVVFFQVFVFP ou QVVVFnon(P ou Q)FFFVnon PFFVVnon QFVFV(non P) et (non Q)FFFVLes colonnes 4 et 7 sont identiques dans les 4 cas. La formule est une tautologie.
Troisième identité :non(P⟹Q)≡(P et (non Q)).
D'après la Proposition 1.1 (première reformulation), on a P⟹Q≡(non P) ou Q. Autrement dit, (P⟹Q)⟺((non P) ou Q) est une tautologie. En particulier, pour toutes valeurs de vérité de P et Q, les formules P⟹Q et (non P) ou Q ont la même valeur de vérité, donc leurs négations aussi. Ainsi :non(P⟹Q)≡non((non P) ou Q).Or, d'après la deuxième identité démontrée ci-dessus (appliquée à non P à la place de P et Q à la place de Q) :non((non P) ou Q)≡(non(non P)) et (non Q).Enfin, d'après la Définition 1.2 de la négation, non(non P) a la même valeur de vérité que P (la double négation redonne la proposition initiale), donc :non((non P)) et (non Q)≡P et (non Q).En enchaînant les trois équivalences, on obtient bien non(P⟹Q)≡P et (non Q).
Exemples
La négation de la proposition −1≤x≤2 est x<−1 ou x>2.
Soient P la proposition «Il y a de la fumée» et Q la proposition «Il y a du feu». Le célèbre proverbe «Il n'y a pas de fumée sans feu» se traduit par P⟹Q. Sa négation est «Il y a de la fumée et il n'y a pas de feu» qui se traduit par P et (non Q).
Attention
L'implication P⟹Q peut être vraie sans que P et Q ne soient forcément vraies. Quand on vous demande de montrer que l'implication P⟹Q est vraie, il ne s'agit nullement de prouver que P ou Q sont vraies mais que si P est vraie, alors Q est vraie.
Méthode—Montrer qu'une équivalence est vraie
Pour montrer que P⟺Q est vraie, il suffit de montrer que si P est vraie, alors Q est vraie et que si Q est vraie, alors P est vraie. Remarque. La notation logique P⟺Q correspond en français à la phrase «P si et seulement si Q».
Attention
L'équivalence P⟺Q peut être vraie sans que P et Q ne soient forcément vraies. Quand on vous demande de montrer que l'équivalence P⟺Q est vraie, il ne s'agit nullement de prouver que P ou Q sont vraies mais que P est vraie si et seulement si Q est vraie. En pratique, dans une rédaction, on n'emploiera jamais les symboles ⟹ et ⟺. Le seul endroit où le symbole ⟺ est toléré, c'est dans les résolutions d'équations ou d'inéquations. On préférera l'emploi de mots de français : conjonctions de coordination (mais, ou, et, donc, or, ni, car), conjonctions de subordination (parce que, si, puisque, ...) ou adverbes (ainsi, cependant, ...).
