[PDF] Calcul propositionnel - LIS lab



Previous PDF Next PDF
















[PDF] logique propositionnelle table de vérité

[PDF] calcul propositionnel formel

[PDF] calcul des propositions exercices corrigés

[PDF] le resultat d'une multiplication est

[PDF] comment calculer le taux de possession du stock

[PDF] cout de stockage annuel

[PDF] calcul du stock moyen

[PDF] exercice cout de passation et possession

[PDF] calcul tangente formule

[PDF] calcul tangente fonction

[PDF] calcul tangente en ligne

[PDF] calculer tangente calculatrice

[PDF] a quoi sert le sinus

[PDF] calcul taux d'évolution annuel moyen excel

[PDF] taux d'évolution successif

14/05/2013,11h15, AmphiMarion

Durée:2heures

Documentsautorisés

LogiqueetCalculabilité

Licence3Informa tiq ue(etMaths)

Attention:donnezautantdedé tai lsquevousjugeznéc essaire;dessimples copie s-collers-miroirsdevos

notesdecou rsne serontpasjugéssatisf aisants.En bref,montrez quevous avezcompris.

Choisissez4exercicesparmiles6exer cicesp roposés.Abord ezun5èmeexerciceseulem ents'il vou srestedu

temps.

Calculpropositionnel

Exercice1.Pourchaquefor mule!

i ,i=1,2,3,én umérezsesmodèles: 1.! 1 :=(P!(Q"P))#Q#(P"¬Q); 2.! 2 :=( P$(Q"P))!Q; 3.! 3 :=(P#¬Q)!((Q"P)"P).

Exercice2.Pourchaquefor mule!

i ,i=1,2,3,de l'Exer cice1,proposezuneformule" i enfor menormale conjonctiveéquivalenteà! i .Po urlaformule! 3 ,dét aillezaussilesétapesdel' algorithmedemi seenform e clausale.

Calculdesprédicats

Exercice3.Oncons idèrelelangageS=(%,S

R )où S R Enutil isantcelangage,exprimezlesénoncéss ui vantsenlogiquedupremier ordre.

1.Lesher bivor enemangentquedesvégétaux.

2.Aucun herbivorenema ngetouttypedevégétal

3.Ilya desvégéta uxq uen emang eaucunherbivore

4.Lespa ndasso ntdesherbivoresquine consommentqued esbamb ous

Exercice4.ConsidérezlelangageS=(S

F ,S R )donnépar S F ={(f,2)}S R ={(P,1),(R,2)}, etla S-structureMsuivante: D M ={0,1,2,3}, f M (x,y)=x+ymod4, P M ={0,2},R M ={(0,1),(1,2),(2,3),(3,0)}.

Pourchaquefo rmule!

i ,i=1,2,3,4,5, 1.! 1 :=&x'yP(f(x,y)); 2.! 2 :='y&xP(f(x,y)); 3.! 3 :=&x(P(x)!'y(R(x,y)#P(y))); 4.! 4 :=&x'y(R(x,y)#P(f(x,y))); 5.! 5 :='y&x(R(x,f(x,y))#(P(x)!P(f(x,y))));

évaluez(ditessiest vraieounon)!

i parrapp ortàlastructureM.Po urlaformule! 1 justifiezaussivotre réponse:détailleztouteslesétap esnécessairesàéval uercetteformule. 1 Licence3Informa tiq ue(etMaths)LogiqueetCalculabilité,p.2

Exercice5.Considérezlaformulesuiva nte:

1 :='x(P(x)#&y((&xR(x,y))"R(y,x))).

1.Tran sformezlaformule!

1 enun eformule! 2

équivalenteenformeprenexe.

2.Skol emisez!

2 :tr ansformezlaformule! 2 enun eformuleeq uisatisfiable! 3 ,av ec! 3 universelle(avec desqua ntificateurs&seulement)etenformeprenexe.

3.Mettez lamatricede!

3 enfo rmenormaleconjonct ive.

4.Dédui sezunensembledeclauses univers ellesequisatisfiablea vec!

1 Exercice6.Utilisezlecalculdelarésol ution pourmontrerqu elaform ule!:=&xP(x)estconséq uence logiquedel'ensembledesfo rmules!={&yQ(y),&z(Q(z)"P(z))}.

Pourcefaire:

1.tran sformez!({¬!}enun ensembl eequisatisfiable"declau sesuniverselles;

2.dédui sez,enutilisezlesrèglesd efact orisationet/ourésoluti on,lacl ausevidede".

28/06/2013,8h30, AmphiMarion

Durée:2heures

Documentsautorisés

LogiqueetCalculabilité

Licence3Informa tiq ue(etMaths) - sitedeSaint-Charles

Attention:donnezautantdedé tai lsquevousjugeznéc essaire;dessimples copie s-collers-miroirsdevos

notesdecou rsne serontpasjugéssatisf aisants.En bref,montrez quevous avezcompris. Cetexamen comporteunelargechoi xd'exercices; vousde vezrésoudre5 exercices defaçoncorrectepour obtenirlanote maximum.

Calculpropositio nnel

Exercice1.Considérezlesformulessuiva ntes:

1.! 1 :=p!¬q; 2.! 2 :=(p!q)"(¬p!r); 3.! 3 :=(p"q!¬r)!(¬p"r); 4.! 4 :=( ¬p"q"¬r"¬s)!(¬p"r)!(¬s"p)!p.

Repondezauxquestions suivantes:

Question1.1Lesquellesparmicesformulesso ntenformenormale conjo nctive?Justifiezvotr eréponse.

Question1.2Si!

i n'estpasenform enormaleco njon ctive,appliqu ezl'algorithmepourtra nsformercettefor-

muledansune formuleéquival enteenforme normaleconjonctive;dét ailleztouteslesétapesdel'algor ith me.

Question1.3Pouri=1,2,3,4,ap pliquezl'algorithmedeDPL L(Davis-Putnam-Logemann-Loveland)pour trouverunmodèledelafo rmule,o ubienpourmontrer quecette formul eestcontradictoire.

Calculdesprédicats

Exercice2.Onsepr oposed etraduiredelalanguefr ancaise enlogiquedupremierordrelesp hrases suivantes:

1.Marcu sétaitunpompéen.

2.Tou slespompéensétai entdesro mains.

3.Césarét aitsouvera in.

4.Tous lesromainsétai entfidèl esàCésaroulehaissaient.

5.Chacun estfidèleàquelqu 'un.

6.Lesper sonnesn 'essayentd'assassinerqu elessouverainsauxquelsilsn esontpasfidèles.

7.Marcu saessayéd'assas sin erCésar.

Question2.1Proposezunlangagedupr emierord repourmodelisercesphrases . Question2.2Pourchaqueph raseenfrancais,propo sezuneformuleenlogiq ued upremierordrecorrepon- dante. 1 Licence3Informa tiq ue(etMaths) - sitedeSaint-CharlesLogi queetCal culabilité,p.2

Exercice3.Considérezlaformulesuiva nte:

#x$y(R(x,y)%P(x,s(y)))

Question3.1Quelestlela ngaged ecettef ormule?

Question3.2ConstruisezunmodèleMdecettefo rmule. N &='etN&|=!.

Attention:quandvouspropos ezu neS-structure,prenezgardeàsoigne usementdéfinirsondom aineet,pour

toutsymboledu langageS,soninterprétation.

Exercice4.SoitS=(S

R ,S F ),oùS R ={(R,2),(S,1)}etS F ={(f,1)},le langag edelaformule !:=$x((#yR(x,f(y)))"($y(R(x,y)%S(y)))).

ConsidérezlesS-structuressuivantes:

1.D M 1 :={a,b},R M 1 :=',S M 1 :={a},f M 1 (a):=aetf M 1 (b):=b. 2.D M 2 :={a,b},R M 2 :={(a,b)},S M 2 :={a},f M 2 (a):=aetf M 2 (b):=a; 3.D M 3 :=N(lesnombr esentiersnon-négatifs) ,R M 3 :={(x,x+1) |x(N},S M 3 :=',f M 3 (x):= x+1; 4.D M 4 :=N,R M 4 :={(x,x+1)|x(N},S M 4 :={1},f M 4 (x):=x+2; 5.D M 5 :=N,R M 5 :={(x+1,x)|x(N},S M 5 :={1},f M 5 (x):=x+1.

Pourchaque i=1,...,5,di tessilarelatio nM

i |=!estvrai eounon.Justifiez votrer éponse. Exercice5.Considérezlaformulesuiva nte(la mêmequecelledel'exercice précédent): !:=$x((#yR(x,f(y)))"($y(R(x,y)%S(y)))).

Question5.1Transformezlaformule!enun eformule!

2

équivalenteenformeprenexe.

Question5.2Skolemisez!

2 :tr ansformezlaformule! 2 enun eformuleeq uisatisfiable! 3 ,av ec! 3 universelle (avecdesquanti ficateurs $seulement)etenformeprenexe.

Question5.3Mettezlamatrice de!

3 enfo rmenormaleconjon ctive. Question5.4Déduisezunensembledecla usesun iversellesequisatisfia bleav ec!.

Exercice6.Considérezlesproblèmesd'un ificatio nsuivants(lasignatur eétant{(c,0),(f,1),(g,2)}):

2.(g(x,c),g(f(y),c)),(z,g(c,x)),(y,z).

Pourchacundeces problèmes,exécutezl' algori thm eUNIFIERpourtrouverun unificateurprincipald u

problèmeoubienmontrerqu 'untelu nificateurn' existepas.Détaillezt outeslesétapesdel'a lgori thme.

Exercice7.Utilisezlecalculdelaréso lution pourmontrerqu elafor mule!:=$x(P(x)%R(x))est conséquencelogiquedel'ens embledesformules!={$y(P(y)%Q(y)),$z(Q(z)%R(z))}.

Pourcefaire:

1.tran sformez!){¬!}enun ensembl eequisatisfiable"declau sesuniverselles;

2.dédu isez,enutilisezlesrèglesd efa ctorisationet/ourésoluti on,la clausevidede".

Date:14/05/ 201 4,8h30,AmphiPeres

Durée:2heures

Documentsauthorisés

CoursLogique etCalculabilité

Licence3Informat iqu e(etMaths),Aix-MarseilleUniversité

Examen

Attention:donnezautantdedé tai lsquevousjugeznéc essaire;dessimples copie s-collers-miroirsdevos

notesdecou rsne serontpasjugéssatisf aisants.En bref,montrez quevous avezcompris.

Cetexamen comporteunchoixd' exercicesvarié;v ousdeve zrésoudre5exercicesdefaçonc orre ctepour

obtenirlanote maximum.

Calculpropositionnel

Exercice1.Considérezlaformule

Question1.1.Calculezunensemblede clauses !telquemod(!)=mod(!).(Finquestion1. 1) Question1.2.Utilisezl'algorithmed eDavis-Putnam-Logemann-Lovelandpourcal culerunm odèlede!,ou bienpourmo ntrerque!estinsa tisfaisable.(Finquestion1. 2)

Calculdesprédicats

Exercice2.Oncons idèrelelangageS=(S

f ,S r )oùS f :=!et S r Enutil isantcelangage,exprimezlesénoncéss ui vantsenlogiquedupremier ordre.

1.Lesch iensai mentleursmaîtres.

2.Desch atshaï ssentleurspropri étaires.

3.Lesch atsso ntlesmaîtresdeleur spropriétair es.

4.Lesch iensneh aïssentquelesch atsqui nelesaimentpas.

Exercice3.ConsidérezlelangageS=(S

f ,S r )donnépar S f :={(f,1),(o,0)}S r :={(R,2)}, etla S-structureMsuivante: D M :={0,1,2,3}, f M (x):=(x$1)m od4,o M :=0, R M :={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}. Question3.1.Représentezcettestructurecom meungraph eétiqueté.(Finquestion3. 1)

Question3.2.Pourchaquefo rmule!

i ,i=1,...,6, 1 :=%x(R(x,f(o))#R(o,x)); 2 :=%x&y(R(x,y)#R(y,x)); 1 Licence3Informa tiq ue(etMaths)LogiqueetCalculabilité,p.2 3 :=%xR(f(x),x); 4 :=%x(R(x,f(o))"&yR(x,y)); 5 :=&x(R(o,x)!%y(R(o,y)"R(x,y))); 6 :=%x(R(o,x)"&y(R(o,y)!¬R(x,y))); ditessiM|=! i ounon. Justifiezbrièv ementvotreréponse.(Finquestion3. 2)

Question3.3.Pourlaformule !

3 ci-dessus,détailleztouteslesétapes nécessairesàl'éva luer.(Finquestion 3.3)

Exercice4.Considérezlaformulesuiva nte:

1 :=%x(Q(x)!&y((%xQ(x))"R(y,x))).

1.Tra nsformezlaformule!

1 enun eformule! 2

équivalenteenformeprenexe.

2.Skol emisez!

2 :tr ansformezlaformule! 2 enun eformuleequ isatisfiable! 3 ,av ec! 3 universelle(avec desquan tificateurs%seulement)etenformeprenexe.

3.Mettez lamatricede!

3 enfor menormaleconjo nctive.

4.Dédui sezunensembledeclauses univers ellesequisatisfiablea vec!

1 Exercice5.Considérezl'ensemble!declaus esdonnépar

Question5.1.Listeztouteslesinfér encesducalculdelarés olutio nquevouspouvezfa ireàpa rtirdel'ensem ble

!.Po urchaqueinfér ence,détaillezlarègle(fa ctorisationourésolu tion)utilisée,lasubstit ution utiliséeetles

deuxlittéra uxunifiésparcettesubstituti on.(Finquestion 5.1)

Question5.2.Utilisezlecalculdelaréso lution pourmontrerqu ecetensem bleesti ncohérent.(Finquestion 5.2)

Calculabilité

Exercice6.ConsidérezlamachinedeTu ringda nslafiguresuivante: (Rappel:unetransiti on delaforme selitd elafaçonsui vante :silam achine estdansl'ét atq i etla têtedele cturelitle symbole",alorsonremplacecesymbolepar six=g,àladroitesix=d,etonserend dansl'étatq j Question6.1.Exécutezlamachines url'en tréeab. 1 (Finquestion6. 1) Question6.2.Soitwunmots url'alpha bet{a,b};qu ecalculecett emachinesurentrée w?Ju stifiezvotre réponse.(Finquestion 6.2)

1.Ondénotera uneconfigurati ondel amac hinecommeun couple(q,w)oùqestunét atde lamachine,etwestunmot

avecunelet tresoulig néeselonlapositio ndelatêtedelecture.Parexem ple,laconfigurat ionin itialesurl'entréeabest(q0,ab).

Date: 27/06/2014,de8h3 0à1 0h30,AmphiMarion

Durée:2heures

Documentsauthorisés

CoursLogique etCalculabilité

Licence3Informat iqu e(etMaths),Aix-MarseilleUniversité

Examen

Attention:donnezautantdedé tai lsquevousjugeznéc essaire;dessimples copie s-collers-miroirsdevos

notesdecou rsne serontpasjugéssatisf aisants.En bref,montrez quevous avezcompris.

Cetexamen comporteunchoixd' exercicesvarié;v ousdeve zrésoudre5exercicesdefaçonc orre ctepour

obtenirlanote maximum.

Calculpropositionnel

Exercice1.Enutil isantlaméthodedelacoupure,véri fiezlava liditédesconséquenceslo giquess uivant es:

1.{p!¬q"r,q!p#¬r}|=r!q;

2.{¬p!q,r!¬p}|=¬p!¬r!q;

3.{p!r#t,t"s!¬q}|=¬(p#q);

4.{s!r#p,q}|=¬r#¬s#p.

Calculdesprédicats

Exercice2.Aprèsavoirclai rementdéfinilelang ageutilisé,exprimezleséno ncéssuivantsenl ogique du

premierordre.

1.Lesenfa ntsded euxparentsauxyeux bleuson tforcémentlesy euxbleus.

2.Lor squ'unenfantalesyeuxbleus,onnep eutpasa

rmerquesesd euxparentso ntlesy euxbleus.

3.Unenfa ntded euxparentsauxy euxbrun speutavoi rlesyeuxbleusoubruns .

4.Lors qu'unepersonnealesyeuxbruns,aumo insundesesdeuxparentsal esyeu xbruns .

Exercice3.ConsidérezlelangageS=(S

f ,S r )donnéparS f :={(f,1),(o,0)}etS r :={(R,2)},etla

S-structureMtellequeD

M :={0,1,2,3,4}etoù l'inter prétationdessymbolesest: o M :=0 ,f M (0):=0 ,f M (1):=2 ,f M (2):=3 ,f M (3):=4 ,f M (4):=1 , R M :={(0,1),(2,0),(0,3),(4,0)}. Question3.1.Représentezcettestructurecomm eungraph eétiqueté.(Finquestion3. 1)

Question3.2.Pouri=1,...,5,di tessiM|=!

i ounon (justifiezbr ièvementvotreréponse): 1 :=$x(R(f(x),o)"R(o,f(x))); 2quotesdbs_dbs5.pdfusesText_9