Cours 1 : Logique des propositions (1) PDF

I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI Cours 1 : Logique des propositions (1) I. Introduction : 1. Qu’est ce que la logique ? « Logique » est un mot provenant...

I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI Cours 1 : Logique des propositions (1) I. Introduction : 1. Qu’est ce que la logique ? « Logique » est un mot provenant du grec logos qui signifie « science de la raison ». La logique étudie le discours, et plus particulièrement le(s) raisonnement(s). Le but de la logique est de calculer des conclusions sûres. Le langage naturel s’avère trop imprécis et riche pour permettre des développements simples et rigoureux. La logique est un outil pour parler et raisonner dans un domaine déterminé. Différents domaines ont différentes logiques. C’est un problème à la fois philosophique et mathématique que de savoir si une logique donnée est adéquate pour un domaine particulier. Dans le 19ième siècle :  la logique devient un outil scientifique (Boole, Hilbert…).  Formaliser les mathématiques comme un langage.  Formaliser le concept de démonstration. Cours 1 : Logique des propositions (1)  Spécifier des propriétés de systèmes informatiques de manière précise et rigoureuse : c’est cet aspect qui va nous intéresser. La « Logique » par rapport à l'Informatique, a 2 rôles : a. rôle fondateur : la Logique est le « calcul de l'informatique » :  une fondation mathématique pour traiter les informations, et le raisonnement sur le comportement des logiciels. Exemple : définir proprement la notion de problème ayant une solution.  elle fournit également une bonne formation dans le raisonnement correct et précis, la description sans ambiguïté. b. rôle interne : Modéliser, spécifier, vérifier, raisonner automatiquement. Le but de ce cours est d’étudier en détail les fondements de la logique classique et de donner aux étudiants une formation suffisante pour qu’ils puissent se familiariser avec d’autres logiques (intuitionniste ou floue) qu’ils peuvent rencontrer plus tard. Et également les Page 1 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI sensibiliser au fait que la logique peut être très utile pour automatiser/semi automatiser les tâches de raisonnement rencontrées lors de la construction/l’analyse de modèles et de programmes. 2. Exemples : Exemple 1 : Considérons la situation décrite par les affirmations suivantes : 1. Si le train arrive en retard et il n’y a pas de taxis à la gare alors l’invité arrive en retard. 2. L’invité n’est pas en retard. 3. Le train est arrivé en retard. Et la déduction suivante : il y avait des taxis à la gare. Question : Pourquoi peut-on déduire qu’il y avait des taxis à la gare ?  Si on met l’affirmation 1 et l’affirmation 3 ensemble, on peut affirmer que s’il n’y avait pas eu de taxis à la gare, alors l’invité serait arrivé en retard. D’après l’affirmation 2, l’invité n’est pas arrivé en retard. Donc il y avait des taxis à la gare. Exemple 2 : Considérons la situation décrite par les affirmations suivantes : Cours 1 : Logique des propositions (1) 1. Si il pleut et l’invité a oublié son parapluie alors l’invité est trempé. 2. L’invité n’est pas trempé. 3. Il pleut. Et la déduction suivante : L’invité n’a pas oubli´e son parapluie. Question : Pourquoi peut-on déduire que l’invité n’a pas oublié son parapluie ?  Si on met l’affirmation 1 et l’affirmation 3 ensemble, on peut affirmer que si l’invité avait oubli´e son parapluie, alors il serait trempé. D’après l’affirmation 2, l’invité n’est pas trempé. Donc l’invité n’a pas oublié son parapluie. Remarque : La deuxième démonstration suit la même structure logique que la première démonstration. Il suffit de remplacer les fragments de phrase. Page 2 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI Exemple du train Exemple du parapluie Le train est arrivé en retard Il pleut Comme suit : Il y a des taxis à la gare L’invité a son parapluie L’invité est en retard L’invité est mouillé. Exemple du train Exemple du parapluie Proposition Le train est arrivé en retard Il pleut p Il y a des taxis à la gare L’invité a son parapluie q L’invité est en retard L’invité est mouillé. r Démonstration 1 : 1. Hypothèse : si p et non q, alors r 2. Hypothèse : p 3. Hypothèse : non r 4. Déduction : si non q alors r 5. Déduction : comme non r, alors q. Cours 1 : Logique des propositions (1) 3. Donc, qu'est-ce que un système logique ? Un Système Logique se compose généralement de trois choses : 1) Syntaxe : un langage formel (tel qu'un langage de programmation) qui sera utilisé pour exprimer des concepts 2) Sémantique : fournit la signification du langage formel 3) Théorie de la preuve : mécanisme purement syntaxique d'obtenir ou d'identifier les énoncés valides du langage. Elle fournit un moyen d'argumenter dans le langage formel II. Définition d’une proposition (en anglais : sentense) On appelle proposition un assemblage de mots d’une langue naturelle vérifiant les trois propriétés suivantes : 1) Il est reconnu syntaxiquement correct ; Page 3 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI 2) Il est sémantiquement correct ; 3) Il est possible de lui assigner sans ambiguïté une valeur de vérité (vrai ou faux). Exemple 1: Louis 14 est un nombre premier.  Un littéraire attribuera à cette phrase la propriété (1) mais sans doute pas la propriété (2). Ce n’est donc pas une proposition. Exemple 2 : Dans un triangle rectangle, le carré de l’hypoténuse est égal à la somme des carrés des cotés de l’angle droit.  Les propriétés (1, 2 et 3) sont vérifiées : c’est une proposition (vraie). Exemple 3: Le facteur est il arrivé ?  les propriétés (1) et (2) sont vérifiées, mais pas la (3). Ce n’est donc pas une proposition. III. Le langage propositionnel Le but du calcul propositionnel est de donner un fondement formel à un ensemble restreint d’énoncés du langage. Nous utiliserons comme élément de base des propositions élémentaires (des énoncés déclaratifs) : « il fait beau », « je suis en vacances », etc. Ces propositions élémentaires seront soit vraies, soit fausses. Cours 1 : Logique des propositions (1) Le langage propositionnel est composé de formules représentant des propositions. Comme les autres langages, le langage du calcul propositionnel est caractérisé par sa syntaxe et sa sémantique. 1. La syntaxe du langage propositionnel La syntaxe d’un langage définit l’alphabet et les règles d’écriture (grammaire) des expressions du langage. Elle ne s’intéresse pas à leurs sens. a. L’alphabet : L’Alphabet de la logique des propositions (langage que l’on notera L) est constitué des symboles suivants : – les formules { A, B, C,... , ϕ, ψ,... , p, q, r, s, t,... }, – les connecteurs { ↔, →, ∧, ∨, ¬}, – les délimiteurs { (,) } Page 4 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI b. Atomes : On appelle atomes ou variables propositionnelles ou propositions élémentaires des énoncés dont nous ne connaissons pas (et ne chercherons pas à connaître) la structure interne, et qui gardent leur identité tout au long du calcul propositionnel qui nous occupe. L’ensemble des variables propositionnelles est noté v(L). On désigne généralement des propositions élémentaires par des lettres minuscules de l’alphabet (habituellement p, q, r,... ). c. Connecteurs : Nous appellerons connecteurs propositionnels les symboles suivants : équivalence ↔; implication →; conjonction ∧; disjonction ∨; négation ¬. d. Littéral : Un littéral est un atome (littéral positif ) ou la négation d’un atome (littéral négatif ). e. Clause : Une clause est une disjonction de littéraux (p1∨p2∨...∨pn), les littéraux pouvant être positifs ou négatifs. 2. Les règles d’écriture Les règles d’écriture précisent la manière dont sont assemblés les symboles de l’alphabet pour former des expressions bien formées : fbf (ou formules) du langage propositionnel : Cours 1 : Logique des propositions (1) 1) Toute variable propositionnelle est une formule ; 2) Si α est une formule, ¬α (ou α) est une formule ; 3) Si α et β sont des formules, (α ∧ β),(α ∨ β),(α ⇒ β) et (α ⇔ β) sont des formules ; 4) Une expression n’est une formule que si elle est écrite conformément aux règles 1,2 et 3. Exemple 1 : 1) p, q, r sont des variables propositionnelles, donc des formules. 2) p ∨ q est une formule. 3) p ⇒ (q¬ r) n’est pas une formule Exemple 2 :  s’il fait beau et que l’on n’est pas samedi alors je fais du vélo  si je fais du vélo alors c’est le printemps Ce problème peut être modélisé sous la forme suivante : Page 5 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI  variable propositionnelle b = il fait beau  variable propositionnelle s = on est samedi  variable propositionnelle f = je fais du vélo  variable propositionnelle p = c’est le printemps  (((b ∧ (¬s)) → f)  (f → p) 3. Priorité des connecteurs Les connecteurs sont appliqués dans l’ordre suivant : ¬, ∧, ∨,⇒, ⇔ Exemple : 1) ¬p ∧ q se lit (¬p) ∧ q. 2) p ∧ q ⇒ r se lit (p ∧ q) ⇒ r. 3) p ∨ q ∧ r se lit p ∨ (q ∧ r). 4) p ∨ q ∨ r se lit (p ∨ q) ∨ r IV. Sémantique d’un langage propositionnel Cours 1 : Logique des propositions (1) L’étude sémantique d’un langage pour le calcul des propositions a pour but de donner une valeur de vérité aux formules du langage. Elle est aussi appelée la théorie des modèles. La sémantique associe une fonction de valuation V : vp −→ {1, 0}, (où vp est l’ensemble des variables propositionnelles, 1 signifie vrai et 0 signifie faux) unique à chacun des connecteurs logiques. Cette fonction est décrite par un graphe appelé table de vérité (ou tableau de vérité). A chaque formule α à n variables propositionnelles correspond une fonction de vérité unique. Le graphe de cette fonction est défini par une table de vérité à 2 n lignes représentant la valeur de vérité de α correspondant à chaque combinaison de valeur de vérité des n variables (appelées aussi distribution de valeurs de vérité des variables). 1. La négation La négation d’une proposition a notée ¬a ou a est définie de la manière suivante :  Si la proposition a est vraie alors a est fausse. Page 6 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI  Si la proposition a est fausse alors a est vraie. En résumé, on a la table de vérité suivante : 2. La conjonction La conjonction de deux propositions a et b notée symboliquement par a ∧ b et se lit (a et b) est vraie si et seulement si les deux propositions a et b sont vraies simultanément. D’où la table de vérité suivante : 3. La disjonction La disjonction de deux propositions a et b notée symboliquement par a ∨ b et se lit (a ou b) est fausse si et seulement si les deux propositions a et b sont fausses simultanément. Cours 1 : Logique des propositions (1) D’où la table de vérité suivante : 4. L’implication Le connecteur "⇒" est appelé le connecteur d’implication, la proposition a ⇒ b est fausse dans le cas où a est vraie et b est fausse. Elle est définie par le tableau suivant : Soient a et b deux propositions, dans la formule a ⇒ b, a est appelée l’hypothèse (ou antécédent) et b la thèse (ou la conséquence). Page 7 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI Remarque : (a ⇒ b) est appelée implication directe. Les implications apparentes à l’implication directe sont dénommées ainsi :  a ⇒ b implication directe, ici a est une condition suffisante pour b (b si a).  b ⇒ a implication réciproque (converse), ici a est une condition nécessaire de b.  a ⇒ b implication contraire (inverse).  b ⇒ a implication contraposée. 5. L’équivalence Le connecteur "⇔" est appelé le connecteur d’équivalence, la proposition a ⇔ b est vraie dans le cas où a et b ont la même valeur de vérité. Elle est définie par le tableau suivant : Exemple : Soit α la formule p ∨ q ⇒ r. Sa table de vérité est : Cours 1 : Logique des propositions (1) 6. Satisfiabilité Une formule α est dite satisfiable si et seulement si sa table de vérité contient au moins une ligne où la valeur de vérité de α est vraie ( ou V(α) = 1). α est dite insatisfiable si elle est fausse sur toutes les lignes de sa table de vérité. Exemple 1: La formule α de l’exemple précédent est satisfiable. Exemple 2: Page 8 sur 9  I.S.L.A.I.B Cours: Logique formelle Enseignante: Mme Soussi Mouna Niveau: 1ière GLSI Soit α la formule : D’où α est insatisfiable 7. Tautologie Une formule α est une tautologie (on note ), si et seulement si α est vraie sur toutes les lignes de sa table de vérité. Exemple : la formule est une tautologie. Cours 1 : Logique des propositions (1) Remarque : 8. Conséquence logique En langage propositionnel, une formule β est conséquence logique d’une formule α (et on note ), si et seulement si étant donné la table de vérité de α et β, la valeur de vérité de β est vraie sur toutes les lignes où la valeur de vérité de α est vraie. Page 9 sur 9