[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.2Exercice5.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-CharlesAttention: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.2Exercice3.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 uproblè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éparQuestion5.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.