Cours - Pour bien demarrer l'annee

Informations

• Publié par: Enfea
• Nombre de lectures: 48
• Langue: Français

Extrait

c Christophe Bertault - MPSI
Pour bien démarrer l’année
Ce chapitre a un statut particulier par rapport à tous ceux qui vont suivre : ses enseignements nous serviront toujours et
partout. Ne paniquez pas si vous le trouvez déroutant, car les chapitres suivants ressembleront davantage à ceux qu’on vous a
enseignés au lycée.
1 Un peu de logique
Convenons d’appeler proposition toute phrase p au sujet de laquelle on peut poser la question : p est-elle vraie? La plupart
des phrases grammaticalement correctes sont des propositions, mais par exemple, « Dis-le-moi! », « Bonjour » ou « Comment
vas-tu? » n’en sont pas : la question « Est-il vrai que bonjour? » n’a aucun sens.
La valeur de vérité d’une proposition est soit le vrai (V), soit le faux (F). Deux propositions qui ont la même valeur de vérité
sont dites équivalentes : elles sont soit toutes les deux vraies, soit toutes les deux fausses. Cette notion est très importante :
quand vous devez démontrer une proposition p, vous n’êtes pas obligé de démontrer p elle-même : il suffit que vous démontriez
n’importe quelle proposition équivalente à p.
Exemple « Socrate n’est pas immortel » et « Socrate est mortel » sont deux propositions équivalentes. Démontrer l’une,
c’est démontrer l’autre.
1.1 Connecteurs logiques
Onappelle connecteur logiquetoutmoyendeconstruire uneproposition àpartird’uneouplusieurspropositions.Par exemple,
« et », « ou », « si, alors » et « parce que » sont des connecteurs : à partir des propositions « J’ai faim » et « J’ai soif », on peut
construire une nouvelle proposition « J’ai faim et (j’ai) soif ».
Un connecteur logique est dit vérifonctionnel si la valeur de vérité d’une proposition construite à l’aide de ce connecteur
dépend seulement de la valeur de vérité des propositions utilisées dans la construction. Ainsi la proposition « p et q » est vraie
si et seulement si les deux propositions p et q sont vraies. Peu importent le contenu exact, le sens exact de p et q : seule leur
vérité compte.
En mathématiques, tous les connecteurs logiques sont vérifonctionnels. L’intérêt des connecteurs
p q p et q
vérifonctionnels réside dans la facilité avec laquelle on peut les définir. Par exemple, pour définir le
V V V
connecteur « et », il suffit de décrire, en fonction de la valeur de vérité de p et q, la valeur de vérité de la
V F F
proposition « p et q » : par définition, « p et q » est vraie si p et q le sont, et fausse dans tous les autres
F V F
cas. Par souci de clarté, on présente généralement cette définition sous forme d’un tableau appelé table
F F F
de vérité :
Pour votre culture, remarquez bien que certains connecteurs logiques ne sont pas vérifonctionnels. C’est le cas du connecteur
« parce que ». Imaginons en effet un contexte dans lequel il est vrai que « Ses lunettes sont cassées parce qu’il s’est assis dessus ».
Alors les deux propositions « Ses lunettes sont cassées » et « Il s’est assis dessus » sont vraies. Remplaçons à présent « Il s’est
assis dessus » par « La glace est un solide », elle aussi vraie. Si le connecteur « parce que » était vérifonctionnel, notre nouvelle
proposition « Ses lunettes sont cassées parce que la glace est un solide » devrait encore être vraie — ce qui n’est pas le cas. Cette
absurdité prouve que « parce que » n’est pas vérifonctionnel.
1.1.1 Négation non
p non p
La proposition « non p » est vraie si p est fausse, fausse si p est vraie. V F
F V
p non p non (non p)
Loi de la double négation : p et « non (non p) » sont deux propositions
V F V
équivalentes. On s’en rend compte en observant la table suivante :
F V F
տ ր
Colonnes identiques
16
c Christophe Bertault - MPSI
1.1.2 Conjonction et, disjonction ou
p q p et q p ou q
La proposition « p et q » est vraie si p et q sont vraies, fausse dans tous les autres cas. V V V V
Quant à la proposition « p ou q », elle est vraie si p est vraie ou si q est vraie (éventuellement V F F V
les deux), fausse dans le seul cas où p et q sont fausses toutes les deux. F V F V
F F F F
$$$ Attention ! Dans le langage usuel, il arrive que « ou » oppose les termes qu’il relie. Dans l’expression « fromage
ou dessert », « ou » est exclusif car il exclut la possibilité qu’on choisisse les deux (fromage et dessert).
En mathématiques au contraire, « ou » est inclusif : « p ou q » est vraie même quand p et q sont vraies.
En pratique Comment montre-t-on une disjonction « p ou q »? Il s’agit de montrer que l’une au moins des
propositions p et q est vraie. Si p est vraie, « p ou q » l’est aussi — mais sinon? Reste à savoir si q est vraie quand p est fausse.
Conclusion : pour montrer que « p ou q » est vraie, on suppose que p est fausse et on montre sous cette hypothèse que q est
vraie. On peut bien sûr permuter les rôles de p et q.
Lois de De Morgan :
• « non (p et q) » et « (non p) ou (non q) » sont deux propositions équivalentes.
• « non (p ou q) » et « (non p) et (non q) » sont deux propositions équivalentes.
p q non p non q p et q non (p et q) (non p) ou (non q) p ou q non(p ou q) (non p) et (non q)
V V F F V F F V F F
V F F V F V V V F F
F V V F F V V V F F
F F V V F V V F V V
տ ր տ ր
Colonnes identiques Colonnes identiques

« Je n’aime ni le chocolat ni la vanille » — « (non p) et (non q) ».
Exemple Ces deux phrases sont équivalentes :
« Il est faux que j’aime le chocolat ou la vanille » — « non (p ou q) ».
1.1.3 Implication =⇒
p q p =⇒ q
V V VLa proposition « p =⇒ q » se lit « p implique q » ou « si p, alors q ». Elle est vraie si p est
fausse ou si q est vraie, fausse uniquement lorsque p est vraie et q fausse. La proposition p est appelée V F F
l’antécédent de l’implication « p =⇒ q », et q est appelée son conséquent. F V V
F F V
p q non p (non p) ou q p =⇒ q
V V F V V
Lien entre l’implication et la disjonction : « p =⇒ q »
V F F F F
et « (non p) ou q » sont deux propositions équivalentes.
F V V V V
F F V V V
տ ր
Colonnes identiques
En pratique Comment montre-t-on la vérité d’une implication « p =⇒ q »? Comme on vient de le voir, cela
revient à prouver la proposition équivalente « (non p) ou q ». Or nous avons vu plus haut comment montrer une disjonction.
Conclusion : pour montrer que « p =⇒ q », on suppose que p est vraie et on montre sous cette hypothèse que q est vraie.
Même quand vous n’arrivez pas au bout de la démonstration d’une implication « p =⇒ q », vous devez au moins sur votre copie
commencer bêtement par : « Supposons p vraie ».
$$$ Attention !
• Une implication « p =⇒ q » peut être vraie alors que p et q n’ont rien de commun. Il suffit que leurs valeurs de vérité
respectent la table de vérité de l’implication. Ainsi la phrase « Si 0 = 0, alors les oiseaux ont des plumes » est vraie.
• Par définition, « p =⇒ q » est toujours vraie quand p est fausse. Ainsi la phrase étrange « Si 0 = 0, alors 0 = 0 » est
vraie. Après un tel exemple, la définition de l’implication peut sembler suspecte : pourquoi donc avoir choisi cette table de
vérité? Nous le justifierons plus loin.
• Affirmer que « p =⇒ q » est vraie n’implique ni que p est vraie, ni que q est vraie. Il est vrai que « Si Pinocchio est
Président de la République, alors il est chef des armées », mais il est faux que Pinocchio est Président de la République,
et également faux qu’il est chef des armées.
26
c Christophe Bertault - MPSI
De l’équivalence des propositions « p =⇒ q » et « (non p) ou q » d’une part, et « non (p ou q) » et « (non p) et (non q) »
d’autre part, il découle immédiatement que :
Négation d’une implication : « non (p =⇒ q) » et « p et (non q) » sont deux propositions équivalentes.
En pratique Pour montrer la fausseté d’une implication « p =⇒ q », il suffit de montrer que « p et (non q) » est
vraie, i.e. que p est vraie mais que q est fausse.
Exemple Est-il vrai que, si on a 18 ans (p), alors on a le droit de vote (q)? La réponse est... non. Car je peux très bien
avoir 18 ans — p est vraie — et un casier judiciaire tel que le droit de vote m’a été supprimé — q est fausse.
Contraposition : p q non q non p p =⇒ q (non q) =⇒ (non p)
« p =⇒ q » et « (non q) =⇒ (non p) » sont deux p