Remerciez-le!

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

Objectif du cours L’objectif général de ce cours est de faire connaître aux étu

Objectif du cours L’objectif général de ce cours est de faire connaître aux étudiants des bases de la logique mathématique, modes de raisonnement logique, des notions de relations binaires sur les ensembles qui sont des fondements pour les mathématiques et l’in- formatique. A la ﬁn de ce cours, l’étudiant doit être capable de : 1. D’établir des tables de vérités ; 2. Traduire certaines expressions, à l’aide des connecteurs ou quantiﬁcateurs lo- giques ; 3. Savoir appliquer des modes de raisonnement logique ; 4. Appliquer des propriétés des ensembles ; 5. Reconnaitre des applications injectives, des applications surjectives, des appli- cations bijectives ; 6. Savoir justiﬁer qu’une relation binaire sur un ensemble est une relation d’équi- valence et savoir d’éterminer les classes d’équivalence ; 7. Savoir justiﬁer qu’une relation binaire sur un ensemble est une relation d’ordre Chapitre 1 Éléments de logique Sommaire 1.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Connecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 La négation . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 La conjonction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 La disjonction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.4 L’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.5 L’implication logique . . . . . . . . . . . . . . . . . . . . . 4 1.3 Quantiﬁcateurs et Règle générale d’application . . . . . 5 1.3.1 Quantiﬁcateurs . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.2 Règle générale d’application . . . . . . . . . . . . . . . . . 6 1.4 Quelques formes de raisonnement . . . . . . . . . . . . . 6 1.4.1 Raisonnement par implication . . . . . . . . . . . . . . . . 6 1.4.2 Raisonnement par équivalence . . . . . . . . . . . . . . . . 7 1.4.3 Le raisonnement par l’absurde . . . . . . . . . . . . . . . 7 1.4.4 Raisonnement par récurrence . . . . . . . . . . . . . . . . 7 1.4.5 Raisonnement par contre-exemple . . . . . . . . . . . . . 8 1.1 Propositions Déﬁnition 1.1.1 Une proposition P est un énoncé qui est vrai dans certaines conditions, faux dans d’autres, mais dont on peut décider dans toute situation don- née, s’il est vrai ou faux. On attribue donc, à chaque situation donnée, l’une des valeurs de vérité • V (vrai) ou • F (Faux) à la proposition P. 2 CHAPITRE 1. ÉLÉMENTS DE LOGIQUE 3 Exemple : • P < Le Liberia est un pays de l’Afrique > est un énoncé vrai. • Q < Pour tout entier naturel n il existe un entier naturel m tel que m2 = n >. La proposition Q est fausse. • R < Quelle belle maison ! >. L’énoncé R n’est pas une proposition. • < Il a fait beau le jour J > n’est pas une proposition car les critères de déci- son sont insuﬃsants. Notons que certaines propositions sont considérées comme vérité absolue, qui ne se déduisent pas d’autres propositions vraies, elles traduisent, dans certains cas des propriétés évidentes. On les appelle des axiomes. Par exemple l’énoncé suivant est un axiome de la Géométrie euclidienne. < Par deux points distincts du plan, il passe une droitre et une seule >. Étant donnée une proposition, on est souvent amené à déterminer si elle est vraie ou fausse. On regroupe diverses propositions de la façon suivante : 1.2 Connecteurs Si P, Q, R, . . . sont des propositions, tout énoncé formé à partir de ces propo- sitions et des liaisons et, ou, non est encore une proposition puisqu’on peut, dans chaque situation, décider de sa vérité. Cette grammaire des propositions se mathématise à l’aide de signes que l’on nomme connecteurs. 1.2.1 La négation La négation d’une proposition P est notée non(P) (ou bien ⌉P). La négation d’une proposition P vraie sera fausse et la négation d’une proposition P fausse sera vraie. On a la table de vérité suivante P ⌉P V F F V 1.2.2 La conjonction La conjonction (P et Q) est une pro- position qui est vraie si et seulement si les deux propositions P et Q sont simul- tanément vraies. On la note aussi P ∧Q. La table de vérité correspondante est P Q P ∧Q V V V V F F F V F F F F CHAPITRE 1. ÉLÉMENTS DE LOGIQUE 4 1.2.3 La disjonction (P ou Q) est une proposition qui est vraie si et seulement si au moins une des deux propositions P et Q est vraie. (Les deux peuvent être vraies). Le "ou" a un sens inclusif. On a la table de vérité suivantes. P Q P ∨Q V V V V F V F V V F F F 1.2.4 L’équivalence L’équivalence (P ⇔ Q) est une proposition qui est vraie si et seulement si P et Q sont simultanément vraies ou simultanément fausses, autrement dit si P et Q ont la même valeur de vérité. On a la table de vérité suivante. P Q P ⇔Q V V V V F F F V F F F V Exemple : , soit x, y ∈R, x = exp(y) ⇔ (x > 0 et y = ln(x)). 1.2.5 L’implication logique L’implication logique (P ⇒Q) est une proposition qui est vraie si et seule- ment si P est fausse ou Q est vraie : P ⇒Q) ⇔ (non(P) ou Q) Cette notion est la plus diﬃcile à maî- triser, contrairement à ce que l’on peut penser au premier abord. On a la table de vérité suivante P Q P ⇒Q V V V V F F F V V F F V 1. La négation de (P et Q) est (non(P) ou non(Q)). En eﬀet, dire que (P et Q) est fausse, c’est dire que l’une au moins des deux propositions est fausse. 2. La négation de (P ou Q) est (non(P) et non(Q)). En eﬀet, nier que l’une au moins des deux propositions est vraie, c’est dire qu’elles sont toutes les deux fausses. CHAPITRE 1. ÉLÉMENTS DE LOGIQUE 5 3. La négation de (P ⇒ Q) est (P et non(Q)). En eﬀet, nous avons vu que P ⇒ Q est synonyme de (non(P) ou Q). La négation est donc bien (P et non(Q)). Dire que l’implication est fausse, c’est donc dire que l’on a l’hypothèse P mais pas la conclusion Q. 4. La négation de (P ⇔ Q) est ((P et non(Q)) ou (Q et non(P))). Propriétés 1 Les propriétés suivantes dérivent de ce qui précède. 1. P ∨P ≡P. 2. P ∨Q ≡Q ∨P. 3. (P ∨Q) ∨R ≡P ∨(Q ∨R). 4. P ∧P ≡P. 5. P ∧Q ≡Q ∧P. 6. (P ∧Q) ∧R ≡P ∧(Q ∧R). 7. P ∨(Q ∧R) ≡(P ∨Q) ∧(P ∨R). 8. P ∧(Q ∨R) ≡(P ∧Q) ∨(P ∧R). 9. P ⇒Q ≡⌉P ∨Q. 10. ⌉(P ∨Q) ≡⌉P∧⌉Q. 11. ⌉(P ∧Q) ≡⌉P ∨⌉Q. 12. P ⇒Q ≡⌉Q ⇒⌉P. 13. (P ⇒Q et Q ⇒R) ⇒(P ⇒R). 14. (P ⇔Q et Q ⇔R) ⇒(P ⇔R). Le lecteur est prié de s’en convaincre via les tables de vérités. Remarque 1.2.1 Il n’est pas diﬃcile de prouver que (P ⇔Q) ≡(P ⇒Q et Q ⇒P) 1.3 Quantiﬁcateurs et Règle générale d’applica- tion 1.3.1 Quantiﬁcateurs Considérons à présent une proposition P qui dépend de la variable x appartenant à un domaine E. On notera P(x) pour dire que P dépend de x. Pour exprimer que la proposition P est vraie pour au moins un élément x du domaine E, on écrit ∃x ∈E, P(x) . Le symbole ∃est appelé quantiﬁcateur existentiel. Pour exprimer que la proposition P est vraie pour tout les éléments x du domaine E, on écrit ∀x ∈E, P(x) . Le symbole ∀est appelé quantiﬁcateur universel. 1) La négation de ∀x, P(x) est ∃x, non(P(x)). En eﬀet, dire qu’il est faux que P(x) soit vraie pour tout x, c’est dire que P(x) est fausse pour au moins uploads/Philosophie/ akeke-cours-l-1-maths-info-logiquemathematique-pdf.pdf