2/3 – Langage logique

Description

• cours - matière potentielle : analyse syntaxique

Universite 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

Sujets

• Analyse syntaxique
• Mathieu
• Logique
• Syntaxe
• Elements
• Formule
• Symbole
• Menstruation
• Problème

Informations

• Publié par: renef
• Nombre de lectures: 38
• Langue: Français

Extrait

Universit ´ ePierreetMarieCurie–Paris6 http://www-spi.lip6.fr/~jaume/LXSTS.html

Ann ´ ee2011-2012 Introduction`alalogique(LXSTS) Mathieu Jaume [e-mail]

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’ensembleF p Σleenunmbsetrap’drifie´da`inmuorsfdesesttionposisproeuedgoqilelaelds p de symbolesdepropositions(d´esignantdesassertionsatomiques,c’esta`diredesassertionsquin’ontpas´ete´ obtenues`apartird’autresassertions)etd’unensembleΣ c de connecteurs logiques permettant de construire desformules`apartird’autresformules.Unformuledelalogiquedespropositionsestdoncune´le´mentde ?1 l’ensembledessuitesfiniesdesymbolesappartenant`aΣ p ∪Σ c . On note (Σ p ∪Σ c ensemble .Toutefois,) cet touslese´le´mentsdecetensemblenesontpasdesformulesdelalogiquedespropositions.Parexemple,si petqsont des symboles de proposition et si l’ensemble Σ c contient 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 ∪Σ c nhqieucseirutsceule.Plustuneformse)duoseroutp´errxioeenst ceproble`meetrele`ventd’uncoursd’analysesyntaxique.Danstoutcequisuit,onconsid`ereraqu’unetelle analyseade´ja´ete´effectue´e.  La syntaxe abstraite des formules deF p ´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`Σ p re`dlareecnotisnoeΣns’eblem c ={¬,∧,∨,⇒}poe´aretdseuesusuelurslogiqe´po’le´tpecxE.surtera¬ ? 1. SiAest un alphabet, on noteAdessmbleensel’teuinisfid’esl´´enemeedstA.

3