2/3 – Langage logique
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Langue
Français
- cours - matière potentielle : analyse syntaxique
- 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
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
