Définition 2.1.1. Proposition mathématique.
Une proposition est un énoncé, une phrase déclarative qui est soit vraie, soit fausse.
Section 2.1 La logique propositionnelle
La logique propositionnelle est l’étude de propositions et leur combinaison par divers connecteurs. De manière plus générale, la logique est l’étude des conséquences de ces combinaisons. Les règles de la logique propositionnelle permettent de distinguer les raisonnements mathématiques valides des autres. Le caractère fondamental des mathématiques repose sur la validité des raisonnements qui sont utilisés pour démontrer les théorèmes et résultats divers.
D’un point de vue pratique, les règles de la logique sont maintenant utilisées en informatique afin que la machine puisse comprendre, sans ambiguïté, ce que l’utilisateur veut faire.
Dans cette section, on définit la notion de proposition, les connecteurs de conjonction,disjonction et implication. On définit aussi la négation d’une proposition, de même que la réciproque et la contraposée d’une implication. Finalement, on introduit le concept de table de vérité.
Sous-section 2.1.1 Propositions mathématiques et connecteurs logiques
L’objet le plus élémentaire de la logique est la proposition. Pour pouvoir faire un raisonnement et le valider, il faut savoir comment écrire et parler des mathématiques.
Par exemple, les énoncés suivants sont des propositions, car on peut leur attribuer une valeur de vérité.
-
Le Québec est une province du Canada (c’est vrai).
-
Le soleil tourne autour de la Terre (c’est faux).
-
\(1+1=3\) (c’est faux).
-
J’ai pris une douche ce matin (c’est soit vrai, soit faux, dépendamment du matin, mais çe ne peut pas être autre chose que vrai ou faux).
-
Si on est jeudi ou si on est samedi, alors je vais prendre un verre. (étant donné la journée, on peut déterminer la véracité)
Une proposition n’est donc pas nécessairement vraie. Ce qui importe, c’est qu’elle soit vraie ou fausse. La valeur de vérité d’une proposition pourrait même changer dans le temps, par exemple si le Québec devenait indépendant, la première proposition serait fausse, et la véracité de la proposition sur la prise de douche dépend des matins.
Les énoncés ci-dessous ne sont pas des propositions.
-
Quel jour de la semaine est-on? (Une question, pas une phrase déclarative.)
-
\(x+1\leq 4\) (si on connaissait \(x\text{,}\) on pourrait peut-être déterminer la véracité de cette proposition, mais sans informations additionnelles, c’est impossible).
Au sujet de l’énoncé avec la variable \(x\text{,}\) c’est un exemple de fonction propositionnelle. On les abordera à la section 2.3.
Les propositions avec lesquelles on travaillera seront plus complexes que les premières du paragraphe ci-dessus. Si on regarde la proposition
\begin{equation*}
\text{Si on est jeudi ou si on est samedi, alors je vais prendre un verre.}\text{,}
\end{equation*}
on constate qu’elle est composée de plusieurs petites propositions: « on est jeudi», «on est samedi» et « je vais prendre un verre». Ces trois propositions sont par la suite composées à l’aide des connecteurs «ou» et « si alors». Une proposition qui ne peut être décomposée davantage est dite atomique, alors qu’une proposition composée est appelée moléculaire.
Du côté symbolique, on utilisera principalement les lettres de l’alphabet minuscule autour de \(p\) pour désigner une proposition (atomique ou moléculaire). Par exemple, « si \(p\) ou si \(q\text{,}\) alors \(r\)» pourrait représenter la proposition «si on est jeudi ou si on est samedi, alors je vais prendre un verre». En fait, le deuxième «si» sera souvent laissé de côté, et même les connecteurs auront leur propre symbole.
Définition 2.1.2. La négation d’une proposition.
Soit \(p\) une proposition quelconque. On apelle la négation de \(p\text{,}\) notée \(\neg p\text{,}\) la proposition « il n’est pas vrai que \(p\)». C’est une proposition qui a toujours comme valeur de vérité le contraire de \(p\text{.}\)
On note parfois aussi la négation comme étant \(\sim p\) ou encore \(!p\text{.}\) Cette dernière option est celle qui est utilisée dans beaucoup de programmes informatiques.
Selon le contexte, on reformulera la proposition \(\neg p\) pour que la formulation soit plus naturelle que « il n’est pas vrai que \(p\)».
Par exemple la négation de «Le Québec est une province du Canada » est « Il n’est pas vrai que le Québec est une province du Canada », que l’on pourrait reformuler plus simplement comme « Le Québec n’est pas une province du Canada ».
Définition 2.1.3. La conjonction.
Soit \(p,q\) deux propositions. On appelle \(p\) et \(q\) la conjonction de \(p,q\text{,}\) notée \(p\wedge q\text{,}\) la proposition qui est vraie lorsque \(p\) et \(q\) sont vraies.
On note parfois aussi la conjonction entre \(p\) et \(q\) comme \(p~\& ~q\text{.}\) C’est aussi la notation qui est utilisée par beaucoup de langages informatiques. Dans la partie textuelle de ces notes, on préfère l’utilisation du symbole \(\wedge\text{,}\) car il évoque un certain parallèle avec l’intersection de la théorie des ensembles. Le lien deviendra plus clair sous peu.
Définition 2.1.4. La disjonction.
Soit \(p,q\) deux propositions. On appelle \(p\) ou \(q\) la disjonction de \(p,q\text{,}\) notée \(p\vee q\text{,}\) la proposition qui est vraie lorsque \(p\) ou \(q\) sont vraies, peut-être les deux.
On note parfois aussi la disjonction entre \(p\) et \(q\) comme \(p~|~q\text{,}\) \(p\parallel q\) ou \(p+q\text{.}\) Les deux premières notations alternatives sont celles qui sont utilisées par beaucoup de langages informatiques. Dans la partie textuelle de ces notes, on préfère l’utilisation du symbole \(\vee\text{,}\) car il évoque un certain parallèle avec l’union de la théorie des ensembles. Ce lien deviendra aussi plus clair sous peu.
La proposition « Il fait beau et je suis en congé » est une conjonction de deux propositions atomiques, alors que la proposition On est jeudi ou c’est l’hiver est une disjonction.
Remarque 2.1.5. Priorité des opérateurs.
Les opérateurs de disjonctions et de conjonctions sont des opérateurs binaires. Ils s’appliquent sur deux opérandes. L’opérateur de négation quant à lui est un opérateur unaire, qui s’applique sur l’opérande qui le suit. Afin d’éviter une trop grande utilisation de parenthèses, on donne la priorité à l’opérateur unaire.
Ainsi, la proposition \(\neg p\wedge q\) doit être vue comme \((\neg p)\wedge q\text{.}\) Si on veut la négation d’une conjonction ou d’une disjonction, on pourra utiliser les parenthèses comme dans la proposition \(\neg(p\wedge q)\text{.}\) Dans la section 2.2, on verra comment réécrire cette négation.
Sous-section 2.1.2 Table de vérité
Il n’est pas évident de déterminer la valeur de vérité d’une proposition moléculaire complexe en regardant simplement ses morceaux et leur interaction. Par exemple, quand peut-on dire que la proposition moléculaire « J’ai une soeur ou il n’est pas vrai que ( j’ai une soeur et le ciel est rouge) » est vraie? Si on la décortique, on voit qu’elle est formée des deux propositions atomiques \(p=\text{J'ai une soeur}\) et \(q=\text{le ciel est rouge}\) et représentée symboliquement par \(p\vee \neg (p\wedge q)\text{.}\) Cette proposition complexe a certainement une valeur de vérité, qui dépend probablement des valeurs de vérités individuelles de \(p\) et \(q\text{.}\)
Pour analyser une proposition complexe, on utilise une table de vérité. C’est un outil semblable au tableau d’appartenance introduit à la proposition 1.2.14. Ci-dessous, les tables de vérités des connecteurs de négation, conjonction et disjonction.
Exemple 2.1.7. Une table de vérité plus complexe.
On considère la proposition \(p\vee \neg (p\wedge q)\) et on cherche à déterminer sous quelle condition elle est vraie. On utilise une table de vérité.
Solution.
Pour ce type de proposition, il convient de décomposer en plus petits morceaux et d’analyser chacun de ces morceaux afin de former le tout. La table de vérité
| \(p\) | \(q\) | \(p\wedge q\) | \(\neg(p\wedge q)\) | \(p\vee \neg(p\wedge q)\) |
| V | V | V | F | V |
| V | F | F | V | V |
| F | V | F | V | V |
| F | F | F | V | V |
Comme on peut le voir, la proposition finale est toujours vraie, indépendamment de la véracité des propositions individuelles \(p,q\text{.}\)
Sous-section 2.1.3 Implication, réciproque et contraposée
Une autre manière de connecter des propositions est d’utiliser la formule « si \(p\text{,}\) alors \(q\)». Par exemple, la proposition « S’il pleut, alors le gazon est mouillé » est une telle proposition.
Définition 2.1.9. L’implication logique.
Soit \(p\) et \(q\) deux propositions. On appelle si \(p\text{,}\) alors \(q\) l’implication logique, notée \(p\rightarrow q\text{.}\) C’est une proposition qui est fausse lorsque \(p\) est vraie et \(q\) est fausse, mais vraie dans tous les autres cas.
La proposition \(p\) est appelée l’hypothèse ou la prémisse et la proposition \(q\) est appelée la conséquence ou la conclusion.
En plus de si \(p\) alors \(q\text{,}\) on dit parfois aussi \(p\) implique \(q\text{,}\) \(p\) seulement si \(q\text{,}\)\(p\) est suffisant pour que \(q\) soit vraie ou encore \(q\) est nécessaire pour avoir \(p\text{.}\)
La table de vérité de l’implication se trouve ci-dessous.
| \(p\) | \(q\) | \(p\rightarrow q\) |
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
À priori, il semble étrange d’avoir une proposition qui est vraie lorsque ses composantes sont fausses. Il faut réaliser que pour la logique mathématique, il n’est pas important qu’il y ait un lien entre \(p\) et \(q\) pour les connecter avec l’implication. Ainsi, « si on est jeudi, alors \(1+1=3\)» est une implication qui en générale sera considérée comme vraie, puisque six fois sur sept jeudi n’est pas aujourd’hui et que \(1+1\neq 3\text{,}\) mais lorsque que c’est jeudi, l’implication devient fausse. L’idée générale à retenir est qu’à partir d’une hypothèse qui est vraie, on ne peut que conclure la vérité, mais à partir d’une prémisse fausse, on peut arriver à n’importe quelle conclusion. En particulier pour la dernière ligne, ce n’est pas de dire que \(q\) est vraie, mais que l’implication au total est vraie, un peu par défaut si à la fois l’hypothèse et la conclusion sont fausses.
Pour reprendre la proposition « S’il pleut, alors le gazon est mouillé », on considère les trois cas de figure suivant:
-
Il pleut et le gazon est mouillé.
-
Il ne pleut pas, mais le gazon est mouillé.
-
Il pleut, mais le gazon n’est pas mouillé.
Dans les deux premiers cas, la conclusion est vraie. L’implication est alors vérifiée. Il n’est pas important de savoir ce qui a causé le gazon à être mouillé. Dans le troisième cas de figure, l’implication est fausse, car elle stipule que la pluie aurait du mouiller le gazon, mais cela ne s’est pas produit. Dans le cas où il ne pleut pas et que le gazon n’est pas mouillé, l’implication serait vraie par défaut.
À partir d’une implication, on peut définir deux autres propositions reliées. Il est important de les distinguer.
Définition 2.1.11. La réciproque et la contraposée d’une implication.
Soit \(p,q\) des propositions. La proposition \(q\rightarrow p\) est appelée la réciproque de \(p\rightarrow q\) et la proposition \(\neg q\rightarrow \neg p\) est appelée la contraposée.
Ci-dessous on retrouve les tables de vérité de l’implication \(p\rightarrow q\text{,}\) sa réciproque et sa contraposée.
| \(p\) | \(q\) | \(\neg p\) | \(\neg q\) | \(p\rightarrow q\) | \(q\rightarrow p\) | \(\neg q \rightarrow \neg p\) |
| V | V | F | F | V | V | V |
| V | F | F | V | F | V | F |
| F | V | V | F | V | F | V |
| F | F | V | V | V | V | V |
En particulier, on remarque que l’implication et la contraposée ont exactement les mêmes valeurs de vérités en même temps. On dit de deux propositions qui possèdent cette propriété qu’elles sont équivalentes. On revient sur ce concept à la section 2.2.
La réciproque par contre n’est pas nécessairement vraie quand l’implication l’est. On peut toutefois imposer cette condition en créant la double implication.
Définition 2.1.13. La double implication.
Soit \(p\) et \(q\) des propositions. On appelle \(p\) si et seulement si \(q\text{,}\) et on note \(p\leftrightarrow q\text{,}\) la proposition \((p\rightarrow q)\wedge (q\rightarrow p)\text{.}\) On l’appelle aussi la biconditionnelle.
Les éléments importants de cette section sont:
-
La définition d’une proposition.
-
La notion d’implication et les formes “si … alors”,“seulement si”,“nécessaire” et “suffisant”.
-
La notion de réciproque et de contraposée.
-
La construction d’une table de vérité et les tables de vérité de la conjonction, disjonction et implication.
-
La double implication et les formes “si et seulement si” et “nécessaire et suffisant”.
Questions de compréhension de la lecture 2.1.4 Questions de compréhension de la lecture
Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
1.
Parmi les énoncés suivants, lesquels sont des propositions? Justifier brièvement.
(a)
Il est 8 heures.
(b)
Il est 8 heures?
(c)
\(x^2\geq 4\)
(d)
(e)
Le café doit être changé toutes les vingt minutes.
(f)
J’ai un chien ou un chat.
(g)
Il roulait à plus de \(60\) km/h et a brulé un feu rouge.
(h)
Cette phrase est fausse.
2.
Parmi les propositions précédentes, identifier celles qui sont moléculaires et décortiquer les en propositions atomiques.
3.
On suppose qu’il est connu que l’auteur a un frère, mais il est incertain s’il a une soeur. Déterminer si les propositions suivantes sont vraies, fausses ou s’il manque d’information pour le savoir.
(a)
L’auteur a un frère ou l’auteur a une soeur.
(b)
L’auteur a un frère et l’auteur a une soeur.
(c)
L’auteur a une soeur ou l’auteur n’a pas de soeur.
(d)
Si l’auteur a une soeur, alors il a un frère.
(e)
Si l’auteur a un frère, alors il a une soeur.
(f)
Si l’auteur n’a pas de frère, alors il a une soeur.
4.
Tout comme pour la théorie des ensembles, on peut définir le “ou exclusif” pour des propositions logiques. Noté \(p\oplus q\text{,}\) cette proposition est vrai lorsqu’exactement une des propositions \(p,q\) est vraie.
Donner la table de vérité du “ou exclusif”.
5.
Donner la table de vérité de la double implication.
6.
Chaque phrase ci-dessous peut-être réécrite sous la forme d’une implication. Donner l’hypothèse et la conclusion de chacune de ces implications.
(a)
Tous les Québécois aiment le Canadien de Montréal.
(b)
Le record sera battu si les conditions sont favorables.
(c)
Le record sera battu seulement si les conditions sont favorables.
(d)
Pour avoir un permis de conduire, il est nécessaire d’avoir au moins \(16\) ans.
(e)
Pour pouvoir acheter de l’alcool, il suffit d’avoir 18 ans.
7.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Exercices 2.1.5 Exercices
À faire en classe.
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
1.
Construire la table de vérité pour
\begin{equation*}
(p\vee q)\wedge (p\vee \neg q)\text{.}
\end{equation*}
2.
Dans chacune des propositions suivantes, est-il plus probable que le « ou » soit inclusif ou exclusif? Justifier
(a)
Je vais prendre du riz ou des frites avec mon poulet.
(b)
Pour s’inscrire à ce cours, il faut avoir réussi deux cours de mathématiques ou trois cours de physique.
(c)
Le Canadien a gagné ou perdu hier.
3.
On considère les propositions
-
\(p:\) J’ai passé le cours de mathématiques discrètes.
-
\(r:\) Je n’ai pas fait tous les devoirs recommandés par mon professeur.
Écrire les propositions suivantes en langage courant.
(a)
\(p\wedge q\)
(b)
\(\neg p \wedge r\)
(c)
\(q\rightarrow p\)
(d)
\(\neg p\rightarrow (\neg q\vee r)\)
(e)
\((p\wedge q)\leftrightarrow \neg r\)
4.
Écrire les phrases suivantes en proposition logique n’utilisant que des variables \(p_1, p_2,\dots\) et des connecteurs de la section. Lorsqu’un « ou » devrait être exclusif, utiliser \(\oplus\text{.}\)
(a)
J’irai à l’épicerie et chercher les enfants.
Indice.
On pose:
\(p_1:\) J’irai à l’épicerie.
\(p_2:\) J’irai chercher les enfants.
\(p_3:\) Tu m’entend chanter.
\(p_4:\) Je chante.
\(p_5:\) Je prend ma douche.
\(p_6:\) C’est nuageux.
\(p_7:\) Il pleut.
\(p_8:\) Je suis seul dans ma voiture.
\(p_9:\) Il fait chaud.
\(p_{10}:\) Vous êtes sage.
\(p_{11}:\) On ira à la plage.
\(p_{12}:\) Vous achetez cette voiture.
(b)
Si tu m’entends chanter, c’est que je suis sous la douche.
(c)
Quand je prends une douche, je chante
(d)
C’est nuageux, mais il n’y a pas de pluie.
(e)
Je chante sous la douche ou seul dans ma voiture.
(f)
S’il fait chaud et que vous êtes sage, on ira à la plage.
(g)
Si vous achetez cette voiture, je vous propose \(1000\)$ de rabais au comptant ou un rabais de \(1\%\) sur le financement.
5.
Construire la table de vérité des propositions suivantes.
(a)
\((p\vee q)\rightarrow (p\wedge q)\)
(b)
\((p\wedge q)\rightarrow \neg r\)
(c)
\((p\vee q)\rightarrow \neg r\)
(d)
\((p\leftrightarrow q)\vee (\neg p \leftrightarrow r)\)
Réponse.
| \(p\) | \(q\) | \(r\) | \(\neg p\) | \((p\leftrightarrow q)\) | \((\neg p \leftrightarrow r)\) | \((p\leftrightarrow q)\vee (\neg p \leftrightarrow r)\) |
| V | V | V | F | V | F | V |
| V | V | F | F | V | V | V |
| V | F | V | F | F | F | F |
| V | F | F | F | F | V | V |
| F | V | V | V | F | V | V |
| F | V | F | V | F | F | F |
| F | F | V | V | V | V | V |
| F | F | F | V | V | F | V |
6.
Dans cet exercice, on réfléchit à la négation de la disjonction, soit \(\neg(p\vee q)\text{.}\) Plus particulièrement, on veut trouver une autre formulation.
(a)
Quelle est la table de vérité de la négation de la disjonction?
(b)
En regardant l’unique ligne qui a pour valeur “vrai”, donner une formulation pour \(\neg(p\vee q)\text{.}\)
(c)
Donner la négation de “Je n’ai pas fait tous les exercices ou j’ai passé le cours” sous la forme trouvée ci-dessus.
7.
Dans cet exercice, on réfléchit à la négation de l’implication, soit \(\neg(p\rightarrow q)\text{.}\) Plus particulièrement, on veut trouver une autre formulation.
(a)
Quelle est la table de vérité de la négation de l’implication?
(b)
En regardant l’unique ligne qui a pour valeur “vrai”, donner une formulation pour \(\neg(p\rightarrow q)\) qui n’utilise pas l’implication.
(c)
Donner la négation de “Si je fais tous les exercices, alors je vais passer le cours” sous la forme trouvée ci-dessus.
8.
Pour les phrases suivantes, énoncer en langage courant l’implication, la négation, la réciproque et la contraposée.
(a)
Si je fais mes exercices, je vais passer le cours.
Réponse.
-
Implication: Si je fais mes exercices, alors je vais passer le cours.
-
Négation: J’ai fais mes exercices, mais je ne vais pas passer le cours.
-
Réciproque: Si je passe le cours, alors j’ai fait mes exercices.
-
Contraposée: Si je ne passe pas le cours, alors je n’ai pas fait mes exercices.
(b)
Quand je travaille de nuit, je dors jusqu’à 14:00.
Réponse.
(c)
Pour être riche, il suffit de gagner à la loterie
(d)
Pour être riche, il est nécessaire de gagner à la loterie.
(e)
Le gazon est mouillé chaque fois qu’il pleut.
Exercices supplémentaires.
9.
Il est possible de réécrire la définition d’un ensemble à partir de propositions et de connecteurs logiques. Par exemple, l’union de deux ensembles peut s’écrire
\begin{equation*}
A\cup B=\{c\in \Omega~|~ c\in A \vee c\in B\}\text{.}
\end{equation*}
Écrire les ensembles suivants en utilisant les symboles logiques.
(a)
\(A\cap B\)
(b)
\(A\times B\)
(c)
10.
Dans cet exercice, on réfléchit à la négation de la conjonction, soit \(\neg(p\wedge q)\text{.}\) Plus particulièrement, on veut trouver une autre formulation.
(a)
Quelle est la table de vérité de la négation de la conjonction?
(b)
En regardant les lignes qui ont pour valeur “vrai”, donner une formulation pour \(\neg(p\wedge q)\text{.}\)
(c)
Donner la négation de “J’ai fait tous les exercices et j’ai passé le cours” sous la forme trouvée ci-dessus.
11.
Dans la section 1.2, on a donné deux moyens pour démontrer l’égalité de deux ensembles, soit avec une table d’appartenance ou avec un argument de double inclusion. On démontre ci-dessous la deuxième loi de De Morgan à l’aide d’une troisième méthode, utilisant la logique.
On veut montrer que \((A\cup B)^c=A^c\cap B^c\text{.}\) Par définition, on a \(A\cup B=\{c~|~ c\in A\vee c\in B\}\text{.}\) D’un point de vue de la logique, le complément représente la négation. On a alors
\begin{align*}
(A\cup B)^c&=\{c~|~\neg ( c\in A\vee c\in B)\}\\
&=\{c~|~\neg (c\in A)\wedge \neg( c\in B)\} & & \text{Selon } \knowl{./knowl/xref/exo-negdisj.html}{\text{2.1.5.6}}\\
&=\{c~|~c\notin A\wedge c\notin B)\}& & \text{négation de la relation d'appartenance}\\
&=A^c\cap B^c && \text{définition de l'intersection}
\end{align*}
Démontrer la première loi de De Morgan avec cette méthode.
Solution.
\begin{align*}
(A\cap B)^c&=\{c~|~\neg ( c\in A\wedge c\in B)\}\\
&=\{c~|~\neg (c\in A)\vee \neg( c\in B)\} & & \text{Selon } \knowl{./knowl/xref/exo-negconj.html}{\text{2.1.5.10}}\\
&=\{c~|~c\notin A\vee c\notin B)\}& & \text{négation de la relation d'appartenance}\\
&=A^c\cup B^c && \text{définition de l'union}
\end{align*}
