Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Logique : ENSIIE 1A - contrˆ ole ﬁnal - CORRIG´ E Mardi 11 mai 2010 - Sans docu

Logique : ENSIIE 1A - contrˆ ole ﬁnal - CORRIG´ E Mardi 11 mai 2010 - Sans documents - Sans calculatrice ni ordinateur Dur´ ee : 1h30 Les exercices sont ind´ ependants. Exercice 1 (Logique du premier ordre et syntaxe) exo sur 4 points Question 1 1 point Quand dit-on qu’une variable est libre dans une formule ? Une variable est dite libre dans une formule si elle poss` ede au moins une occurrence libre. Dans la suite de l’exercice, nous consid´ erons le langage du premier ordre L = {R, S, f, a} o` u R et S d´ esignent deux symboles de relation respectivement unaire et binaire, f d´ esigne un symbole de fonction unaire et a d´ esigne un symbole de constante. Soit F la formule suivante : (∀x∃yR(f(x), f(y))) ∧((∀zR(x, z)) ⇒S(x)) Question 2 Les variables x et y sont-elles libres dans la formule F ? Justiﬁez votre r´ eponse en quelques mots. 1 point x est libre dans la formule car il existe deux occurrences libres (les deuxi` eme et troisi` eme oc- currences quand on lit la formule de gauche ` a droite. En revanche y est une variable li´ ee car toutes ses occurrences (une seule) sont li´ ees. Question 3 Transformez la formule F pr´ ec´ edente de mani` ere ` a ce que variables li´ ees et variables libres (´ eventuelles) ne portent pas le mˆ eme nom. 1 point On renomme les variables li´ ees qui ont aussi une occurrence libre. Soit ici le x quantiﬁ´ e uni- versellement. On ne renomme pas les variables libres, on changerait le sens de la formule. (∀u∃yR(f(u), f(y))) ∧((∀zR(x, z)) ⇒S(x)) Question 4 Donnez la formule F[x := t] (c’est-` a-dire la substitution de t ` a la variable x dans F) quand t est le terme f(z). 1 point (∀x∃yR(f(x), f(y))) ∧((∀vR(f(z), v)) ⇒S(f(z))) Cette substitution ne concerne que l’occurrence libre de x. Pour ´ eviter la capture de la variable z (dans le terme t = f(z)) par le quantiﬁcateur, on commence par renommer dans la formule F la variable li´ ee z en v puis on fait le remplacement. D’o` u la formule ci-dessus. Exercice 2 (Uniﬁcation) exo sur 3 points Soit f un symbole de fonction d’arit´ e 3. Soit a une constante. x, y et z sont des variables. Question 5 1 Les termes f(x, x, y) et f(f(y, y, z), f(y, y, z), a) sont-ils uniﬁables ? Si oui donnez un mgu (uniﬁcateur le plus g´ en´ eral), si non, dites pourquoi. 1,5 point On applique l’algorithme d’uniﬁcation (` a base de r` egles) : {f(x, x, y) ≈f(f(y, y, z), f(y, y, z), a)} →(decomposition) {x ≈f(y, y, z), x ≈f(y, y, z), y ≈a} →(elimination de y) {x ≈f(a, a, z), x ≈f(a, a, z), y ≈a} →(elimination de x) {x ≈f(a, a, z), f(a, a, z) ≈f(a, a, z), y ≈a} →(effacement) {x ≈f(a, a, z), y ≈a} Les deux termes sont donc uniﬁables. Le mgu est l’ensemble obtenu ` a la ﬁn, soit {x ≈ f(a, a, z), y ≈a}. Question 6 Les termes f(x, x, y) et f(f(y, y, z), f(y, x, z), a) sont-ils uniﬁables ? Si oui donnez un mgu (uniﬁcateur le plus g´ en´ eral), si non, dites pourquoi. 1,5 point On applique l’algorithme d’uniﬁcation (` a base de r` egles) : {f(x, x, y) ≈f(f(y, y, z), f(y, x, z), a)} →(decomposition) {x ≈f(y, y, z), x ≈f(y, x, z), y ≈a} →(occurrence −x ∈V ars(f(y, x, z))) echec Les deux termes ne sont donc pas uniﬁables. Exercice 3 (Mod´ elisation et m´ ethode de r´ esolution) exercice sur 6,5 points Soit l’´ enonc´ e suivant : 1. Les personnes qui ont la grippe A doivent prendre du Tamiﬂu. 2. Les personnes qui ont de la ﬁ` evre et qui toussent ont la grippe A. 3. Ceux qui ont une temp´ erature sup´ erieure ` a 38◦ont de la ﬁ` evre. 4. Pierre tousse et a une temp´ erature sup´ erieure ` a 38◦. 5. Pierre doit prendre du Tamiﬂu. Question 7 Mod´ elisez en logique du premier ordre l’´ enonc´ e ci-dessus en utilisant les pr´ edicats suivants : • grippe(x) : x a la grippe A. • prendre(x, y) : x doit prendre y. • fievre(x) : x a de la ﬁ` evre. • tousse(x) : x tousse. • temp(x, t) : x a la temp´ erature t. • sup(x, y) : x est sup´ erieur ` a y. 2 On utilisera ´ egalement les constantes 38, Pierre et Tamiflu. 2,5 point : 0,5 par phrase Mod´ elisation en logique du premier ordre : • (a) ∀x(grippe(x) ⇒prendre(x, Tamiflu)) • (b) ∀x((fievre(x) ∧tousse(x)) ⇒grippe(x)) • (c) ∀x∀t((temp(x, t) ∧sup(t, 38)) ⇒fievre(x)) • (d) tousse(Pierre) ∧∃t(temp(Pierre, t) ∧sup(t, 38)) • (e) prendre(Pierre, Tamiflu) Question 8 Prouvez ` a l’aide de la m´ ethode de r´ esolution que la derni` ere aﬃrmation est une cons´ equence logique de l’ensemble des autres aﬃrmations. On rappelle que la m´ ethode de r´ esolution s’applique ` a un ensemble de formules mises sous forme clausale. 2 points pour une mise en forme clausale correcte et 2 points pour une resolution correcte R´ esolution : On va montrer que a ∧b ∧c ∧d ∧¬e est insatisfaisable. Pour cela il faut mettre les formules sous forme clausale. Premi` ere ´ etape mise sous forme prenexe : • (a) ∀x(¬grippe(x) ∨prendre(x, Tamiflu)) • (b) ∀x(¬fievre(x) ∨¬tousse(x)) ∨grippe(x)) • (c) ∀x∀t(¬temp(x, t) ∨¬sup(t, 38) ∨fievre(x)) • (d) ∃t(tousse(Pierre) ∧temp(Pierre, t) ∧sup(t, 38)) • (¬ e) ¬prendre(Pierre, Tamiflu) Seule d contient une variable existentielle t, on introduit la constante de Skolem a. On obtient alors la formule : (d0) tousse(Pierre) ∧temp(Pierre, a) ∧sup(a, 38) Passage ` a la forme clausale : • C1 = ¬grippe(x) ∨prendre(x, Tamiflu) • C2 = ¬fievre(x) ∨¬tousse(x)) ∨grippe(x) • C3 = ¬temp(x, t) ∨¬sup(t, 38) ∨fievre(x) • C4 = tousse(Pierre) • C5 = temp(Pierre, a) • C6 = sup(a, 38) • C7 = ¬prendre(Pierre, Tamiflu) R´ esolution : • C8 = Res(C7; C1) = ¬grippe(Pierre) 3 • C9 = Res(C8; C2) = ¬fievre(Pierre) ∨¬tousse(Pierre) • C10 = Res(C9; C3) = ¬tousse(Pierre) ∨¬temp(Pierre; t) ∨¬sup(t, 38) • C11 = Res(C10; C4) = ¬temp(Pierre, t) ∨¬sup(t, 38) • C12 = Res(C11; C5 = ¬sup(a, 38) • C13 = Res(C12; C6) = clause vide Exercice 4 (D´ eduction naturelle) 3 points : pas d’` a peu pr` es ! Question 9 D´ emontrer en d´ eduction naturelle (en utilisant uniquement les r` egles rappel´ ees en annexe du sujet) le s´ equent ⊢((C ⇒A) ∨(C ⇒B)) ⇒(C ⇒(A ∨B) Posons Γ = {(C ⇒A) ∨(C ⇒B), C} et Γ1 = {(C ⇒A) ∨(C ⇒B), C, C ⇒A} et Γ2 = {(C ⇒ A) ∨(C ⇒B), C, C ⇒B}. ax Γ ⊢(C ⇒A) ∨(C ⇒B) ax Γ1 ⊢C ⇒A ax Γ1 ⊢C ⇒e Γ1 ⊢A ∨ig Γ1 ⊢A ∨B ax Γ2 ⊢C ⇒B ax Γ2 ⊢C ⇒e Γ2 ⊢B ∨id Γ2 ⊢A ∨B ∨e Γ ⊢A ∨B ⇒i (C ⇒A) ∨(C ⇒B) ⊢C ⇒(A ∨B) ⇒i ⊢((C ⇒A) ∨(C ⇒B)) ⇒(C ⇒(A ∨B)) Au choix : question 10 ou 11 exo sur 3,5 points Exercice 5 (Logique du premier ordre et s´ emantique) On consid` ere le langage du premier ordre compos´ e d’un symbole de fonction f d’arit´ e 2, du symbole binaire de l’´ egalit´ e = (on l’utilisera avec la notation inﬁxe habituelle) et d’un symbole de relation R d’arit´ e 2. Les variables sont not´ ees x, y, z . . . . Soit l’interpr´ etation suivante : - le domaine est Z (ensemble des entiers relatifs), - l’interpr´ etation de f, soit fI, est l’addition sur Z, - l’interpr´ etation de R, soit RI, est la relation <, - l’interpr´ etation de =, soit =I, est l’´ egalit´ e sur Z. Question 10 Quelle est la valeur de v´ erit´ e de chacune des 3 formules ci-dessous dans cette interpr´ etation ? Vous justiﬁerez votr´ e r´ eponse en quelques lignes. On rappelle que la valeur de v´ erit´ e d’une formule peut d´ ependre d’une valuation. - F1 : ∀x∃z(f(z, y) = x) - F2 : ∃x(R(x, y) ∧R(y, f(x, x)))) - F3 : ∀x(R(x, y) ⇒R(f(x, x), y)) 4 • La valeur de v´ erit´ e de la formule F1 d´ epend a priori de la valeur associ´ ee ` a la variable libre y. Soit a la valeur de y (c’est un entier). La valeur de v´ erit´ e de F1 sera 1 si pour tout entier n il existe un entier m tel que m+a=n. Pour n et a donn´ es, il suﬃt de prendre m=n-a. Donc la valeur de v´ erit´ e de F1 est 1, quelle que soit la valeur de y. • De mˆ eme, ici, y est une variable libre. Soit a sa valeur. On se pose la question de savoir si il existe un entier n tel n <a et a uploads/s3/ controle-final-correction-pdf.pdf