//img.uscri.be/pth/47adc81a021fce31f884a0455e63585b9cab807d
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Cours : Logique du premier ordre

13 pages
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 ...
Voir plus Voir moins

Vous aimerez aussi

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´xe. Lessymbolesdefonctionsetlesvariablespermettentdede´nirlestermescomme vupr´ece´demment.Poursimplieronsupposeraquelensembledessymbolesde fonctions contient une constante au moins. L’ensemble F orm des formules est le plus petit ensemble tel que r R darite´ 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ϕ ∈ 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´nitlanotiondoccurerncelibre,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´eparlequanticateur 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 estlensembledese´tudiantsdelicence D E D est l’ensemble des entiers positifs ou nuls N D estlensembledestrianglesisoc`eles T ri Etape 2 : donner un sens aux fonctions. A chaque symbole f F darit´e n on associe une fonction I ( f )note´eaussi f I , de D n D quiestsoninterpre´tation. Enparticulieruneconstanteserainterpre´t´eparune´l´ementdudomaine. exemple : Laconstantecsinterpr`eteparPierreDupont(pourunchoixdedomaine D = D E ) – La fonction f darit´e2sinterpr`eteparladdition(pourunchoixdedo-maine D = N ) – La fonction s sinterpre`tecommelesymme´triqueparrapport`alorigine (pour un choix de domaine D = T ri ) Noterquoninterpr`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 darit´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 peutsinterpre´terpar suivre le meme cursus , les ˆ cursus´etantmath-info,physique-infoouinformatique(pourunchoixde domaine D = D E ). – La relation binaire bg sinterpre`te (pour un choix de domaine D = N ). – La fonction isoc sinterpre`te ˆetreisoce`le (pour un choix de domaine D = T ri ) Une structure h D I i estladonn´eedundomaine D etduneinterpr´etation I quiinterpre`techaquesymboledefonctionetderelation. Etape 4 :donnerunevaleur1pourvraiou0pourfaux`auneformuledans une structure h D I i . Onsaitlefaireintuitivement,maislade´nitionformelledemandea`eˆtreplus ´ is prec . Lapremi`erediculte´estlexistencedevariableslibresauxquellesilfaut 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 cestcalculerlavaleurdev´erite´ ϕ IA par : p ( t 1      t n ) IA = 1 ssi p I ( t I 1 A      t InA ) – ( ϕ ψ ) 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 : ilnyapasune´tudiantquisuitlemˆemecursusquetouslesautres(ilnest paspossibledesuivredeuxcursusdie´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´nition,si ϕ estuneformuleclosealorslavaleurdeve´ritede ϕ IA ´ estind´ependantede A et on la note ϕ I . On dit que la formule est satisfaisable sicettevaleurest1(i.e.vrai).Danstoutelasuiteonnesinte´resseraqua`des
4 CHAPITRE 1. LOGIQUE DU PREMIER ORDRE formulescloses.Quandlaformulenestpasclose,onconsid`ereusuellementsa cloˆtureuniversellecesta`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`ledunensemble deformulesclosesΓestuneinterpre´tationquiestmod`eledechaqueformulede Γ. Uneformuleclosequinapasdemode`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´equencelogiquedunensembledeformulescloses si ϕ estvraidanstoutmode`ledeΓ,e´critΓ | = ϕ . The´orie :uneth´eorieestlensembledescons´equenceslogiquesdunensemble deformulescloses.Parexemplelath´eoriedesgroupesestlensembledesformules logiques qui sont vraies dans tous les groupes. 1.2.3Mode`ledeHerbrand Uneinterpr´etationdeHerbrandestuneinterpre´tationdontledomaine D est lensembledestermesetunsymboledefonctionestint´t´eparluimeˆme,cad erpre f I est la fonction f I : t 1      t n f ( t 1      t n ).Laseulelatitudequiestdonne´e estdanslinterpr´etationdespr´edicats(quonidentie`aunsous-ensemblede T Fn pourunpre´dicatdarit´e n ) Intereˆtdesmode`lesdeHerbrand: ilnyapas`achercherledomaineniles interpre´tationsdefonctions. Limite:certainesformulesnontpasdemod`elesdeHerbrand(danslasig-naturedonne´e). Re´sultatfondamental(th.deHerbrand):uneformuleuniverselle(i.e.de la forme x 1    x n ϕ ou` ϕ necontientpasdequantication)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,ilmanquedepouvoirparlerdensembleetdunpre´dicatfondamental le´galit´equiadespropri´et´esparticuli`eres.Laxiomatisationdelathe´oriedes ensemblesnestpaslesujeticietcelledele´galite´neseraqu´evoqu´ee. Uneth´eorieestlensembledesconsequenceslogiquesdunensembledefor-´ mulescloses(lesaxiomesdelathe´orie).