Remerciez-le!

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

Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 4 Chapitre 2 La logi

Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 4 Chapitre 2 La logique propositionnelle I. Introduction On appelle logique propositionnelle la partie de la logique qui traite des propositions. Les propositions (contrairement aux paradoxes) sont des affirmations qui ne peuvent être que vraies ou fausses. Par exemple: "le ciel est bleu", "les coquelicots sont jaunes", "2+2=4", "2+2=5", sont des propositions. L'un des buts de la logique propositionnelle est d'élaborer un calcul, que nous nommerons: calcul propositionnel. Cela entraîne que les propositions soient traitées comme des variables, donc désignées par des lettres (p, q, r, ...) et que l'on introduise des opérations permettant de combiner les valeurs de ces variables. Nous admettons que ces variables sont à valeurs dans l'ensemble {Vrai, Faux}, noté aussi {0, 1} La logique propositionnelle permet: − La représentation des propositions d'une manière formelle (le langage du calcul propositionnel) − Déduction de nouvelles propositions à partir d'autres propositions (système déductif) − Vérification de la validité des propositions d'une manière formelle (tables de vérité) II. Les paradoxes Le paradoxe en est une affirmation qui contient une contradiction logique (vraie et fausse en même temps), ou un raisonnement qui, bien que sans faille apparente, aboutit à une absurdité, ou encore une situation qui contredit l'intuition commune. Exemples: • Paradoxe de l'autoréférence Considérons la phrase suivante : "cette phrase est fausse". Si cette phrase est vraie, alors elle est fausse. Et si elle est fausse de par son contenu, alors elle est vraie. Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 5 • Paradoxe de Zénon d'Elée: La course à pied Pour atteindre la ligne d'arrivée, un coureur doit d'abord parcourir la moitié de la distance qui le sépare de cette ligne, puis la moitié de la distance restante, et ainsi de suite à l'infini. Le coureur ne terminera donc jamais la course. Ce paradoxe dit de "la dichotomie" (c'est à dire division par deux) veut montrer l'impossibilité du mouvement. Il tend à mettre en doute la vérité par un raisonnement logique. Cependant si on fait la somme (infinie) de toutes les distances du problème on trouve 1: 1/2+1/4+1/8+... La limite de cette suite vaut 1. Mais une limite est ce vers quoi on tend sans jamais l'atteindre... III. Le tiers exclu Toute proposition est soit vraie soit fausse. IV. Le langage du calcul propositionnel Définir un langage revient à définir: − Des symboles (alphabet) − Des expressions (formules) Soit Lp(¬,∧) un langage propositionnel IV.1. L'alphabet L'alphabet de Lp(¬,∧) se compose de trois classes de symboles: • Les symboles des variables propositionnelles : lettres majuscules avec ou sans indices (A, B, C, A1, A2,…) • Les symboles logiques ou connecteurs ¬,∧ • Les symboles impropres '(' et ')' IV.2. Les formules L'ensemble des formules de Lp(¬,∧) est défini inductivement de la manière suivante: − Toute variable propositionnelle est une formule atomique (simple) − Si α et β sont deux formules alors ¬α, α∧β sont des formules composées. Les lettres grecques sont utilisées pour représenter les noms des formules. Remarque: Le connecteur ∧ est binaire et le connecteur ¬ est unaire. V. Autres connecteurs Pour des raisons d'abréviation, nous avons introduit de nouveaux symboles logiques qui sont: ∨, →, ↔. Ces nouveaux connecteurs sont définis comme suit: Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 6 • α∨β=def ¬(¬α ∧ ¬β) • α→β=def ¬(α ∧ ¬β) • α↔β=def (α→β) ∧ ( β→α) =def ¬(α ∧ ¬β) ∧ ¬( β ∧ ¬α) Exemple: écrire (A→¬B) ∨ C dans le système Lp(¬,∧). VI. Priorité des connecteurs Certaines parenthèses sont inutiles et peuvent être supprimées lorsqu'on associe une priorité aux différents connecteurs: ( ) La plus à gauche, puis la plus interne ¬ Le plus interne d'abord ∧ ∨ Le plus à gauche d'abord ↔ Le plus à gauche d'abord Exemples: • ¬(¬(¬A))) s'écrira ¬¬¬A • ((α∧β)∨ γ) s'écrira α∧β∨ γ • (α → β) ↔ γ s'écrira α → β ↔ γ • (α ∧ β) ↔ γ s'écrira α ∧ β ↔ γ • (α ∨ (β ↔ γ)) s'écrira α ∨ (β ↔ γ) Exercice: En associant les énoncés élémentaires “Fayçal est étudiant”, “Omar est étudiant”, “Ali est étudiant” aux propositions p, q, r, respectivement, associer à chacun des énoncés suivants la formule propositionnelle qui lui correspond. (a) Fayçal et Omar sont étudiants (b) Fayçal ou Omar est étudiant (c) Exactement un seul parmi Fayçal et Omar est étudiant (d) Ni Fayçal ni Ali ne sont étudiants (e) Au moins l’un des trois n’est pas étudiant (f) Un seul parmi les trois n’est pas étudiant (g) Seulement deux, parmi les trois, sont étudiants (h)Si Fayçal est étudiant, Omar l’est (i)Fayçal est étudiant à condition qu'Ali le soit (j) Que Ali soit étudiant est une condition nécessaire et suffisante pour que Fayçal le soit Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 7 VII. Le système déductif : étude syntaxique Le système déductif de Lp(¬,∧) est basé sur quatre règles: deux règles pour le ∧ et deux règles pour le ¬. VII.1. Règles du ∧ Règle d'introduction Règle d'élimination α β α ∧ β α ∧ β α ∧ β α β VII.2. Règles du ¬ Règle d'introduction Règle d'élimination α ¬ ¬α ⊥ α ¬ α VII.3. Définition Une déduction dans le système déductif (¬, ∧) est un arbre utilisant les règles (I¬) , (E¬), (I∧) ,(E∧) Feuilles=hypothèses ou prémisses Racine=conclusion Notation: Γ est un ensemble de formules et β une formule • Γ⊦β : il existe une déduction β dont les prémisses non éliminées sont dans l'ensemble Γ. • Cas particulier: Γ=∅, ⊦β est appelé un théorème du calcul propositionnel. • {α1, α2, …, αn} ⊦β est équivalent à α1, α2, …, αn ⊦β • Γ∪α⊦β est équivalent à Γ, α⊦β Exercice: voir série TD I∧ E∧ E∧ I¬ E¬ Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 8 VIII. Etude sémantique En général, la sémantique étudie les rapports entre les signes d’un langage et les objets. Du point de vue extensionnel de la logique mathématique, la sémantique renvoie à l'étude de la façon dont les formules dénotent des valeurs de vérité. Les valeurs de vérité sont des objets qui n’appartiennent pas à notre langage logique L, mais dont on se sert pour parler de L. Dans la logique classique que nous étudions ici, il n’y a que deux valeurs de vérité, le vrai et le faux. VIII.I. Table de vérité C'est un énorme avantage de n'avoir que deux valeurs. En effet, si n propositions p1, p2, ..., pn entrent dans la définition d'un même "état de choses" (ou, dira‐t‐on de manière imagée: d'un même "monde possible"), celui‐ci est complètement caractérisé par une situation des valeurs de vérité de ces propositions parmi 2n possibles. Ainsi si nous avons 3 propositions: p, q, r, elles déterminent un ensemble de 2×2×2 situations a priori possibles, qui seront modélisées sous forme d'une table appelée Table de vérité. La table de vérité d'une formule α contenant n variables propositionnelles A1,…, An est composée de 2n+1 lignes et (n+m) colonnes: n colonnes pour les n variables propositionnelles et m colonnes pour les m sous‐formules de α. Chaque ligne est appelée une instanciation. On définit une fonction de valuation V : {A1,….,An} { V,F } On dit que α est satisfiable s'il existe une valuation pour laquelle α est vraie. Nous associons à chaque connecteur du langage Lp(¬,∧) une table de vérité. VIII.1.a. Table du connecteur ¬ A ¬A V F F V VIII.1.b. Table des connecteurs ∧, ∨ , → , ↔ A B A ∧ B A ∨ B A → B A ↔ B V V V V V V V F F V F F F V F V V F F F F F V V Exercice: Définir la table de vérité de: • (p ∧ q) ∧ r • (p ∧ (q ∧ r) • (p → q) → r • p → (q → r) • (p → q) ∧ (q → r) Notes de Cours de logique mathématique Par Dr S. BOUYAKOUB 9 Remarque: Si α et β sont des formules alors: • α ∧ β=V ⇔ α=V et β=V • α ∨ β=F ⇔ α=F et β=F • α → β=F ⇔ α=V et β=F • α → β=V ⇔ α=F ou β=V • α ↔ β=V ⇔ (α=V et β=V) ou (α=F et β=F) : α et β ont la même valeur de vérité VIII.2. Tautologie, antilogie VIII.2.a. Définition Une formule α est appelée Tautologie (et on note ⊨α) si quelle que soit la valuation V on a V(α)=vrai. En d'autres termes, dans la table de vérité il n'y a que la valeur vrai comme résultat. Remarque: Si α et β sont deux formules alors: • ⊨ α ⇔ toutes les valuations satisfont α • ⊨¬α ⇔ aucune valuation ne satisfait α, α est une antilogie. • ⊭ α ⇔ α n'est pas une tautologie (il existe au moins une valuation qui ne satisfait pas α. uploads/Philosophie/ cours-logique-mathematique-chapitre-2-logique-propositionnelle.pdf