Precis de Logique

LOGIQUE PROPOSITIONNELLE

INTRODUCTIONLe but de la logiquecaractriser les raisonnements validesAnnexe :applications de la logiqueExemples de raisonnementsUne infrence est valide cause de sa forme(et non pas cause du sens des prmisses).Les moyens reprsentation du monde : introduction de connecteurs pour structurer les propositions ngation :~(il_pleut) conjonction :il_pleut & la_route_est_mouille implication :il_pleut -> la_route_est_mouille ... quantification existentielle :EXISTS x (dieu(x)) quantification universelle :... ...Construction de propositions complexes :~(la_route_est_mouille) -> ~(il_pleut) rgles d'infrence : passage des prmisses la conclusionNiveaux d'analyse Langage : dfinition des formules bien formes Thorie de la preuve (axiomatique) : dfinition des notions de prouvabilit et de dduction Thorie des modles (smantique) : dfinition des notions de validit et de consquence logiqueIdal : valide = dmontrableAnnexe :remarque sur la relation avec le langage naturel

suite :chapitre sur la logique propositionnelle

Logique propositionnelle : langageIntroductionDfinition (alphabet).L'alphabetde la logique propositionnelle est constitu de un ensemble dnombrableATMdevariables propositionnelles(ouformules atomiques, ou encore atomes) lesconnecteursFALSE,~,&,v,-> les sparateurs (ou parenthses)(et)Notation.Nous utilisonsp, q, r, p1, p2,...pour des variables propositionnelles.Dfinition (formule).L'ensembleFORdesformules(ou formules bien formes) de la logique propositionnelle est le plus petit ensemble de mots construits sur l'alphabet tel que siAest une formule atomique alorsAest une formule FALSEest une formule (~A)est une formule siAest une formule (A & B)est une formule siAetBsont des formules (A v B)est une formule siAetBsont des formules (A -> B)est une formule siAetBsont des formulesExemples de formulesNotation.Nous utilisonsA , B , C , A1, A2,...pour des formules (strictement parlant,A,B,...sont des metavariables, car ils ne font pas partie de l'alphabet de la logique).S , S1, S2,...dnotent des ensembles de formules.Remarque.Notre jeu de connecteurs primitifs consiste enFALSE , ~ , & , v , ->. D'autres connecteurs peuvent tre dfinis en tant que abrviations :TRUEabrvie(~FALSE)et l'quivalence(A B)abrvie((A -> B) & (B -> A)).(Annexe :remarque sur des jeux de connecteurs alternatifs)

suite :notions de substitution uniforme et de sous-formule

[Plan|Introduction|Logique propositionnelle(langage,thorie des modles,thorie de la preuve,proprits,FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : langage (suite)Dfinition (sous-formule).L'ensemble dessous-formulesd'une formuleAest le plus petit ensemble tel que Aest une sous-formule deA. Si(~B)est une sous-formule deAalorsBest une sous-formule deA. Si(B & C)est une sous-formule deAalorsBetCsont des sous-formules deA. Si(B v C)est une sous-formule deAalorsBetCsont des sous-formules deA. Si(B -> C)est une sous-formule deAalorsBetCsont des sous-formules deA.L'endroit o une sous-formule apparat est sonoccurrence.Exemples de sous-formulesDfinition (substitution uniforme).Unesubstitution(ou substitution uniforme) associe une variable propositionnellepune formuleA. Elle est note[p\A].L'application de[p\A] une formuleB, note(B)[p\A], est le rsultat du remplacementsimultandetoutesles occurrences depdansBparA.(A)[p\B]est appel uneinstancedeA.Exemples de substitutionsNotation.On omet toujours les parenthses les plus l'extrieur. En gnral, l'omission de parenthses peut tre source d'ambiguts : ainsi,~p & qpeut correspondre (~p) & qet ~(p & q). Cependant, on peut souvent omettre les parenthses en donnant des priorits aux connecteurs, dans l'ordre suivant : , -> , & , v , ~. Ainsi,~p & qcorrespond (~p) & q, etc.Annexe :rappel sur les dmonstrations par inductionAnnexe :remarque sur une dfinition plus constructive deFOR

suite :section sur la thorie des modles

[Plan|Introduction|Logique propositionnelle(langage, thorie des modles,thorie de la preuve,proprits,FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : thorie des modlesIntroductionDfinition (interprtation).UneinterprtationI(ou valuation) est une application del'ensemble des variables propositionnellesATMdans l'ensemble des valeurs de vrit{0,1}.Dfinition (interprtation des formules).Une interpretation donneIpeut tretenduel'ensemble des formulesFORpar : I(FALSE) = 0 I(~A) = 1 - I(A) I(A & B) = min(I(A),I(B)) I(A v B) = max(I(A),I(B)) I(A -> B) = 1ssiI(A) = 0ouI(B) = 1Iest un modle pourA(ouIsatisfaitA) ssiI(A) = 1.I(A) = 1est parfois not|=IA.Iest un modle pour un ensemble de formulesSssiIest un modle pour toute formuleAdeS.ExemplesDfinition (validit, satisfiabilit).SoitAune formule.Aestvalide(ou tautologique ; not|= A) siI(A) = 1pour toute interpretationI. SinonAest invalide ou falsifiable.Aestsatisfiablessi il existe une interpretationIt.q.I(A) = 1. SinonAest insatisfiable ou contradictoire.ExemplesDfinition (consquence logique).Une formuleAestconsquence logiquedeA1, ... ,An(notA1, ... ,An|= A) ssi tout modle deA1, ... ,Anest un modle deA.ExemplesAnnexe :remarque sur des ensembles d'hypothses infinis

suite :section sur la thorie de la preuve

[Plan|Introduction|Logique propositionnelle(langage,thorie des modles, thorie de la preuve,proprits,FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : thorie de la preuveIntroductionDfinition (axiomatique la Hilbert).Lesschmas d'axiomede la logique propositionnelle sontA -> (B -> A)(A -> B) -> ((A -> (B -> C)) -> (A -> C))A -> (B -> A & B)(A & B) -> A(A & B) -> BA -> A v BB -> A v B(A -> C) -> ((B -> C) -> (A v B -> C))(A -> B) -> ((A -> ~B) -> ~A)~~A -> A~FALSE

et largle d'infrenceest leModus Ponens :A A -> B_____________BAetA -> Bsont appelesprmisses, etBest appeleconclusionde la rgle.(Rappel : on omet les parenthses selon les priorits suivantes : , -> , & , v , ~.)Chaque formule qui a la forme d'un schma est appele un axiome. Ainsi, un axiome est uneinstanced'un schma. P.ex.(p & q) -> (r -> (p & q))est un axiome, obtenu partir du premier schmaA -> (B -> A).Annexe : remarque sur une axiomatisation qui n'a pas besoin de la notion de schma (ncessitant une rgle de substitution uniforme)

suite :notion de preuve et de dduction


Logique propositionnelle : thorie de la preuve (suite)Dfinition (preuve).SoitAune formule. UnepreuvedeAest une liste finie de formules(A1, ... ,An)t.q. An= A pouri = 1, ..., n, la formuleAiest soit l'instance d'un axiome, soit obtenue par application de la rgle de Modus Ponens partir de deux prmissesAj, AkprcdantAidans la liste.ExemplesDfinition (prouvabilit, consistance).SoitAune formule.Aestprouvable(not|- A) si il existe une preuve deA.Aestconsistantesi~An'est pas prouvable. SinonAest inconsistante.ExemplesDfinition (dduction).Unedductiond'une formuleA partir d'hypothsesB1,...,Bm(notB1,...,Bm|- A) est une liste finie de formules(A1, ... ,An)t.q. An= A pouri = 1, ...,n, la formuleAiest soit un axiome, soit gal une des hypothsesBj, soit obtenue par application de la rgle de Modus Ponens partir de deux prmissesAj, AkprcdantAidans la liste.ExemplesDonc une preuve est une dduction partir d'un ensemble vide d'hypothses.Parfois les axiomes sont appelles àxiomes logiques', et les hypothses àxiomes non-logiques'.Annexe : remarque sur des ensembles d'hypothses infinis

suite :section sur les proprits importantes

[Plan|Introduction|Logique propositionnelle(langage,thorie des modles,thorie de la preuve, proprits,FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : proprits importantesIntroductionAdquation et de compltudeLemme (largle de modus ponensprserve la validit).Si|= Aet|= A -> Balors|= B.Lemme (lasubstitution uniformeprserve la validit).SoientAetBdes formules etpun atome. Si|= Aalors|= A[p\B].(cf. laremarquesur une axiomatisation avec une rgle de substitution uniforme dans la section sur lathorie de la preuve)Thorme d'adquation.Si|- Aalors|= A.(la dmonstration utilise les lemmes prcdents, et le fait que les axiomes sont valides)Thorme de compltude.Si|= Aalors|- A.(la dmonstration est difficile)Thorme de dductionThorme de dduction.A |- Bssi|- A -> B.Donc le problme de dductionA |- Bpeut tre rduit au problme de prouvabilit|- A -> B.Thorme de la consquence logique (version smantique du thorme de dduction).A |= Bssi|= A -> B.Donc le problme de consquence logiqueA |= Bpeut tre rduit au problme de validit|= A -> B.Annexe :thormes d'adquation et de compltude forte (non pas entre validit et prouvabilit, mais entre consquence logique et dduction)DcidabilitThorme (existence d'une procdure de dcision).La logique propositionnelle est dcidable : il existe une procdure effective qui pour toute formuleAen entre s'arrte et retourne òui' siAest valide, et `non' sinon.Un exemple de procdure de dcision est lamthode des tables de vrit. Une mthode plus efficace est lamthode de balayage.L'axiomatique est une caractrisation finie des formules valides : elle peut tre `rendue oprationelle' comme procdure numerant l'ensemble des formules prouvables. Mais ceci ne nous donne qu'une procdure de semi-dcision : si la formule en question est valide, cette procdure va la trouver un jour, mais si elle ne l'est pas alors la procdure ne s'arrtera jamais.

suite :quelques quivalences utiles


Logique propositionnelle : proprits importantes (suite)Remarque.tant donn lesthormes d'adquation et de compltude, les proprits qui suivent peuvent tre formules et en termes de prouvabilit (avec|-) et en termes de validit (avec|=).Remplacement des quivalences logiquesThorme (remplacement des quivalences).SoitBune sous-formule deA, et soit|- B C. SiA'est obtenue partir deApar le remplacement de cette occurrences deBparCalors|- A A'.Exemples d'applicationRemarque.Le remplacement en question n'est pas unesubstitution uniforme(cette dernire ne s'applique qu'aux atomes, et non des formules ; de plus, elle s'applique toutesles occurrences, et non une ou plusieurs).quivalences permettant d'liminer des connecteurslimination de l'implication :|- A -> B ~A v Blimination de l'quivalence :|- (A B) (A -> B) & (B -> A)limination deFALSE:|- FALSE p & ~p (pour unpquelconque)limination de la ngation :|- ~A A -> FALSEliminations de la disjonction :|- A v B ~(~A & ~B)|- A v B (A -> FALSE) -> Bliminations de la conjonction :|- A & B ~(~A v ~B)|- A & B (A -> (B-> FALSE)) -> FALSE(v. aussil'annexesur des jeux de connecteurs alternatifs)quivalences correspondant aux proprits algbriques des connecteursidempotence de~:|- ~~A Aidempotence de&etv:|- A & A A|- A v A Aassociativit de&etv:|- A & (B & C) (A & B) & C|- A v (B v C) (A v B) v Ccommutativit de&etv:|- A & B B & A|- A v B B v Adistributivit (lois de De Morgan) :|- (A v B) & C (A & C) v (B & C)|- (A & B) v C (A v C) & (B v C)

(Rappel : on omet les parenthses selon les priorits suivantes : , -> , & , v , ~.)

suite :section sur la forme normale conjonctive

[Plan|Introduction|Logique propositionnelle(langage,thorie des modles,thorie de la preuve,proprits, FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : forme normale conjonctiveIntroduction et motivationDfinition (littral, clause, forme normale conjonctive).Unlittralest uneformule atomiqueou la ngation d'une formule atomique.Uneclauseest une disjonction de littraux.Une formule est enforme normale conjonctivesi elle est une conjonction de clauses.ExemplesNotation.Nous utilisonsL, L1, L2...pour des littraux, etC, C1, C2...pour des clauses.Notation.On suppose que les disjonctions et conjonctions sont parenthses gauche :une clauseL1v L2v ... v Lnest((...(L1v L2) v ...) v Ln), etune conjonction de clausesC1& C2... & Cmest((...(C1& C2) ...) & Cm).Ceci est justifi parl'associativit de la conjonction et de la disjonction(v. aussiles exemples).Par convention, une disjonction de 0 littraux estFALSE(la clause vide), et une conjonction de 0 clauses estTRUE.Notation.Nous confondons une conjonction de clauses avec un ensemble de clauses, et une clause avec un ensemble de littraux. Ceci est justifi parla commutativit et l'idempotence de la conjonction et de la disjonction. Ainsi, la formule en forme normale conjonctive(p v q) & (~p v r)sera confondu avec l'ensemble{ {p v q} , {~p v r} }. La clause videFALSEsera confondu avec l'ensemble vide{}.Algorithme de mise en forme normale conjonctiveentre :une formuleAsortie :une formule en forme normale conjonctivedbutliminer-> , , FALSE; appliquer autant que possible les quivalences suivantes (en remplaant le membre gauche par le membre droit), dans n'importe quel ordre : ~~A A ~(A v B) ~A & ~B ~(A & B) ~A v ~B A v (B & C) (A v B) & (A v C)finExemplesThorme.Pour toute entreA, l'algorithme de mise en forme normale conjonctive s'arrte. Il retourne une formule en forme normale conjonctive quivalente l'entre.(la dmonstration utilise lethorme de la substitution des quivalents: les remplacements effectus par l'algorithmecorrespondent des quivalences prouvables)Thorme.Une formule en forme normale conjonctive est valide ssi toute clause contient deux littraux contradictoires, c--d chaque clause est de la formeL1 v ... v p v ... v ~p v ... v Ln.

suite :section sur la dmonstration automatique

[Plan|Introduction|Logique propositionnelle(langage,thorie des modles,thorie de la preuve,proprits,FNC, dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : dmonstration automatiqueIntroductionLa mthode de balayage (rsolution non-clausale)Algorithme de balayageentre :une formuleAsortie :TRUEouFALSEdbutliminer-> , ;tant que non(A = TRUE)etnon(A = FALSE) fairechoisir une variable propositionnellepapparassant dansA;remplacerApar la formuleA[p\TRUE]& A[p\FALSE];appliquer autant que possible les quivalences suivantes (en remplaant le membre gauche par le membre droit), dans n'importe quel ordre : ~FALSE TRUE ~TRUE FALSE B v TRUE TRUE B & FALSE FALSE B & TRUE B B v FALSE Bfin tant quefinRemarque.La liste des quivalences utilises n'est pas complte : on a suppos tacitement que lacommutativitde&et devest exploit.ExemplesRemarque.Les exemples montrent que le choix de l'atome substituer est crucial (une heuristique possible est de choisir l'atome qui a le plus d'occurrences dansA).Thorme.Pour tout entreA, l'algorithme de balayage s'arrte. Il retourneTRUEsiAest valide, etFALSEsinon.Dmonstration. La terminaison est assure par le fait que chaque passage de la boucle limine un atome. Ensuite, comme|= Assi|= (A[p\TRUE] & A[p\FALSE]), la deuxime tape prserve la validit. Finalement, les simplifications correspondent des quivalences valides.Remarque.L'quivalenceA (A[p\TRUE] & A[p\FALSE])n'est pas valide (exemple :A = p).

suite :chapitre sur la logique des prdicats

http://www.irit.fr/~Andreas.HerzigLogique propositionnelle : thorie des modlesIntroductionDfinition (interprtation).UneinterprtationI(ou valuation) est une application del'ensemble des variables propositionnellesATMdans l'ensemble des valeurs de vrit{0,1}.Dfinition (interprtation des formules).Une interpretation donneIpeut tretenduel'ensemble des formulesFORpar : I(FALSE) = 0 I(~A) = 1 - I(A) I(A & B) = min(I(A),I(B)) I(A v B) = max(I(A),I(B)) I(A -> B) = 1ssiI(A) = 0ouI(B) = 1Iest un modle pourA(ouIsatisfaitA) ssiI(A) = 1.I(A) = 1est parfois not|=IA.Iest un modle pour un ensemble de formulesSssiIest un modle pour toute formuleAdeS.ExemplesDfinition (validit, satisfiabilit).SoitAune formule.Aestvalide(ou tautologique ; not|= A) siI(A) = 1pour toute interpretationI. SinonAest invalide ou falsifiable.Aestsatisfiablessi il existe une interpretationIt.q.I(A) = 1. SinonAest insatisfiable ou contradictoire.ExemplesDfinition (consquence logique).Une formuleAestconsquence logiquedeA1, ... ,An(notA1, ... ,An|= A) ssi tout modle deA1, ... ,Anest un modle deA.ExemplesAnnexe :remarque sur des ensembles d'hypothses infinis






















Logique propositionnelle : langageIntroductionDfinition (alphabet).L'alphabetde la logique propositionnelle est constitu de un ensemble dnombrableATMdevariables propositionnelles(ouformules atomiques, ou encore atomes) lesconnecteursFALSE,~,&,v,-> les sparateurs (ou parenthses)(et)Notation.Nous utilisonsp, q, r, p1, p2,...pour des variables propositionnelles.Dfinition (formule).L'ensembleFORdesformules(ou formules bien formes) de la logique propositionnelle est le plus petit ensemble de mots construits sur l'alphabet tel que siAest une formule atomique alorsAest une formule FALSEest une formule (~A)est une formule siAest une formule (A & B)est une formule siAetBsont des formules (A v B)est une formule siAetBsont des formules (A -> B)est une formule siAetBsont des formulesExemples de formulesNotation.Nous utilisonsA , B , C , A1, A2,...pour des formules (strictement parlant,A,B,...sont des metavariables, car ils ne font pas partie de l'alphabet de la logique).S , S1, S2,...dnotent des ensembles de formules.Remarque.Notre jeu de connecteurs primitifs consiste enFALSE , ~ , & , v , ->. D'autres connecteurs peuvent tre dfinis en tant que abrviations :TRUEabrvie(~FALSE)et l'quivalence(A B)abrvie((A -> B) & (B -> A)).(Annexe :remarque sur des jeux de connecteurs alternatifs)

suite :notions de substitution uniforme et de sous-formule

[Plan|Introduction|Logique propositionnelle(langage,thorie des modles,thorie de la preuve,proprits,FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : langage (suite)Dfinition (sous-formule).L'ensemble dessous-formulesd'une formuleAest le plus petit ensemble tel que Aest une sous-formule deA. Si(~B)est une sous-formule deAalorsBest une sous-formule deA. Si(B & C)est une sous-formule deAalorsBetCsont des sous-formules deA. Si(B v C)est une sous-formule deAalorsBetCsont des sous-formules deA. Si(B -> C)est une sous-formule deAalorsBetCsont des sous-formules deA.L'endroit o une sous-formule apparat est sonoccurrence.Exemples de sous-formulesDfinition (substitution uniforme).Unesubstitution(ou substitution uniforme) associe une variable propositionnellepune formuleA. Elle est note[p\A].L'application de[p\A] une formuleB, note(B)[p\A], est le rsultat du remplacementsimultandetoutesles occurrences depdansBparA.(A)[p\B]est appel uneinstancedeA.Exemples de substitutionsNotation.On omet toujours les parenthses les plus l'extrieur. En gnral, l'omission de parenthses peut tre source d'ambiguts : ainsi,~p & qpeut correspondre (~p) & qet ~(p & q). Cependant, on peut souvent omettre les parenthses en donnant des priorits aux connecteurs, dans l'ordre suivant : , -> , & , v , ~. Ainsi,~p & qcorrespond (~p) & q, etc.Annexe :rappel sur les dmonstrations par inductionAnnexe :remarque sur une dfinition plus constructive deFOR

suite :section sur la thorie des modles

[Plan|Introduction|Logique propositionnelle(langage, thorie des modles,thorie de la preuve,proprits,FNC,dmonstration automatique) |Logique des prdicats|Logiques non-classiques]

Logique propositionnelle : thorie des modlesIntroductionDfinition (interprtation).UneinterprtationI(ou valuation) est une application del'ensemble des variables propositionnellesATMdans l'ensemble des valeurs de vrit{0,1}.Dfinition (interprtation des formules).Une interpretation donneIpeut tretenduel'ensemble des formulesFORpar : I(FALSE) = 0 I(~A) = 1 - I(A) I(A & B) = min(I(A),I(B)) I(A v B) = max(I(A),I(B)) I(A -> B) = 1ssiI(A) = 0ouI(B) = 1Iest un modle pourA(ouIsatisfaitA) ssiI(A) = 1.I(A) = 1est parfois not|=IA.Iest un modle pour un ensemble de formulesSssiIest un modle pour toute formuleAdeS.ExemplesDfinition (validit, satisfiabilit).SoitAune formule.Aestvalide(ou tautologique ; not|= A) siI(A) = 1pour toute interpretationI. SinonAest invalide ou falsifiable.Aestsatisfiablessi il existe une interpretationIt.q.I(A) = 1. SinonAest insatisfiable ou contradictoire.ExemplesDfinition (consquence logique).Une formuleAestconsquence logiquedeA1, ... ,An(notA1, ... ,An|= A) ssi tout modle deA1, ... ,Anest un modle deA.ExemplesAnnexe :remarque sur des ensembles d'hypothses infinis









































LOGIQUES NON-CLASSIQUESIntroductionLes logiques modales (qui font partie des logiques non-classiques) sont des extensions de la logique classique par des nouveaux connecteurs (ou oprateurs). Ces oprateurs permettent d'analyser formellement des concepts tels la croyance, le temps, l'incertitude, l'execution d'un programme, d'une actions, etc. Ainsi, la formule[a]Apeut tre lue `l'agentacroit queA' dans une interprtation en termes de croyances, Àest vraie l'instanta' dans une interprtation temporelle, Àest vraie au dgra' dans une interprtation en termes d'incertitude, Àest vraie aprs terminaison du programmea' dans une interprtation en termes de programmes. Àest vraie aprs execution de l'actiona' dans une interprtation en termes d'actions.Plusieurs familles de logiques modales ont ainsi t dfinies dans la littrature. Les interprtations particulires des oprateurs modaux ont motives l'application de ces logiques en particulier en intelligence artificielle et en vrification des programmmes.Pour une introduction plus dtaille nous nous refrons aux documents suivants (tous en Anglais). Modal logics: applications and proof methods(transparents)

Documents

Precis de Logique