Remerciez-le!

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

1 Éléments de logique et de théorie des ensembles Pour les exemples et exercice

1 Éléments de logique et de théorie des ensembles Pour les exemples et exercices traités dans ce chapitre les ensembles usuels de nombres entiers, rationnels réels et complexes sont supposés connus, au moins de manière intuitive comme cela se passe au Lycée. Nous reviendrons plus loin sur les constructions de ces ensembles. 1.1 Quelques notions de logique Nous allons préciser à un premier niveau quelques notions mathématiques qui sont relative- ment intuitives mais nécessitent quand même des déﬁnitions rigoureuses. L’idée étant de préciser schématiquement comment se présente une théorie mathématique ainsi que la notion essentielle de démonstration. La première notion est celle d’assertion. De manière intuitive, une assertion est un énoncé mathématique aussi rigoureux que possible qui ne peut prendre que deux valeurs de vérité à savoir « vrai » ou « faux » mais jamais entre les deux comme dans le langage courant. Une assertion qui est toujours vraie est une tautologie. Par exemple les énoncés suivantes sont des assertions : 2 < 15 (elle est vraie), √ 2 est un nombre rationnel (elle est fausse), cos(nπ) = (−1)n (vraie), ... Deux assertions sont dites logiquement équivalentes, ou plus simplement équivalentes, si elles sont toutes deux vraies ou toutes deux fausses. Il y a ensuite les énoncés qui se démontrent. Pour ce faire, on se donne des règles précises (que nous verrons par la pratique) qui permettent de construire de nouvelles assertions à partir d’assertions données. Remarque 1.1 Il ne faut pas croire que dans une théorie donnée toute assertion P soit obli- gatoirement démontrable. En 1931 Kurt Gödel à démontré qu’il y a des assertions non démon- trables (on dit aussi qu’elles sont indécidables) : il n’est pas possible de démontrer que P est vraie ni que P est fausse. À la base de toute théorie mathématique, on dispose d’un petit nombre d’assertions qui sont supposés vraies à priori (c’est-à-dire avant toute expérience) et que l’on nomme axiomes ou postulats. Ces axiomes sont élaborés par abstraction à partir de l’intuition et ne sont pas déduits d’autres relations. Par exemple, la géométrie euclidienne est basée sur une quinzaine d’axiomes. L’un de ces axiomes est le postulat numéro 15 qui aﬃrme que par un point donné passe une et une seule droite parallèle à une droite donnée. 3 4 Éléments de logique et de théorie des ensembles Une autre exemple important est donné par la construction de l’ensemble noté N des entiers naturels. Cette construction peut se faire en utilisant les axiomes de Peano suivants : – 0 est un entier naturel ; – tout entier naturel n a un unique successeur noté n + 1 ; – deux entiers naturels ayant même successeur sont égaux ; – une partie P de N qui contient 0 et telle que si n est dans P alors le successeur de n y est aussi, est égale à N (axiome de récurrence). Nous reviendrons au paragraphe 1.6 sur l’ensemble N en partant sur une autre base. La théorie des ensemble est basée sur le système d’axiomes de Zermelo-Fränkel. La notion de déﬁnition nous permet de décrire un objet ou une situation précise à l’aide du langage courant. Les énoncés qui se démontrent sont classés en fonction de leur importance dans une théorie comme suit : – un théorème est une assertion vraie déduite d’autres assertions, il s’agit en général d’un résultat important à retenir ; – un lemme est un résultat préliminaire utilisé pour démontrer un théorème ; – un corollaire est une conséquence importante d’un théorème ; – une proposition est de manière générale un résultat auquel on peut attribuer la valeur vraie ou fausse sans ambiguïté. Pour rédiger un énoncé mathématique, on utilise le langage courant et les objets manipulés sont représentés en général par des lettres de l’alphabet latin ou grec. Usuellement, on utilise : – les lettres minuscules a, b, c, ... pour des objets ﬁxés ; – les lettres minuscules x, y, z, t, ... pour des objets inconnus à déterminer ; – les lettres majuscules E, F, G, H, ... pour des ensembles ; – des lettres de l’alphabet grecques minuscules ou majuscules α, β, ε, δ, ... Λ, Γ, Ω, ... 1.2 Les connecteurs logiques de base L’élaboration de nouvelles assertions à partir d’autres se fait en utilisant les connecteurs lo- giques de négation, de conjonction, de disjonction, d’implication et d’équivalence déﬁnis comme suit, où P et Q désignent des assertions. – La négation de P, notée ¬P, ou non P ou P, est l’assertion qui est vraie si P est fausse et fausse si P est vraie. Par exemple la négation de l’assertion : « x est strictement positif » est « x est négatif ou nul ». En théorie des ensembles on admet qu’il n’existe pas d’assertion P telle que P et P soient toutes deux vraies. On dit que cette théorie est non contradictoire. – La conjonction de P et Q, notée P ∧Q (lire P et Q), est l’assertion qui est vraie uniquement si P et Q sont toutes deux vraies (et donc fausse dans les trois autres cas). Par exemple P ∧P est toujours faux (on se place dans des théories non contradictoires). – La disjonction de P et Q, notée P ∨Q (lire P ou Q), est l’assertion qui est vraie uniquement si l’une des deux assertions P ou Q est vraie (donc fausse si P et Q sont toutes deux fausses). Par exemple P ∨P est toujours vraie (c’est une tautologie). Il faut remarquer que le « ou » pour « ou bien » est inclusif, c’est-à-dire que P et Q peuvent être toutes deux vrais dans le cas où P ∨Q est vraie. On peut aussi introduire le « ou exclusif », noté W, qui est vrai uniquement lorsque l’une des deux assertions, mais pas les deux simultanément, est vraie. Les connecteurs logiques de base 5 – L’implication, notée P →Q, est l’assertion qui est fausse uniquement si P est vraie et Q fausse (donc vraie dans les trois autres cas). On peut remarquer que si P est fausse, alors P →Q est vraie indépendamment de la valeur de vérité de Q. L’implication est à la base du raisonnement mathématique. En partant d’une assertion P (ou de plusieurs), une démonstration aboutit à un résultat Q. Si cette démonstration est faite sans erreur, alors P →Q est vraie et on notera P ⇒Q (ce qui signiﬁe que si P est vraie, alors Q est vraie). Dans ce cas, on dit que P est une condition suﬃsante et Q une condition nécessaire. On peut remarquer que l’implication est transitive, c’est-à-dire que si P implique Q et Q implique R, alors P implique R. – L’équivalence de P et Q, notée P ↔Q, est l’assertion qui est vraie uniquement si P →Q et Q →P sont toutes deux vraies. Dans le cas où P ↔Q est vraie on dit que P est Q sont équivalentes et on note P ⇔Q (ce qui signiﬁe que P et Q sont, soit toutes deux vraies, soit toutes deux fausses). Dans ce cas, on dit que Q est une condition nécessaire et suﬃsante de P. On peut résumer ce qui précède, en utilisant la table de vérité suivante : P Q P P ∧Q P ∨Q P →Q P ↔Q V V F V V V V V F F F V F F F V V F V V F F F V F F V V Les tables de vérité peuvent être utilisées pour faire certaines démonstrations. On rappelle que deux assertions qui ont même table de vérité sont équivalentes. Avec le théorème qui suit, on résume quelques règles de calcul. Théorème 1.1 Soient P, Q, R des propositions. On a les équivalences : 1. commutativité : (P ∧Q) ⇔(Q ∧P) (P ∨Q) ⇔(Q ∨P) 2. associativité (P ∧(Q ∧R)) ⇔((P ∧Q) ∧R) (P ∨(Q ∨R)) ⇔((P ∨Q) ∨R) 3. distributivité : (P ∧(Q ∨R)) ⇔((P ∧Q) ∨(P ∧R)) (P ∨(Q ∧R)) ⇔((P ∨Q) ∧(P ∨R)) 4. négations : ³ P ´ ⇔(P) ¡ P ∧Q ¢ ⇔ ¡ P ∨Q ¢ ¡ P ∨Q ¢ ⇔ ¡ P ∧Q ¢ (P →Q) ⇔ ¡ Q →P ¢ (P →Q) ⇔ ¡ P ∨Q ¢ ¡ P →Q ¢ ⇔ ¡ P ∧Q ¢ 6 Éléments de logique et de théorie des ensembles Démonstration. On utilise les tables de vérité (exercices). Les équivalences ¡ P ∧Q ¢ ⇔ ¡ P ∨Q ¢ et ¡ P ∨Q ¢ ⇔ ¡ P ∧Q ¢ sont appelées lois de Morgan. Exercice 1.1 Montrer que les assertions P →Q et P ∨Q sont équivalentes. Solution 1.1 On montre qu’elles ont même table de vérité. P Q P P ∨Q P →Q V V F V V V F F F F F V V V V F F V V V Exercice 1.2 Montrer que les assertions P →Q et P ∧Q sont équivalentes. Solution 1.2 On montre qu’elles ont même table de vérité. P Q P uploads/Philosophie/ algebre-chap1.pdf