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 Le langage propositionnel La logique propositionnelle comme syst`

Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Logique classique Cours 2 : Logique propositionnelle Odile PAPINI POLYTECH Universit´ e d’Aix-Marseille odile.papini@univ-amu.fr http://odile.papini.perso.esil.univmed.fr/sources/LOG.html Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Plan du cours 1 Introduction 2 Le langage propositionnel 3 La logique propositionnelle comme syst` eme formel 4 La s´ emantique de la logique propositionnelle 5 Quelques r´ esultats Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Bibliographie I Delahaye J. P., Outils logiques pour l’intelligence artiﬁcielle. , Eyrolles, Paris, 1986. Gochet P.& Gribomont P., Logique : m´ ethodes pour l’informatique fondamentale. Langue, Raisonnement, Calcul, Hermes, Paris, 1990. Kleene S. C., Logique math´ ematique. , Epist´ emologie, Jacques Gabay, Paris, 1987. Thayse A.& al., Approche logique de l’intelligence artiﬁcielle, Tome 1. , Informatique, DUNOD, Paris, 1990. Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Bibliographie II Alliot J.-M., Scheix T., Brisset P. & Garcia F., Intelligence artiﬁcielle et Informatique th´ eorique., CEPADUES EDITIONS, Toulouse, 2002. Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Bibliographie 2 I Support de cours logique propositionnelle http ://www.irit.fr/ Andreas.Herzig/C/prop.html http ://www.grappa.univ- lille3.fr/ champavere/Enseignement/0607/l2miashs /ia/logique.pdf http ://www-lipn.univ-paris13.fr/ levy/pdf/CoursLogMod.pdf Exercices http ://home.etu.unige.ch/ guigong3/TPdeLogique.html http ://users.info.unicaen.fr/ zanutti/logique/ http ://liris.cnrs.fr/ amille/enseignements/emiage/ supports−IA/logique/logique propositions.pdf Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Intoduction proposition concept de proposition : information atomique contingente ce qui est ou ce qui n’est pas, un fait, une assertion exemple de propositions 2 + 2 = 4 1 + 1 = 0 Le soleil brille Il a les yeux rouges un carr´ e est un polygone tout homme est mortel · · · Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Le langage propositionnel L Vocabulaire un ensemble inﬁni d´ enombrable de variables propositionnelles ou propositions P les constantes : 0 (Faux, F ou ⊥) et 1 (Vrai, V , ou ⊤) les connecteurs : ¬ ∧ ∨ → ↔ les parenth` eses Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Le langage propositionnel Proc´ ed´ e de formation des formules de L ⊤(ou 0 ou F) : est une formule ⊥(ou 1 ou V ) : est une formule p : une variable propositionnelle est une formule si P et Q sont des formules alors ¬ P, P ∧Q, P ∨Q, P →Q, P ↔Q sont des formules Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Le langage propositionnel Exemples de formules propositionnelles (¬P ∧Q) ∨(P ∧¬Q) P ∨(Q ∧R) (P →(Q →P)) (A →B) →((A →(B →C)) →(A →C)) ¬¬A →A Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Le langage propositionnel exercice : repr´ esentation d’´ enonc´ e Si Pierre vient, on joue aux cartes ; Si Pierre et Jean viennent, il y a des disputes ; Si on ne joue pas aux cartes, il n’y a pas de dispute ; Pierre ne vient pas. Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats Le langage propositionnel exercice : repr´ esentation d’´ enonc´ e Si Didier est l’auteur de ce bruit, il est stupide ou d´ epourvu de principes. Didier n’est ni stupide ni d´ epourvu de principes. Didier n’est pas l’auteur de ce bruit. Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel Axiomes ∀P, Q, R ∈L A1) (P →(Q →P)) A2) ((P →(Q →R)) →((P →Q) →(P →R))) A3) ((¬ P →¬ Q) →(Q →P)) Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel R` egles de d´ eduction ∀P, Q, R ∈L modus ponens ⊢P, ⊢P →Q ⊢Q r` egle de substitution remplacer dans un th´ eor` eme une variable propositionnelle, partout o` u elle ﬁgure, par : une autre variable propositionnelle ou une formule bien form´ ee Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel D´ eﬁnitions ∀P, Q ∈L D1) P →Q =def ¬P ∨Q D2) P ∧Q =def ¬(¬P ∨¬Q) D3) P ↔Q =def (¬P ∨Q) ∧(P ∨¬Q) Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel D´ eduction une d´ eduction ` a partir d’hypoth` eses H1, H2, · · · , Hm est une suite de formules bien form´ ees F1, F2, · · · , Fp o` u chaque Fi est soit : une hypoth` ese un axiome ou une formule obtenue ` a partir des r` egles d’inf´ erence (substitution ou modus ponens) appliqu´ ees aux formules plac´ ees avant Fi dans la d´ eduction notation H1, H2, · · · , Hm ⊢Fp th´ eor` eme : d´ eduction sans hypoth` ese ⊢F Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel exemple : d´ eduction Donner une d´ eduction de C ` a partir de A, B et A →(B →C), plus formellement, montrer que : A, B, A →(B →C) ⊢ C Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel Proposition : ∀P ∈L ⊢(P →P) Proposition : ∀P1, · · · , Pn−1 ∈L si P1, · · · , Pn−1 ⊢(Pn →Q) alors P1, · · · , Pn ⊢Q Th´ eor` eme de d´ eduction : Soient P1, · · · , Pn, Q ∈L si P1, · · · , Pn ⊢Q alors P1, · · · , Pn−1 ⊢(Pn →Q) Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel Quelques th´ eor` emes utiles : ∀P, Q, R ∈L, toutes les formules suivantes sont des th´ eor` emes : ⊢((P →Q) →((Q →R) →(P →R))) ⊢(P →((P →Q) →Q)) ⊢(¬P →(P →Q)) ⊢(¬¬P →P) ⊢(P →¬¬P) ⊢((P →Q) →(¬Q →¬P)) ⊢(P →(¬Q →¬(P →Q))) ⊢((Q →P) →((¬Q →P) →P)) Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats syst` eme formel exercices : d´ eduction Montrer que ∀P ∈L, ⊢(P →P) Montrer que ⊢((q →p) →r) →(p →r) En utilisant le th´ eor` eme de d´ eduction montrer que : ⊢(A →(B →C)) →(B →(A →C)) Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats s´ emantique de la logique propositionnelle Interpr´ etation toute application σ de P (ensemble des propositions) dans {0, 1} telle que : σ(⊥) = 0 et σ(⊤) = 1 ∀P, Q ∈L, σ(¬P) = 1 −σ(P) σ(P ∨Q) = max(σ(P), σ(Q)) σ(P ∧Q) = min(σ(P), σ(Q)) σ(P →Q) = max((1 −σ(P)), σ(Q)) σ(P ↔Q) = min(max((1 −σ(P)), σ(Q)), max(σ(P), (1 −σ(Q)))). Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats s´ emantique de la logique propositionnelle Table de v´ erit´ e P Q P ∨Q P ∧Q P →Q P ↔Q 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 Odile PAPINI Logique classique Introduction Le langage propositionnel La logique propositionnelle comme syst` eme formel La s´ emantique de la logique propositionnelle Quelques r´ esultats s´ emantique de la logique propositionnelle exercice Quelles sont les interpr´ etations qui rendent vraie la formule : (A →(B →C)) →(B →(A →C)) ? Odile PAPINI Logique classique Introduction Le langage propositionnel uploads/Philosophie/ cours-log-odile-cours-2.pdf