[PDF] Examen - 20 décembre 2017 20 déc. 2017 L'

View - Download Examen - 20 décembre 2017

Previous PDF

Next PDF

Licence Informatique, semestre 5 2017-18

Elements de logique pour l'informatique (Info 315) 29 mai 2018 http://www.lri.fr/ ~paulin/Logique

Examen - 20 decembre 2017

L'examen dure 2 heures. L'enonce est compose de 2 pages. Toutes les reponses devront ^etre clairement

justiees. Le seul document autorise est une page A4 manuscripte recto-verso. Le tableau resumant les regles du systeme G est donne a la n du sujet. Inscrivez votre nom sur chaque copie et numerotez-les. Cacheter toutes les copies. Re- copier le numero d'anonymat sur les intercalaires et sur le QCM.

Exercice 1QCM (5 points)

Le numero d'anonymat de la copie principale doit ^etre reporte sur l'enonce du QCM.Utiliser un style bleu ou noir pour cocher les cases.N'oubliez pas de rendre le QCM avec vos copies. Exercice 2(5 points)On considere une logique dont la signature est composee de trois predicats unairesP,QetR. 1.

F aireune preuv epar r esolutionde la form ule

on prendra soin de bien expliciter les dierentes etapes. 2. P ourc hacundes s equentssuiv ants,dir esi ils son tprouv ablesdans le syst emeG. Si oui don ner l'arbre de preuve, sinon donner une interpretation dans laquelle le sequent est faux. (a) ( 9x;P(x))Q(x));(9x;Q(x))R(x))` 9x;P(x))R(x) (b) ( 9x;P(x))Q(x));(8x;Q(x))R(x))` 9x;P(x))R(x) Exercice 3(5 points)On considere un langage dans lequel on a une constantemoi, le predicat d'egalite et les predicats suivants : |objet(o) qui represente le fait queoest un objet. |appartient(x;o) qui represente le fait qu'un objetoappartient a un individux(xest le proprietaire deo). |ami(x;y) qui represente le fait que les individusxetysont amis. |prete(x;o;y) qui represente le fait que l'individuxpr^ete l'objetoay. 1. Donner les form uleslogiques qui corresp ondentaux phrases suiv antes (a) Je ne pr ^etequ' ames amis et que des c hosesqui m'appartiennen t. (b) Si un ob jeta plu sieurspropri etairesdi erentsalors ceux-ci son tamis. (c)

T outob jeta (au moins) un propri etaire.

(d)

J'ai pr etetou tce qui m'appartien t.

(e) Un ob jetn'est pr eteau plus qu' aune seule p ersonne. 2. Donner les form uleslogiques puis expliciter en langue naturelle les armation scorresp ondant a lanegationdes formules 1d et 1e de la question precedente. (a)9o;appartient(moi;o)^ 8x;:prete(moi;o;x) Il existe un objet qui m'appartient et que je n'ai pas prete. (b)9xy z to;prete(x;o;y)^prete(z;o;t)^y6=t Il existe un objet qui est prete a deux personnes dierentes. 3. On consid ereun domaine a vec5 elementsA,B,p,qetrdans lequelp,qetrsont des objets. (a) Prop oserun mo deledes cinq form ulesde la question 1. 1 (b)Prop oserun mo deledes trois premi eresfor mulesde la question 1 et de la n egationdes formules 1d et 1e. Exercice 4(8 points)Les questions de ce probleme sont largement independantes. On considere une logique dont la signature est composee de deux predicats unairesP,Q. La signature donnee est un cas particulier de signaturemonadiquec'est-a-dire avec que des sym-

boles de predicat unaires et pas de symbole de fonction. Cette logique est decidable et on va justier

dans ce cas particulier que l'on peut toujours eliminer les quanticateurs. SoitAune formule etIune interpretation du langage dont le domaine estD. A tout element du domained2 D, on associe un couple de booleeens qui sont les valeurs de verite deP(x) etQ(x) dans un environnement dans lequelxa la valeurd, c'est-a-dire le couple (val(x7!d;P(x));val(x7!d;Q(x))).

On note(d) ce couple.

1. Dans cette question on consid ereune in terpretationparticuli ereNdont le domaine est l'ensemble des entiers naturels, dans lequel le predicatPest interprete par la propriete \^etre un entier pair" et le predicatQpar la propriete \^etre une multiple de 3". Quelles sont les valeurs de(1),(2), (3),(4),(5),(6). 2. Com biende v aleursdi erentesprend (d) dans l'interpretationNde l'exemple precedent? Com- bien de valeurs dierentes peut prendre(d) dans le cas d'une interpretationIquelconque (don- ner un maximum et un minimum)? 3. On in troduitun erelation binaire d'd0entre les elements deDdenie pard'd0si et seulement si(d) =(d0), c'est-a-dire que les valeurs de verite des predicats sont les m^emes pourdetd0. Il est facile de voir qued'd0est une relation d'equivalence qui a un nombre ni de classes d'equivalence. On dit que deux environnementset0sont equivalents si pour toute variablex, on a(x)'0(x). On note egalement'0cette equivalence entre environnements. Montrer que pour toute formuleAet pour n'importe quels environnementset0, si'0alors val(;A) =val(0;A) (on pourra raisonner par recurrence sur la formuleAet traiter juste le cas de formules qui ne contiennent que le quanticateur8, et les connecteurs de negation et de conjonction). 4. On construit apartir de Iune nouvelle interpretationI0en choisissant comme domaine un sous-ensembleD0 Dforme exactement d'un element deDdans chaque classe d'equivalence.

C'est-a-dire que

|8d2 D;9d02 D0;d'd0 |8xy2 D0;x'y)x=y (a) Justier le fait que D0est un ensemble ni et donner une borneMsur sa taille. (b) Construire en suiv antcette m ethodeune in terpretationN0pour l'interpretationNde la question 1 (on indiquera le domaine et l'interpretation des deux predicats sur ces valeurs). (c) Mon trerque p ourtout e nvironnementde domaineD, il existe un environnement0sur le domaineD0tel que'0. (d) Mon trerdans le cas g eneralque p ourn'imp ortequelle form uleAet n'importe quel envi- ronnement0sur le domaineD0de l'interpretationI0, la valeur deAdans l'environnement

0est la m^eme dans l'interpretationIet dans l'interpretationI0, c'est-a-direvalI(0;A) =

val

I0(0;A).

5. On in troduitMnouvelles constantesa1;:::;aMdans la signature. (a) Expliquer commen ton p euttransfor mertoute form uleclose Aen une formule closeAM sans quanticateur telle queAest valide si et seulement siAMest valide. (b) Appliquer v otrem ethodeaux form ules( 8x;P(x)))(9x;P(x)) et (9x;P(x)))(8x;P(x)). Dire si les formules obtenues sont ou non valides. 6. En d eduireune m ethodep ourd eciderde la v alidited' uneform uledans le langage. 2 Rappel des regles logiques du systemeGhypothese(Hyp)A;`;Agauchedroite

??;```;?>`>;``;>:`;A:A;`A;``;:A^A;B;`A^B;``;A`;B`;A^B_A;`B;`A_B;``;A;B`;A_B)`;A B;`A)B;`A;`;B`;A)B8P[x t];(8x;P);`(8x;P);``;P`;(8x;P)x62Vl(;)9P;`(9x;P);`x62Vl(;)`;(9x;P);P[x t]`;(9x;P)3

quotesdbs_dbs29.pdfusesText_35

[PDF] PLANNING DES EXAMENS DE RATTRAPAGE DE S2 FILIERE

[PDF] Examen Matière : Marketing International - L 'ENT de IGA Rabat

[PDF] Première LMD ST (S1) ~ Faculté des Sciences (Univ Tlemcen)

[PDF] Université des Sciences et de la Technologie Houari - usthb

[PDF] Épreuves uniques - Enseignement secondaire, 2e cycle

[PDF] IMM 5753F : Demande d 'examen médical - Citoyenneté et

[PDF] Les métiers des Sciences

[PDF] Microscopie en bacteriologie - Direction des laboratoires

[PDF] Calendrier Primaire 2017-2018

[PDF] Épreuve unique - Enseignement secondaire, 2e cycle - Histoire et

[PDF] Épreuves uniques - Enseignement secondaire, 2e cycle - Science et

[PDF] coproculture - XLABS laboratoire

[PDF] Nederlands - vwo: vakspecifieke informatie centraal examen 2016

[PDF] Examen normalisé

[PDF] Examen normalisé