Remerciez-le!

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

Introduction à la logique mathématique Encadré par: Mr Lâaroussi Gary Animé par

Introduction à la logique mathématique Encadré par: Mr Lâaroussi Gary Animé par: Mr Houssem Eddine Fitati Année scolaire 2012 – 2013 CREFOC-Radès Introduction: La logique mathématique, logique formelle ou méta- mathématique est une discipline des mathématiques introduite à la fin du XIXe siècle, qui s'est donnée comme objet l'étude des mathématiques en tant que langage. Les objets fondamentaux de la logique mathématique sont les formules modélisant les énoncés mathématiques, les dérivations ou démonstrations formelles modélisant les raisonnements mathématiques et les sémantiques ou modèles qui définissent le « sens » des formules (et parfois même des démonstrations) comme certains invariants : par exemple l'interprétation des formules du calcul des prédicats dans les structures permet de leur affecter une valeur de vérité. ( source wikipédia ) Introduction à la logique mathématique CREFOC Radès 2012~2013 2 Ça sert à quoi ? Introduction à la logique mathématique CREFOC Radès 2012~2013 3 Préambule Un résultat mathématique (ou une proposition) est un énoncé vrai. Suivant son importance, il est qualiﬁé de : • lemme : résultat d’une importance mineure, • théorème : résultat d’une importance majeure. Faire une démonstration (on dit aussi preuve), c’est réaliser un processus qui permet de passer de propositions supposées vraies prises comme hypothèses à une proposition appelée: concl sion et ce en tilisant les règles strictes de logiq e Introduction à la logique mathématique CREFOC Radès 2012~2013 4 Plan du cours Introduction à la logique mathématique CREFOC Radès 2012~2013 5 • Assertion et prédicat • Propriétés • Les connecteurs logiques • Les quantiﬁcateurs mathématiques • Différents modes de démonstration Assertion & prédicat Définitions et exemples Introduction à la logique mathématique CREFOC Radès 2012~2013 6 Assertion: • Définition: Une assertion est un énoncé mathématique auquel on peut attribuer la valeur de vérité: vraie (V) ou faux (F) mais jamais les deux à la fois. C’est le principe du tiers-exclu. • Exemple: § L’énoncé « 24 est un multiple de 2 » est vrai (V). § L’énoncé « 19 est un multiple de 2 » est faux (F). §L’énoncé « Tunis est la capitale de la Tunisie » est vrai (V). Introduction à la logique mathématique CREFOC Radès 2012~2013 7 Prédicat: • Définition: Un prédicat est un énoncé mathématique contenant des lettres appelées variables tel que quand on remplace chacune de ces variables par un élément donné d’un ensemble, on obtient une assertion. • Exemple: L’énoncé suivant : P(n) = « n est un multiple de 2 » est un prédicat car il devient une assertion quand on donne une valeur à n. § P(10) = « 10 est un multiple de 2 » est une assertion vraie, § P(11) = « 11 est un multiple de 2 » est une assertion f Introduction à la logique mathématique CREFOC Radès 2012~2013 8 • Remarque: Une assertion peut s’interpréter comme un prédicat sans variable, c’est-à-dire comme un prédicat toujours vrai ou toujours faux. Introduction à la logique mathématique CREFOC Radès 2012~2013 9 Les connecteurs logiques Négation, conjonction , disjonction , implication & équivalence. Introduction à la logique mathématique CREFOC Radès 2012~2013 10 Négation: Introduction à la logique mathématique CREFOC Radès 2012~2013 11 Les connecteurs logiques permettent de créer de nouveaux prédicats (dits prédicats composés) à partir de prédicats P, Q, Soit P un prédicat. La négation du prédicat P est le prédicat noté non(P) qui: § est vrai lorsque P est faux, § est faux lorsque P est vrai. P Non(P) V F F V Exemples: • L’assertion P = « 24 est un multiple de 2 » est une assertion vraie (V). L’assertion non(P) est déﬁnie par : non(P) = « 24 n’est pas un multiple de 2 ». C’est une assertion fausse (F). • A partir du prédicat « x ∈ A », on déﬁnie le prédicat non (x ∈ A) = « x /∉ A ». Par exemple, l’assertion « 1/2 ∉ Z » est vraie car l’assertion « 1/2 ∈ Z » est fausse. Introduction à la logique mathématique CREFOC Radès 2012~2013 12 Conjonction: Soient P et Q deux prédicats. Le prédicat « P et Q », appelé conjonction de P et de Q, est un prédicat qui: • est vrai lorsque P et Q sont vrais simultanément, • est faux dans tous les autres cas. On résume ceci dans la table de vérité: On écrit par fois : P⋀Q au lieu de P et Q. Introduction à la logique mathématique CREFOC Radès 2012~2013 13 P Q P et Q V V V F V F V F F F F F Disjonction: Soient P et Q deux prédicats. Le prédicat « P ou Q », appelé disjonction de P et de Q, est un prédicat qui: • est vrai lorsque l’un au mois des deux prédicat P et Q est vrais, • est faux lorsque les deux sont faux. On résume ceci dans la table de vérité: On écrit par fois : P ∨Q au lieu de P ou Q. Introduction à la logique mathématique CREFOC Radès 2012~2013 14 P Q P ou Q V V V F V V V F V F F F Exemple: On en déduit les deux assertions : Considérons les deux assertions P et Q suivantes : • P = « 10 est divisible par 2 », • Q = « 10 est divisible par 3 ». L’assertion P est vraie tandis que l’assertion Q est fausse. • P et Q = « 10 est divisible par 2 et 10 est divisible par 3 », • P ou Q = « 10 est divisible par 2 ou 10 est divisible par 3 ». L’assertion « P et Q » est une assertion fausse. En revanche, l’assertion « P ou Q » est une assertion vraie. Introduction à la logique mathématique CREFOC Radès 2012~2013 15 Implication: Soient P et Q deux prédicats. Le prédicat « P ⇒ Q » appelé implication de P vers Q est un prédicat qui: • est faux lorsque P est vrai et Q faux, • est vrai dans tous les autres cas. On résume ceci dans la table de vérité : • On dit que P est une condition suffisante pour Q. • Q ⇒ P s’appelle l’implication réciproque de P ⇒ Q. Introduction à la logique mathématique CREFOC Radès 2012~2013 16 P Q P Q V V V F V V V F F F F V Equivalence: Soient P et Q deux prédicats. Le prédicat « P ⇔ Q » appelé équivalence de P et de Q est un prédicat qui: • est vrai lorsque P et Q sont simultanément vrai ou faux, • est faux dans tous les autres cas. On résume ceci dans la table de vérité : • (P Q) et (Q R) se note: P Q R. • (P ⇔ Q) et (Q ⇔ R) se note: P ⇔ Q ⇔ R. Introduction à la logique mathématique CREFOC Radès 2012~2013 17 P Q P ⇔ Q V V V F V F V F F F F V Propriétés Équivalence , tautologie , prédicats incompatibles. Introduction à la logique mathématique CREFOC Radès 2012~2013 18 Équivalences: Soient R1 et R2 deux prédicats. Si • R1 est vrai lorsque R2 est vrai • R1 est faux lorsque R2 est faux Alors on dit que R1 et R2 sont de même table de vérité ou qu’ils sont logiquement équivalents, et on note R1 ≡ R2 . Dans le cas contraire on note: R1 ≢ R2 . Exemple: § Soit P un prédicat. Non(non(P))≡P. § Soit P et Q deux prédicats. P et ( P ou Q) ≡P. Introduction à la logique mathématique CREFOC Radès 2012~2013 19 Tautologie: Considérons un prédicat P. Ce prédicat peut prendre la valeur (de vérité) Vrai ou Faux. Considérons le prédicat composé : R = « P ou non (P) ». Ce prédicat est remarquable. En effet, R est toujours vrai et ce indépendamment de P. Vériﬁons-le : Le prédicat composé R est alors qualiﬁé de tautologie. Définition: Un prédicat composé R qui est vrai quelles que soient les valeurs de vérité des prédicats qui le composent, est appelé une tautologie. Introduction à la logique mathématique CREFOC Radès 2012~2013 20 P Non P P ou non P V F V F V V Prédicats incompatibles: Soit P un prédicat. Considérons le prédicat composé : « P et non (P) ». Ce prédicat est toujours faux. Vériﬁons-le : On dit que les prédicats P et non(P) sont incompatibles. Définition: On dit que deux prédicats composés sont incompatibles si leur conjonction est fausse quelles que soient les valeurs de vérité des prédicats qui les composent. Introduction à la logique mathématique CREFOC Radès 2012~2013 21 P Non P P et non P V F F F V F Propriétés incontournables: § Soit P et Q deux prédicats, on a les équivalences logiques suivantes: Non(P ou Q) ≡ non(P) et non(Q) Non(P et Q) ≡ non(P) ou non(Q) Ce sont les lois de Morgan pour les prédicats. § Soit P, Q et R trois prédicats, on uploads/Philosophie/ introduction-a-la-logique-mathematique.pdf