Cours : Logique du premier ordre

Description

Chapitre 1Logique du premier ordre1.1 Langage et FormulesLe langage est form´e avec :– un ensemble de connecteurs logiques,– des quantificateurs existentiels∃ et universels∀,– un ensemble d´enombrable de variables X,– un ensemble fini de symboles de fonctions F chaque symbole ayant unearit´e fixe.Lessymbolesdefonctionsetlesvariablespermettentded´efinirlestermescommevu pr´ec´edemment.Pour simplifier on supposera que l’ensemble des symboles defonctions contient une constante au moins.L’ensembleForm des formules est le plus petit ensemble tel que– r∈R d’arit´en,t ,...,t ∈T (X) alorsr(t ,...,r )∈Form (atomes),1 n F 1 n– ϕ,ψ∈Form alors¬ϕ,ϕ∧ψ,ϕ∨ψ,ϕ⇒ψ,ϕ⇔ψ∈Form– ϕ∈Form alors∀xϕ,∃xϕ∈Form.Exemple F ={o,s( ),+( , )} , R ={≥} avec +,≥ not´ees de mani`eres in-fix´ees.∀x s(x)≥o∧∀x,y s(x)≥s(y)⇒x≥yest une formuleMais s(s(x)) n’en n’est pas une (c’est un terme), ni∀x s(x).21.1.1 Variables libres, li´eesOn d´efinit la notion d’occurernce libre, li´ee et de FV(ϕ) l’ensemble desvariables libres d’une formule ainsi :– siϕ est un atome alors tout occurrence d’une variablex dans ϕ est libre.12 CHAPITRE 1. LOGIQUE DU PREMIER ORDRE– si ϕ est∃x ψ ou∀x ψ alors FV(ϕ) = FV(ψ)−{x} et toute occurrencelibre de x dans ψ devient li´ee dans ϕ par le quantificateur introduit.′ ′– FV(ϕ◦ϕ ) = FV(ϕ)∪FV(ϕ ) et l’ensemble des occurrence libre d’une′variable est l’union des ensembles des occurences libre dans ϕ et dansϕ .Une formule ϕ est close ou ferm´ee ssi FV(ϕ) =∅.Exemples[∀x(∃yp(x ...

Informations

• Publié par: Nucheg
• Nombre de lectures: 30
• Langue: Français

Extrait

Chapitre 1

Logique du premier ordre

1.1 Langage et Formules Lelangageestforme´avec: – un ensemble de connecteurs logiques, – des quantificateurs existentiels ∃ et universels ∀ , –unensemblede´nombrabledevariables X , – un ensemble fini de symboles de fonctions F chaque symbole ayant une arite´fixe. Lessymbolesdefonctionsetlesvariablespermettentdede´finirlestermescomme vupr´ece´demment.Poursimplifieronsupposeraquel’ensembledessymbolesde fonctions contient une constante au moins. L’ensemble F orm des formules est le plus petit ensemble tel que – r ∈ R d’arite´ n , t 1      t n ∈ T F ( X ) alors r ( t 1      r n ) ∈ F orm (atomes), – ϕ ψ ∈ F orm alors ¬ ϕ ϕ ∧ ψ ϕ ∨ ψ ϕ ⇒ ψ ϕ ⇔ ψ ∈ F orm – ϕ ∈ F orm alors ∀ xϕ ∃ xϕ ∈ F orm . Exemple F = { o s ( )  +(  ) } , R = {≥} avec +  ≥ note´esdemanie`resin- fix´ ees. ∀ x s ( x ) ≥ o ∧ ∀ x y s ( x ) ≥ s ( y ) ⇒ x ≥ y est une formule Mais s ( s ( x )) n’en n’est pas une (c’est un terme), ni ∀ x s ( x ).

✷

1.1.1Variableslibres,li´ees Onde´finitlanotiond’occurerncelibre,lie´eetde F V ( ϕ ) l’ensemble des variables libres d’une formule ainsi : – si ϕ est un atome alors tout occurrence d’une variable x dans ϕ est libre. 1

2

CHAPITRE 1. LOGIQUE DU PREMIER ORDRE – si ϕ est ∃ x ψ ou ∀ x ψ alors F V ( ϕ ) = F V ( ψ ) − { x } et toute occurrence libre de x dans ψ devientlie´edans ϕ par le quantificateur introduit. – F V ( ϕ ◦ ϕ ′ ) = F V ( ϕ ) ∪ F V ( ϕ ′ ) et l’ensemble des occurrence libre d’une variable est l’union des ensembles des occurences libre dans ϕ et dans ϕ ′ . Une formule ϕ estcloseouferme´essi F V ( ϕ ) = ∅ . Exemples [ ∀ x ( ∃ yp ( x y ))] ⇒ [ ∃ z ∀ y yq ( x z y )] a une variable libre x ,desvariableslie´es x y z .Lapremi`ereoccurrencede x estlie´eparlequantificateur ∀ x .Lapremie`reoccurrencede y estli´eepar ∃ y et la seconde par ∀ y ✷ .

1.2Se´mantique 1.2.1 Evaluation d’une formule Il faut donner un sens vrai ou faux aux formules, les interpreter. Pour cela ´ il faut donner un sens aux fonctions, puis aux relations. Pour cela il faut dire dans quel domaine les individus se trouvent. Cela se fait en se donnant une int ´tation. erpre Etape 1 : choisir un domaine D qui est un ensemble non vide. exemple : D estl’ensembledese´tudiantsdelicence D E D est l’ensemble des entiers positifs ou nuls N D estl’ensembledestrianglesisoc`eles T ri Etape 2 : donner un sens aux fonctions. A chaque symbole f ∈ F d’arit´e n on associe une fonction I ( f )note´eaussi f I , de D n → D quiestsoninterpre´tation. Enparticulieruneconstanteserainterpre´t´eparune´l´ementdudomaine. exemple : –Laconstantecs’interpr`eteparPierreDupont(pourunchoixdedomaine D = D E ) – La fonction f d’arit´e2s’interpr`eteparl’addition(pourunchoixdedo- maine D = N ) – La fonction s s’interpre`tecommelesymme´triqueparrapport`al’origine (pour un choix de domaine D = T ri ) Noterqu’oninterpr`etepardesfonctionsde D n → D et pas par des fonctions d’un autre domaine : par exemple si D = T ri onnepeutinterpre´terlafonction s comme l’aire du triangle (fonction de Tri dans R ). Etape 3 : donner un sens aux relations. A chaque symbole r ∈ R d’arit´e n on associe une relation I ( r )((not´eaussi r I ) de D n quiestsoninterpr´etation. exemple :

´ 1.2. SEMANTIQUE 3 – La relation binaire r peuts’interpre´terpar suivre le meme cursus , les ˆ cursus´etantmath-info,physique-infoouinformatique(pourunchoixde domaine D = D E ). – La relation binaire bg s’interpre`te ≥ (pour un choix de domaine D = N ). – La fonction isoc s’interpre`te ˆetreisoce`le (pour un choix de domaine D = T ri ) Une structure h D I i estladonn´eed’undomaine D etd’uneinterpr´etation I quiinterpre`techaquesymboledefonctionetderelation. Etape 4 :donnerunevaleur1pourvraiou0pourfaux`auneformuledans une structure h D I i . Onsaitlefaireintuitivement,maislade´finitionformelledemandea`eˆtreplus ´ is prec . Lapremi`eredifficulte´estl’existencedevariableslibresauxquellesilfaut donner une valeur : la formule ∀ x x ≥ y avec D = N , ≥ interpr´et´ecommeplus grand,peuteˆtrevraieoufausseselonlavaleurde y . 1. Assignation. Une assignation est une application A de X dans D qu’on ´etendenuneapplicationde T F ( X ) dans D par : – A ( c ) = I ( c ) – A ( f ( t 1      t n )) = f I ( A ( t 1 )      A ( t n )) Une x -variante B d’une assignation A est une assignation telle que B ( y ) = A ( y ) pour toute y 6 = x ∈ X (´egale`a A sur X saufpeut-ˆetreen x ). 2. Evaluer une formule ϕ ´etantdonn´eunestructure h D I i et une assignation A c’estcalculerlavaleurdev´erite´ ϕ IA par : – p ( t 1      t n ) IA = 1 ssi p I ( t I 1 A      t I n A ) – ( ϕ ∨ ψ ) I A = max ( ϕ IA ψ IA ) (et similaire pour ∧  ⇒  ⇔ )  – ∃ x ϕ IA = 1 ssi il existe une x -variante B de A telle que ϕ IB = 1. – ∀ x ϕ IA = 1 ssi ϕ IB = 1 pour toute x -variante B de A . Exemples : – ∀ x y z ( r ( x y ) ∧ r ( y z ) ⇒ r ( x z )) dans le domaine D dese´tudiantsdu CMI avec r I = suivrelemˆemecursus est vraie. –Aveclemˆemedomaineetlamˆemeinterpr´etation, ∃ y ∀ x ( r ( x y ) est fausse : iln’yapasune´tudiantquisuitlemˆemecursusquetouslesautres(iln’est paspossibledesuivredeuxcursusdiffe´rentsetilyenaplusieursauCMI). – ∀ x x > y est vraie dans la structure hN  I i avec I(o)=0, I(s) la fonction successuer, I ( > ) la relation > avec l’assignation A ( x ) = 0, fausse pour toute 1.2.2 Terminologie Parde´finition,si ϕ estuneformuleclosealorslavaleurdeve´ritede ϕ IA ´ estind´ependantede A et on la note ϕ I . On dit que la formule est satisfaisable sicettevaleurest1(i.e.vrai).Danstoutelasuiteonnes’inte´resseraqu’a`des

4 CHAPITRE 1. LOGIQUE DU PREMIER ORDRE formulescloses.Quandlaformulen’estpasclose,onconsid`ereusuellementsa cloˆtureuniversellec’esta`dire ∀ x 1      x n ϕ si F V ( ϕ ) = { x 1      x n } . Si ϕ est une formule close et h D I i une structure telle que ϕ est satisfaisable dans h D I i , alors on dit que h D I i est un mod`ele de ϕ .Unmode`led’unensemble deformulesclosesΓestuneinterpre´tationquiestmod`eledechaqueformulede Γ. Uneformuleclosequin’apasdemode`leestditeinsatisfaisable. Exemple : ∀ x ( p ( x ) ∧ ¬ p ( x )) Une formule close ϕ qui est satisfaisable dans n’importe quelle structure est tautologie´ecrit | = ϕ . une , Exemple : ( ∀ x ( p ( x ) ∧ q ( x ))) ⇔ ( ∀ x p ( x ) ∧ ∀ x q ( x )) Une formule close ϕ estcons´equencelogiqued’unensembledeformulescloses si ϕ estvraidanstoutmode`ledeΓ,e´critΓ | = ϕ . The´orie :uneth´eorieestl’ensembledescons´equenceslogiquesd’unensemble deformulescloses.Parexemplelath´eoriedesgroupesestl’ensembledesformules logiques qui sont vraies dans tous les groupes. 1.2.3Mode`ledeHerbrand Uneinterpr´etationdeHerbrandestuneinterpre´tationdontledomaine D est l’ensembledestermesetunsymboledefonctionestint´t´eparluimeˆme,cad erpre f I est la fonction f I : t 1      t n → f ( t 1      t n ).Laseulelatitudequiestdonne´e estdansl’interpr´etationdespr´edicats(qu’onidentifie`aunsous-ensemblede T Fn pourunpre´dicatd’arit´e n ) Intereˆtdesmode`lesdeHerbrand: iln’yapas`achercherledomaineniles interpre´tationsdefonctions. Limite:certainesformulesn’ontpasdemod`elesdeHerbrand(danslasig- naturedonne´e). Re´sultatfondamental(th.deHerbrand):uneformuleuniverselle(i.e.de la forme ∀ x 1    x n ϕ ou` ϕ necontientpasdequantification)aunmod`elesiet seulementsielleaunmode`ledeHerbrand.Cer´esultatseramontre´plusloin. De plus le paragraphe suivant montre qu’on peut transformer une formule en uneformuleuniverselleenpr´eservantlasatisfaisabilite´(maispasl’´equivalence logique).

1.3Mode´lisation Lalogiquedupremierordreesttre`sexpressiveetpermtdemode´liserde nombreuxprobl`emes.Pourcorrespondretotalement`acequiestutileenpra- tique,ilmanquedepouvoirparlerd’ensembleetd’unpre´dicatfondamental l’e´galit´equiadespropri´et´esparticuli`eres.L’axiomatisationdelathe´oriedes ensemblesn’estpaslesujeticietcelledel’e´galite´neseraqu’´evoqu´ee. Uneth´eorieestl’ensembledesconsequenceslogiquesd’unensembledefor-´ mulescloses(lesaxiomesdelathe´orie).