2/3 – Langage logique
5
pages
Français
Documents
Cet ouvrage est disponible dans votre offre d'abonnement
5
pages
Français
Documents
Cet ouvrage est disponible dans votre offre d'abonnement
Publié par
Langue
Français
cours - matière potentielle : analyse syntaxiqueUniversite Pierre et Marie Curie – Paris 6 Annee 2011-2012 Introduction a la logique (LXSTS) Mathieu Jaume 2/3 – Langage logique 1 Un langage pour quoi faire ? Un langage pour specifier, definir, raisonner. Exercice 1. 1 Donner la specification du probleme du tri par ordre croissant des elements d'une liste d'entiers. Exercice 1. 2 Trouver un probleme, dont vous enoncerez clairement la specification, pour lequel vous definirez deux procedes differents de resolution (satisfaisant exactement la meme specification).specification du probleme du tri par ordre croissant des elements symbole de proposition formule de la logique des propositions regles arbre de syntaxe abstraite elements probleme formules formule
Voir
Publié par
Langue
Français
Universit´ePierreetMarieCurie–Paris6 http://www-spi.lip6.fr/~jaume/LXSTS.html
Ann´ee2011-2012 Introduction`alalogique(LXSTS) Mathieu Jaume Mathieu.Jaume@lip6.fr
2/3 – Langage logique
1 Unlangage pour quoi faire? Unlangagepoursp´ecifier,d´efinir,raisonner. Exercice1. 1borpme`ltudeapirp´asifiecticaduonsee´´lmenest’dnurordrecroissantdteiselrlneonD d’entiers. Exercice1. 2pon,leurficciioataltne´psialcemeruqleovsuvuorTsue´tnovrezeoncnproberune,dol`em d´efinirezdeuxproc´ed´esdiffe´rentsdere´solution(satisfaisantexactementlamˆemesp´ecification).
2 Qu’estce qu’un langage? 2.1Quelquesingr´edientsd’unlangage – delasyntaxe... – dessymboles (un alphabet) – desmots (un lexique) –unecaract´erisationdessuitescorrectesdemots(unegrammaire) Analyse syntaxiquensoeerinadtrgenammatrnsreuiecsccoasnireisnuD:e´etmrespecteuephraser “arbre de syntaxe abstraite” (ASTAbstract Syntax Tree) – delaequnait´sme... –euSma´eiqnt:qieuesdtleuecrmosunit´eslinguistEedutesudedsnnoitisop–Petit Larousse, 1994 –permetd’attribuerdusens,unevaleur,uneffet,etc.a`unephrase,uneexpression,unprogramme. Exemple 2.1 –Expressionarithm´etique:2+3×4 Leverl’ambigu¨ıte´: –r`eglesdepriorit´edesop´erateursarithm´etiques –parenthe´sage(syntaxeconcre`te) Se´mantique:2+(3×4)14 – Phrases: –dnraseeg´nteemesivreatd’sse.Deuxcontcudsrueate´tneiteinelrpesl´rlpa–Var Matindu 13/07/94 –Pierre prend la boule et la lance. Syntaxe?Se´mantique? 2.2Quelquesingre´dientsd’unlangagelogique Unlangagelogiquepermetd’exprimerdesfaits(des´enonce´s)quipeuventeˆtrevraisoufauxetdeles combiner entre eux. – Combinerdes faitsviades connecteurs logiques –et (conjonction):∧ –Il est beau et il est intelligent.
1
–Il est beau mais il est intelligent. – or,toutefois, pourtant, certes ... –)tnionn(noage´:¬ –Il n’est pas beau. –Il n’est plus beau. –ou (disjonction):∨ –Il ne pleut pas ou je prends mon parapluie. –JPa`as.rijeouissuexurselliuseBa`s(ou exclusif XOR) –si-alors (implication):⇒ –Si il pleut alors je prends mon parapluie. –Si tu ne manges pas ta soupe, alors tu n’auras pas de dessert. –ndsuuait,artseessautsrolate´gname.soupS –Une condition suffisante pour que j’ai mon parapluie est la pluie. –gnamedtsetressedUne.upsosaerno´ncesecenoiditravoirunsairepou –qeiuis´(emtnueeltsiesnce)vale:⇔ –Tu auras un dessert si et seulement si tu manges ta soupe. –CNS:conditionne´cessaireetsuffisante – Quantifiersur des objets : –Lesobjetssontrepre´sente´spardestermes: – Constantes – Variables – Combinaisonde termes avec des symboles de fonction Exemple : (2+ 3)×x 2et3sontdesconstantes,+estunsymboledefonctiond’arite´2,2+3estunterme,×est un symboledefonctiond’arit´e2,xest une variable, (2+ 3)×xest un terme. –Propri´et´essurlestermes:stacide´pruqilppasmeerstdeurss´e Exemple : (2+ 3)×x≤10 ≤ledeymbotunsesa’dt´tire´rpacid.e2 –pour-tout (quantication universelle):∀ –´dae.ltsToonutsulneis´etudian ∀x(etudiant(x)⇒ ∃y ideal(x, y)) –il-existe (quantication existentielle):∃ –xesilI.tnelliavartiusqntiaudets´dete ∃x(etudiant(x)∧travaille(x)) – Occurrencesdei´slseeiravelba(muettes), Occurrence devariables libres – surdes formules logiques : –∀x p(x, y) – (∀x p(x, y))∧(∃y q(y)) –surdesexpressionsmathe´matiques: R 1 –f(x() =x+y)dx 0 R R 1 1 Calculerf(y), ce n’est pas calculer(y+y)dy... c’est calculer(y+z)dz: on renomme 0 0 l’occurrencelie´edeypar une variable fraˆıche. – surdes programmes informatiques : –(define (plus x) (+ x y))
Exercice1. 3lretureanneitbmertuone”Tohrasrr´leaspenRteepxire´fnitseiuqruessceucnsaueurou ´egal`atoutentierstrictementsup´erieur`axlumrgoleurapofen.”:stna´ediesprsuivcatsnetuqieunaltlisi entier(x) “xest un entier naturel” successeur(x,y) “xest successeur dey” inf(x,y) “xinsterf´uraiel´`egoauey”
2
Exercice1. 4nE´emamathes,otiquptirce´nsiofra∃!x p(x) pour exprimer qu’il existe un uniquextel que p(xepoiserltiliansuoi?nmataxelctn’d).mmoCetneirpxcremteetoppr´eriest´
3 Syntaxede la logique des propositions Lalogiquedespropositionsfournitunlangagepermettantd’exprimercertainesassertionspouvantˆetre vraiesoufausses,accompagn´edetechniquespermettantderaisonnersuret`apartirdecesassertionsafin decaract´eriserlesassertionsquisontvraies.Cesassertionspeuventeˆtreobtenuesencombinantd’autres assertions avec des connecteurs logiques (et, ou, ...). Par exemple, ce langage permet d’exprimer la phrase : Siilnepleutpas etque je suis en vacances, (1) alorsjevaegalpala`siouje jardine. quipeutˆetrevuecommelacombinaisondesquatreassertionsatomiques: il pleut(2) je suis en vacances(3) jevaisa`laplage(4) je jardine(5)
La phrase (1) exprime en effet que si l’assertion (2) est fausse et l’assertion (3) est vraie, alors l’assertion (4) oul’assertion(5)estvraie.End’autrestermes,lan´egationdel’assertion(2)etl’assertion(3)impliquent l’une ou l’autre au moins des assertions (4) et (5). Il s’agit donc d’une combinaison des assertions (2), (3), (4) et (5) avec les connecteurssi-alors ,et ,non ,et ou. Nous introduisons ici la syntaxe du langagedelalogiquedespropositionspermettantdecaracte´riserl’ensembledesassertionsquel’onpeut exprimer dans ce langage : ces assertions sont les formules de la logique des propositions. L’ensembleFpΣleenunmbsetrap’drifie´da`inmuorsfdesesttionposisproeuedgoqilelaeldspde symbolesdepropositions(d´esignantdesassertionsatomiques,c’esta`diredesassertionsquin’ontpas´ete´ obtenues`apartird’autresassertions)etd’unensembleΣcde connecteurs logiques permettant de construire desformules`apartird’autresformules.Unformuledelalogiquedespropositionsestdoncune´le´mentde ?1 l’ensembledessuitesfiniesdesymbolesappartenant`aΣp∪Σc. On note (Σp∪Σcensemble .Toutefois,) cet touslese´le´mentsdecetensemblenesontpasdesformulesdelalogiquedespropositions.Parexemple,si petqsont des symboles de proposition et si l’ensemble Σccontient le connecteur binaire∧de conjonction (permettant de combiner deux formules avec unet ),la suite de symbolesp qn’est pas une formule alors que la suitep∧qmneeifnonefsotruc’esfixe,nroo´utmeellsfsse(teeisscmerilruleerurfigseerida`ttnasiafn ope´rateursbinairesentrelesargumentssurlesquelsilss’appliquent).C’estl’analysesyntaxiquequipermet ? ded´eterminersiune´l´ementde(Σp∪Σcnhqieucseirutsceule.Plustuneformse)duoseroutp´errxioeenst ceproble`meetrele`ventd’uncoursd’analysesyntaxique.Danstoutcequisuit,onconsid`ereraqu’unetelle analyseade´ja´ete´effectue´e. La syntaxe abstraite des formules deFp´nnodtnevuostseed’uformuslaeesoar-mdegee`lgenr maire BNF(Bachus Naur Form) :
ϕ::=p| ¬ϕ|ϕ∧ϕ|ϕ∨ϕ|ϕ⇒ϕ
Cettere`gleexprimequ’uneformuleestsoitunsymboledeproposition,soituneformuleobtenueenappli-quant le connecteur¬sur une formule, soit une formule obtenue en appliquant un des connecteurs logiques ∧,∨et⇒sur deux formules. Dans ce qui suit, on noterap,q,r, ... les symboles propositionnels appartenant a`Σpre`dlareecnotisnoeΣns’eblemc={¬,∧,∨,⇒}poe´aretdseuesusuelurslogiqe´po’le´tpecxE.surtera¬ ? 1. SiAest un alphabet, on noteAdessmbleensel’teuinisfid’esl´´enemeedstA.
3
