Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Mathématiques MAT1 - MAT 2022 - 2023 R. Absil L. Beeckmans J. Beleho D. Boigelo

Mathématiques MAT1 - MAT 2022 - 2023 R. Absil L. Beeckmans J. Beleho D. Boigelot L. La Fuente C. Leignel N. Richard Haute École Bruxelles-Brabant École supérieure d’informatique License Ce document, et l’intégralité de son contenu, est sous licence Creative Com- mons « Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International (CC BY-NC-SA 4.0) », à l’exception des logos de la haute-école Bruxelles - Brabant (HE2B) et de l’école supérieure d’informatique (ESI), ainsi que les contenus issus des références listées dans la bibliographie qui, sont la propriété de leurs détenteurs respectifs. Le texte légal complet de cette licence peut être trouvé sur le site de Creative Commons 1. 1. https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode Première partie Mathématiques discrètes 1 CHAPITRE 1 Algèbre booléenne Propositions et opérateurs logiques • Calcul propositionnel et priorités des opérateurs logiques 1.1 Propositions et opérateurs logiques Déﬁnition 1.1 Une proposition est une aﬃrmation qui possède une valeur de vérité qui peut être soit vraie, soit fausse. A priori, cette déﬁnition n’a rien de « mathématique ». On peut l’utiliser dans tout contexte, comme en français dans l’exemple suivant. Exemple 1.1. Considérez les phrases suivantes : 1. « La carotte est un légume » est une proposition. Le légume est un concept clairement déﬁni, et cette proposition est vraie. 2. « La carotte est un moyen de locomotion » est une proposition. Elle est fausse : personne ne se déplace à dos de carotte. 3. « La carotte a bon goût » n’est pas une proposition. En eﬀet, la valeur de 3 4 Chapitre 1. Algèbre booléenne vérité de cette aﬃrmation dépend de qui mange la carotte. Cette aﬃrmation est subjective. 4. « Arrache cette carotte ! » et « Qu’est-ce qu’une carotte ? » ne sont pas des propositions. Ces phrases ne déclarent pas un fait, et n’ont pas de valeur de vérité. 5. « Il existe de la vie ailleurs dans l’univers » est une proposition. Elle possède une valeur de vérité : soit vrai, soit faux. Le fait qu’on ne puisse pas décider laquelle de ces valeurs est la bonne est sans importance. đ La suite de ce chapitre est dédiée à la complexiﬁcation de ce modèle. En parti- culier, on verra comment composer une proposition à partir d’autres propositions, comment introduire des variables dans une proposition, comment restreindre les valeurs de ces variables, etc. Ce modèle est très utilisé en logique propositionnelle, un formalisme utilisé dans de nombreuses disciplines mathématiques, telles que l’algèbre, l’analyse, l’arithmétique, etc. Dans cette logique, on raisonne la plupart du temps sur des compositions de propositions quelconques que l’on nomme p, q, r . . . Comme on ne connaît pas a priori la valeur de vérité de la proposition originale, ni de celles des sous-propositions p, q, r, etc., on doit envisager tous les cas de valeurs possibles. Cette énumération requiert l’utilisation de tables de vérité. Une table de vérité est simplement un tableau qui énumère toutes les possibi- lités de valeurs de vérité d’une proposition. Si une proposition p est composée de deux sous-propositions q et r, on y note les valeurs de vérité de q et r, et on en déduit la valeur de vérité de p. Ces valeurs sont notées V pour la valeur « vrai », et F pour la valeur « faux » 1. Exemple 1.2. Considérez une personne disant « Ce poisson a des dents et est rouge 2 ». C’est une proposition, car elle peut être soit vraie, soit fausse. Notons-la p. Elle est composée de deux sous-propositions. — Le poisson a des dents. Notons cette propriété q. 1. Notez que, parfois, « vrai » est noté comme le chiﬀre « 1 » et « faux » comme le chiﬀre « 0 ». Cette notation est souvent utilisée en électronique, notamment. 2. Les couleurs utilisées dans les exemples de ce cours sont considérées comme déﬁnies clairement à l’aide d’un code de 3 octets, comme dans la plupart des systèmes informatiques. En ce sens, elles ne sont pas sujettes à interprétation. 1.1 Propositions et opérateurs logiques 5 — Le poisson est rouge. Notons cette propriété r. On peut illustrer la table de vérité de cette proposition avec la table 1.1. q r p V V V V F F F V F F F F Table 1.1 – Table de vérité de p đ Les tables de vérité sont très utiles pour décrire les opérateurs logiques de base, tels que le « ou », le « et », etc. On utilisera le même formalisme que dans l’exemple précédent pour les illustrer : un tableau à deux dimensions, avec un V signiﬁant vrai, et un F signiﬁant faux. À ce titre, o déﬁnit les concepts de tautologie et d’antilogie. Déﬁnition 1.2 Une tautologie (resp. antilogie ou une contradiction) est une proposition toujours vraie (resp. fausse). Intuitivement, la valeur de vérité des tautologies (vrai) et des antilogie (faux) ne dépend pas des valeurs de vérité des propositions qui la composent. Visuelle- ment, la dernière colonne de la table de vérité d’une tautologie ne contient que des V , celle d’une antilogie ne contient que des F. Le très grand intérêt des tautologies est de fournir des méthodes de raison- nement sûres. Par exemple, lorsque l’on écrit ab “ 0 si et seulement si a “ 0 ou b “ 0, on déﬁnit en réalité une tautologie. Comme cette formule est toujours vraie quelle que soit la valeur de son contenu (en l’occurrence, les valeurs des variable a et b), développer le raisonnement de cette manière répond à la question originale (trouver a et b) de manière sûre. Dans la suite de cette section, on déﬁnit divers opérateurs logiques de base, 6 Chapitre 1. Algèbre booléenne avec leurs tables de vérité associées pour illustrer ces déﬁnitions. 1.1.1 Négation Intuitivement, la négation d’une proposition échange sa valeur de vérité. En français, cela correspond au contraire. Déﬁnition 1.3 La négation d’une proposition p est notée ␣p, et se lit « non p ». Si p est vrai, ␣p est faux, et inversement. La table 1.2 illustre la table de vérité de la négation d’une proposition p. p ␣p V F F V Table 1.2 – Table de vérité de la négation Exemple 1.3. Considérez la proposition « mon ordinateur a au moins 8GB de mémoire ». La négation de cette proposition est « il est faux que mon ordinateur a au moins 8GB de mémoire », ou mieux construit : « mon ordinateur a moins de 8GB de mémoire » 3. đ 1.1.2 Conjonction La conjonction de deux propositions impose à deux propositions d’être vraie pour que le résultat soit vrai. En français, cela correspond au « et ». Dans l’exemple 1.2, pour que le résultat soit vrai, il faut que le poisson ait des dents et qu’il soit rouge. 3. Notez qu’il est ambigu d’aﬃrmer que la négation est « mon ordinateur a au plus 8GB de mémoire », dans la mesure où cette proposition inclut l’ordinateur avec exactement 8 GB de mémoire. 1.1 Propositions et opérateurs logiques 7 Déﬁnition 1.4 La conjonction de deux propositions p et q est notée p ^ q et se lit « p et q ». Elle n’est vraie que si à la fois p et q sont vraies, et est fausse dans tous les autres cas. La table 1.3 illustre la table de vérité de la conjonction de deux propositions p et q. p q p ^ q V V V V F F F V F F F F Table 1.3 – Table de vérité de la conjonction Exemple 1.4. Soient les propositions p « il pleut » et q « le soleil brille ». La conjonction de ces deux propositions est, « il pleut et le soleil brille », ou encore « il pleut mais le soleil brille », ou même « le soleil brille mais il pleut ». đ 1.1.3 Disjonction La disjonction de deux propositions impose à au moins une de ces propo- sitions d’être vraie pour que le résultat soit vrai. En français, cela correspond généralement au « ou ». Par exemple, quand on aﬃrme « pendant les repas, je bois de l’eau ou du vin », le seul cas dans lequel on mentirait serait celui où on ne boirait ni eau, ni vin. En particulier, boire à la fois de l’eau et du vin n’est pas interdit par la proposition. Notez néanmoins que, parfois, le contexte en français va parfois rendre cette disjonction comme exclusive. En eﬀet, si une personne aﬃrme qu’elle va à la plage ou à la piscine, on ne s’attend pas à ce qu’elle se rende à ces deux activités. En mathématiques, elle pourrait très bien aller à la fois à la plage et à la piscine. 8 Chapitre 1. Algèbre booléenne Déﬁnition 1.5 La disjonction de deux propositions p et q est notée p _ q et se lit « p ou q ». Elle est vraie si au moins un de ses opérandes est vrai. L’opérateur _ uploads/Science et Technologie/ syllabus-de-theorie-version-courte 1 .pdf