34
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 [email protected] http://odile.papini.perso.esil.univmed.fr/sources/LOG.html Odile PAPINI Logique classique

Cours LOG Odile Cours 2

Embed Size (px)

Citation preview

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Logique classiqueCours 2 : Logique propositionnelle

    Odile PAPINI

    POLYTECHUniversite [email protected]

    http://odile.papini.perso.esil.univmed.fr/sources/LOG.html

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Plan du cours

    1 Introduction

    2 Le langage propositionnel

    3 La logique propositionnelle comme syste`me formel

    4 La semantique de la logique propositionnelle

    5 Quelques resultats

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Bibliographie I

    Delahaye J. P., Outils logiques pour lintelligenceartificielle. ,Eyrolles, Paris, 1986.

    Gochet P.& Gribomont P., Logique : methodes pourlinformatique fondamentale.Langue, Raisonnement, Calcul, Hermes, Paris, 1990.

    Kleene S. C., Logique mathematique. ,Epistemologie, Jacques Gabay, Paris, 1987.

    Thayse A.& al., Approche logique de lintelligenceartificielle, Tome 1. ,Informatique, DUNOD, Paris, 1990.

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Bibliographie II

    Alliot J.-M., Scheix T., Brisset P. & Garcia F.,Intelligence artificielle et Informatique theorique.,CEPADUES EDITIONS, Toulouse, 2002.

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Bibliographie 2 I

    Support de cours logique propositionnelle

    http ://www.irit.fr/ Andreas.Herzig/C/prop.htmlhttp ://www.grappa.univ-lille3.fr/ champavere/Enseignement/0607/l2miashs/ia/logique.pdfhttp ://www-lipn.univ-paris13.fr/ levy/pdf/CoursLogMod.pdf

    Exerciceshttp ://home.etu.unige.ch/ guigong3/TPdeLogique.htmlhttp ://users.info.unicaen.fr/ zanutti/logique/http ://liris.cnrs.fr/ amille/enseignements/emiage/supportsIA/logique/logique propositions.pdf

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Intoduction

    proposition

    concept de proposition :

    information atomique contingente

    ce qui est ou ce qui nest pas, un fait, une assertion

    exemple de propositions

    2 + 2 = 41 + 1 = 0

    Le soleil brilleIl a les yeux rouges

    un carre est un polygonetout homme est mortel

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Le langage propositionnel L

    Vocabulaire

    un ensemble infini denombrable de variables propositionnellesou propositions P

    les constantes : 0 (Faux , F ou ) et 1 (Vrai , V , ou >)

    les connecteurs :

    les parenthe`ses

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Le langage propositionnel

    Procede 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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Le langage propositionnel

    exercice : representation denonce

    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 ny a pas de dispute ;

    Pierre ne vient pas.

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    Le langage propositionnel

    exercice : representation denonce

    Si Didier est lauteur de ce bruit, il est stupide ou depourvu deprincipes.

    Didier nest ni stupide ni depourvu de principes.

    Didier nest pas lauteur de ce bruit.

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me 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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    Re`gles de deduction

    P, Q, R L

    modus ponens

    ` P, ` P Q` Q

    re`gle de substitution

    remplacer dans un theore`me une variable propositionnelle,partout ou` elle figure, par :

    une autre variable propositionnelleou une formule bien formee

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    Definitions

    P, Q LD1) P Q =def P Q

    D2) P Q =def (P Q)

    D3) P Q =def (P Q) (P Q)

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    Deduction

    une deduction a` partir dhypothe`ses H1,H2, ,Hm est une suitede formules bien formees F1,F2, ,Fp ou` chaque Fi est soit :

    une hypothe`se

    un axiome

    ou une formule obtenue a` partir des re`gles dinference(substitution ou modus ponens) appliquees aux formulesplacees avant Fi dans la deduction

    notation

    H1,H2, ,Hm ` Fptheore`me : deduction sans hypothe`se ` F

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    exemple : deduction

    Donner une deduction 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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    Proposition :

    P L ` (P P)

    Proposition :

    P1, ,Pn1 L

    si P1, ,Pn1 ` (Pn Q) alors P1, ,Pn ` Q

    Theore`me de deduction :

    Soient P1, ,Pn,Q L

    si P1, ,Pn ` Q alors P1, ,Pn1 ` (Pn Q)

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    Quelques theore`mes utiles :

    P,Q,R L, toutes les formules suivantes sont des theore`mes :

    ` ((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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    syste`me formel

    exercices : deduction

    Montrer que P L, ` (P P)

    Montrer que ` ((q p) r) (p r)

    En utilisant le theore`me de deduction montrer que :` (A (B C )) (B (A C ))

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    Interpretation

    toute application de P (ensemble des propositions) dans {0, 1}telle que :

    () = 0 et (>) = 1P,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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    Table de verite

    P Q P Q P Q P Q P Q1 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

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    exercice

    Quelles sont les interpretations qui rendent vraie la formule :

    (A (B C )) (B (A C )) ?

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    quelques definitions

    P,Q L et F L

    P est une tautologie si pour toute interpretation , (P) = 1, onecrit |= P

    Q est une consequence logique de P si pour toute interpretation, si (P) = 1 alors (Q) = 1, on ecrit P |= Q

    Q est une consequence logique de F si pour toute interpretation, tq P F , si (P) = 1 alors (Q) = 1, on ecrit F |= Q

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    exercices

    Monter que les axiomes A1), A2), A3) sont des tautologies

    Est-ce que (p r) est une tautologie ?

    Est -ce que est une consequence logique de ?

    = (p q) (p r), = q r = (p q) (p q), = p

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    quelques definitions

    P,Q L et F LP est satisfaisable ou coherente sil existe une interpretation tq (P) = 1

    F est satisfaisable sil existe une interpretation tq P F ,(P) = 1

    P est insatisfaisable ou incoherente si pour touteinterpretation , (P) = 0

    F est insatisfaisable si pour toute interpretation , P Ftq (P) = 0

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    exercices

    les formules suivantes sont-elles coherentes ?

    (a b) (a b) (a b)

    b (c (b c))

    les ensembles de formules suivants sont-ils satisfaisables ?

    F = {a b c , a b, a c , b,c}

    G = {a b, a, b}

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    Quelques proprietes

    P,Q L,

    |= (P Q) ssi P |= Q

    |= (P Q) ssi P Q

    si |= P et |= (P Q) alors |= Q

    |= (P Q) ssi |= P et |= Q

    si |= P ou |= Q alors |= (P Q)

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    semantique de la logique propositionnelle

    exercice

    Montrer :

    |= (P Q) ssi P |= Q

    |= (P Q) ssi P Q

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    la logique propositionnelle

    Quelques theore`mes

    theore`me (dadequation) :P L si ` P alors |= P

    (les formules qui sont des theore`mes sont des tautologies)

    theore`me (de completude faible) :P L si |= P alors ` P

    (les formules qui sont des tautologies sont des theore`mes )

    theore`me (de completude forte) :Soit F un ensemble de formules de L, P Lsi F |= P alors F ` P

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    logique propositionnelle

    Quelques theore`mes

    theore`me (de compacite) :Soit F un ensemble de formules de L.Si toute famille finie F F est satisfaisable alors F est aussisatisfaisable.

    theore`me (de finitude) :Soit F un ensemble de formules de L. Soit Q Lsi F |= Q alors F F fini tq F |= Q

    theore`me (de decidabilite) :P L , il existe un programme qui, pour toute formule P,

    indique en un temps fini si oui ou non ` POdile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    logique pour linformatique

    formes normales

    litteral : une proposition ou la negation dune propositionclause : disjonction de litterauxcube : conjonction de litterauxforme conjonctive normale : une conjonction de clausesforme disjonctive normale : une disjonction de cubes

    theore`me (de normalisation) :

    P L, P admet une forme conjonctive normale qui lui estequivalente

    P L, P admet une forme disjonctive normale qui lui estequivalente

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    logique pour linformatique : algorithme de normalisation

    debut

    elimination des connecteurs et remplacer P Q par (P Q) (Q P)puis remplacer P Q par P Qapplication des lois de Morgan

    remplacer (P Q) par P Q et (P Q) par P Qelimination des doubles negations

    remplacer P par Papplication des re`gles de distributivite

    remplacer P (Q R) par (P Q) (P R)et (P Q) R par (P R) (Q R)

    finOdile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    formes normales

    exercice

    Mettre sous forme CNF :

    (a b c)

    P (Q R)

    ((P Q) (R S))

    Odile PAPINI Logique classique

  • IntroductionLe langage propositionnel

    La logique propositionnelle comme syste`me formelLa semantique de la logique propositionnelle

    Quelques resultats

    formes normales

    exercice

    Mettre sous forme DNF :

    (a b c)

    P (Q R)

    ((P Q) (R S))

    Odile PAPINI Logique classique

    IntroductionLe langage propositionnelLa logique propositionnelle comme systme formelLa smantique de la logique propositionnelleQuelques rsultats