Remerciez-le!

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

Chapitre 1 Logique Un scientiﬁque étudie des objets, à propos desquels il énonc

Chapitre 1 Logique Un scientiﬁque étudie des objets, à propos desquels il énonce des faits (ou propositions). La logique manipule de façon formelle les propositions. Elle permet de modéliser les bases élémen- taires du raisonnement. Il est important de souligner que la logique est utile dans toute démarche scientiﬁque. En revanche, dans le langage courant (dit langage vernaculaire), la logique ne s’applique pas toujours. Cela peut poser problème car les livres et les articles scientiﬁques (ainsi que les copies des étudiants !) sont rédigés en langage vernaculaire, et pas dans un langage formel. Il faut donc s’eﬀorcer d’être parfaitement clair quand on rédige un texte scientiﬁque. Déﬁnition. En logique, une proposition (ou assertion) est une phrase à laquelle on peut attribuer une valeur de vérité (vrai ou faux). On note 1 le vrai, et 0 le faux. Exemple. « π est un nombre entier » est une assertion fausse. « 18 est divisible par 3 » est une assertion vraie. Remarque. a) La phrase « cette assertion est fausse » n’est ni vraie, ni fausse. Ce n’est donc pas une assertion logique. Ce paradoxe est comparable à un individu aﬃrmant « je mens » : il est logiquement impossible de savoir si cet individu dit ou non la vérité. C’est le paradoxe du menteur. b) Mentionnons aussi le paradoxe de Berry : soit E l’ensemble des entiers naturels descriptibles par une phrase (en français) de quinze mots ou moins. Alors E est un ensemble ﬁni (il n’y a qu’un nombre ﬁni de phrases de quinze mots ou moins). Soit n0 le plus petit entier n’appartenant pas à E. Alors n0 est déﬁni de façon unique par la phrase « Le plus petit entier non descriptible par une phrase de moins de quinze mots ». Or cette phrase comporte 14 mots, donc n0 appartient à E, ce qui constitue un paradoxe. Celui-ci ne dévoile aucune incohérence des mathématiques, mais prouve tout simplement que n’importe quelle phrase ne peut être considérée comme une assertion mathématique. 1.1 Connecteurs logiques Soient P et Q deux propositions. Les connecteurs logiques sont : 1) La conjonction : « et » (notée ∧) P ∧Q signiﬁe que P est vraie et Q est vraie. 3 2) La disjonction : « ou » (notée ∨) P ∨Q signiﬁe que au moins l’une des deux propositions P ou Q est vraie. 3) La négation : « non » (notée ¬) ¬P signiﬁe que P est fausse. 4) L’implication (notée ⇒) P ⇒Q signiﬁe que si P est vraie, alors Q est vraie. 5) L’équivalence (notée ⇔) P ⇔Q signiﬁe que P et Q ont même valeur de vérité. Remarque. a) Dans le langage courant, « ou » a en général un sens exclusif (fromage « ou » dessert). En mathématiques, le « ou » est toujours inclusif : si P et Q sont toutes les deux vraies, alors P ∨Q est vraie. b) Le seul cas où P ⇒Q est fausse se produit quand P est vraie et Q est fausse. En mathé- matiques, un résultat vrai n’implique jamais un résultat faux. c) En revanche, si P est fausse, alors P ⇒Q est toujours vraie, quelle que soit la valeur de vérité de Q. On raconte, qu’intrigué par ce résultat, un philosophe interpella ainsi Bertrand Russell : « Voulez-vous dire que si 2 = 1, alors vous êtes le pape ? ». « Bien sûr », répondit Russell. « En eﬀet, le pape et moi sont deux personnes distinctes et deux égale un, donc le pape et moi sont la même personne ». Les connecteurs logiques permettent de combiner des assertions données P, Q, R, . . . pour construire de nouvelles assertions, dites composées, dont on peut déterminer la valeur de vérité à partir des valeurs de vérité de P, Q, R, . . . . 1.2 Tables de vérité Pour manipuler une assertion composée, on peut tout simplement parcourir la liste complète des valeurs de vérité possibles des assertions qui ont servi à la construire, qui n’est en général pas très longue. Ceci permet de remplacer un raisonnement par une simple vériﬁcation mécanique, exécutable par ordinateur. Les tables ci-dessous, qui décrivent les connecteurs logiques, servent de point de départ à ces vériﬁcations. P Q P ∧Q P ∨Q P ⇒Q P ⇔Q 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 P ¬P 0 1 1 0 Exemple. Si P et Q sont deux assertions, alors P ⇒Q est équivalente à (¬P) ∨Q. En eﬀet, on peut vériﬁer cela à l’aide d’une table de vérité : P Q P ⇒Q ¬P (¬P) ∨Q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 Ainsi l’assertion (P ⇒Q) ⇔((¬P) ∨Q) est toujours vraie, quelles que soient les valeurs de vérité rattachées aux assertions P et Q. On qualiﬁe un tel énoncé de tautologie. 4 1.3 Règles logiques Il existe en logique un certain nombre de règles qui établissent un calcul des propositions, semblable au calcul algébrique. Après application de l’une de ces règles sur une assertion, on obtient une assertion équivalente, c’est-à-dire ayant la même valeur de vérité. Propriété. Soient P, Q et R trois assertions. Alors : 1. (¬(¬P)) ⇔P 2. (P ∧P) ⇔P et (P ∨P) ⇔P 3. (P ⇒Q) ⇔(¬Q ⇒¬P) 4. ¬(P ∧Q) ⇔(¬P ∨¬Q) 5. ¬(P ∨Q) ⇔(¬P ∧¬Q) 6. ¬(P ⇒Q) ⇔(P ∧¬Q) 7. P ∧(Q ∨R) ⇔(P ∧Q) ∨(P ∧R) 8. P ∨(Q ∧R) ⇔(P ∨Q) ∧(P ∨R) Démonstration. Ces règles sont des tautologies, qui se vériﬁent avec une table de vérité. Remarque. a) Étant donnée une implication P ⇒Q, on dit que : • l’implication Q ⇒P est sa réciproque ; • l’implication ¬Q ⇒¬P est sa contraposée. La règle 3. aﬃrme qu’une implication est équivalente à sa contraposée. Par contre, il n’y a en général aucun lien logique entre une implication et sa réciproque : il se peut que l’une soit vraie et l’autre fausse. b) Les règles 4. et 5. sont appelées lois de De Morgan en l’honneur du mathématicien britan- nique Augustus De Morgan (1806-1871). c) La règle 6. est très importante à retenir, car elle permet d’écrire la négation d’une impli- cation. 1.4 Quantiﬁcateurs Déﬁnition. Un prédicat (ou formule à une variable) sur un ensemble E est un procédé qui associe à chaque élément de E une assertion. Exemple. La phrase « x est pair » est un prédicat sur l’ensemble N des entiers naturels. Ce prédicat associe à l’entier 4 une assertion vraie, et à l’entier 5 une assertion fausse. Pour transformer un prédicat en proposition, on utilise un quantiﬁcateur. Soient E un en- semble, et P un prédicat sur E. (1) Quantiﬁcateur universel : ∀x ∈E, P(x) signiﬁe que, pour tout élément x de E, l’assertion P(x) est vraie. (2) Quantiﬁcateur existentiel : ∃x ∈E, P(x) signiﬁe qu’il existe au moins un élément x de E tel que P(x) soit vraie. Il convient également de signaler le quantiﬁcateur « d’existence et d’unicité », d’usage moins courant que les deux précédents. 5 (3) ∃!x ∈E, P(x) signiﬁe qu’il existe un unique élément x de E tel que P(x) soit vraie. Remarque. Les variables quantiﬁées sont muettes, c’est-à-dire que ∀x ∈E, P(x) est la même assertion que ∀β ∈E, P(β). Exemple. L’assertion (vraie) « Tout nombre réel strictement positif a une racine cubique réelle strictement positive » s’écrit : ∀x ∈]0, +∞[, ∃y ∈]0, +∞[, y3 = x Attention à l’ordre des quantiﬁcateurs. En eﬀet : ∃y ∈]0, +∞[, ∀x ∈]0, +∞[, y3 = x est une assertion tout à fait diﬀérente de la précédente (et fausse). Remarque. a) Si E est vide, alors ∀x ∈E, P(x) est vraie, et ∃x ∈E, P(x) est fausse. b) Si E = {x1, . . . , xn} est un ensemble ﬁni, alors ∀x ∈E, P(x) est équivalente à P(x1) ∧ · · · ∧P(xn). De même, ∃x ∈E, P(x) est équivalente à P(x1) ∨· · · ∨P(xn). c) Une assertion de la forme ∃x ∈E, P(x) peut être vraie sans qu’on ait aucun moyen de construire eﬀectivement un élément x de E tel que P(x) soit vraie. Par exemple, l’assertion « il existe des banquiers honnêtes » ne constitue pas une information très substantielle, car elle ne permet pas, à elle seule, de fournir un exemple. 1.5 Négation et quantiﬁcateurs Propriété. Soient E un ensemble, et P un prédicat sur E. Alors : (1) ¬(∀x ∈E, P(x)) ⇔(∃x ∈E, ¬P(x)) (2) ¬(∃x ∈E, P(x)) ⇔(∀x ∈E, ¬P(x)) Exemple. L’assertion ¬(∃x ∈R, x2 = −1) peut se réécrire (∀x ∈R, x2 ̸= −1). Le quantiﬁcateur universel pouvant être vu comme une généralisation de la conjonction et le quantiﬁcateur existentiel pouvant être vu comme une généralisation de la disjonction, ces règles de négation des quantiﬁcateurs généralisent les lois de De Morgan. 1.6 Démonstrations En mathématiques, démontrer un résultat, c’est se convaincre de sa validité par uploads/Philosophie/ cours-algebre-cpp.pdf