Série 12 pour Non-Philosophes

Description

INTRODUCTION A LA LOGIQUE I 23 décembre 2011 Prof. J. Duparc Série 12 pour Non-Philosophes Section : Nom : Prénom : Nom : Prénom : Nom : Prénom : Nom : Prénom : La série est à rendre au maximum par quatre étudiants non-philosophes, et au plus tard le mercredi soir dans la boîte aux lettres no 94 du Professeur Duparc, Internef, 3ème étage. Répondre sur la feuille de donnée.

• phrases du langage naturel
• langage égalitaire
• symbole de relation unaire
• relation d'ordre partiel
• signification des négations des formules de l'exercice
• formule ψ1
• renne du père noël
• renne
• modèle
• modèles

Sujets

• Duparc
• Formule
• Negation
• Signification
• Relation
• Symbole
• Modèle
• Langage
• Phrase

Informations

• Publié par: orno
• Nombre de lectures: 62
• Langue: Français

Extrait

INTRODUCTION A LA LOGIQUE I Prof. J. Duparc

Section : Nom : Nom : Nom : Nom :

Prnom : Prnom : Prnom : Prnom :

SÉrie 12 pour Non-Philosophes

23dcembre2011

La sÉrie est À rendre au maximum par quatre Étudiants non-philosophes, et au plus o tard le mercredi soir dans la bote aux lettres n94 du Professeur Duparc, Internef, Ème 3Étage. RÉpondre sur la feuille de donnÉe. Toute rÉponse non justifiÉe pourra tre considÉrÉe comme nulle.

Exercice 1 (10 pts) SoitLle langage galitaire contenant trois symboles de relation unaireF,PetR, un symbole de relation binaireA, un symbole de fonctionfet un symbole de constantec. On considre la L-structureMsuivante : –|M|:={Tornade, Danseuse , Furie , Fringante, Comte, Cupidon, Tonerre, Èclair, Rudolphe}, l’ensemble des rennes du Pre Nol. M –F:={Danseuse, Fringante, Cupidon, Èclair}, l’ensemble des rennes femelles. M –P:={Furie, Fringant, Tonerre}, l’ensemble des rennes les plus puissants. M –R:={Rudolphe}, l’ensemble des rennes au nez rouge. M –A:={ {Tornade, Danseuse},{Danseuse, Tornade},{Furie , Fringante}, {Fringante, Furie},{Comte, Cupidon},{Cupidon, Comte},{Tonerre, Èclair}, {Èclair, Tonerre}}la relation « tre partenaires ». M –fest la fonction qui À chaque rennes associe son partenaire s’il en a un, et Rudolphe À lui-mme. M –cest Rudolphe. Les formules suivantes sont-elles vraies ou fausses dansM? Justifiez brivement vos rponses. (1)∀x¬x=c (2)∀x∃y(A(x, y)→f(x) =y); (3)∀x(x=c→(f(x) =x∧R(x))); (4)∃x¬(P(x)∧F(x)); (5)∀x∀y((P(x)∧F(y))→A(x, y)); (6)∀x(f(x) =x→x=c); (7)∃x∀y(P(f(y))↔A(x, y)); (8)∀x f(f(x)) =x; (9)∃x(¬F(x)∧P(f(x))); (10)∀x∀y((¬x=y∧P(x)∧F(y))→f(x) =y);

Exercice 2 (10 pts) On reprend dans cet exercice le langage et le modle considrs À l’exercice 1. Les phrases du langage naturel sont elles quivalentes À la signification des ngations des formules de l’exercice 1 une fois interprte dansM? (1) Ilexiste un renne qui s’appelle Rudolphe. OUI NON (2) Ilexiste deux rennes qui sont partenaires mais dont l’image de l’un par la fonctionfn’est pas l’autre. OUI NON (3) Chaquerenne est Rudolphe ou son propre partenaire. OUI NON (4) Tousles rennes du Pre-Nol sont soit puissants soit máles. OUI NON (5) Ilexiste deux rennes du Pre Nol dont l’un est puissant et l’autre femelle, mais qui ne sont pas partenaires. OUI NON (6) Ilexiste un renne du Pre-Nol diffrent de Rudolphe qui est son propre partenaire. OUI NON (7) Pourtout renne du Pre Nol il existe un renne qui n’est pas son partenaire dont le partenaire est puissant. OUI NON (8) Ilexiste un renne du Pre Nol qui n’est pas le partenaire de son partenaire. OUI NON (9) Chaquerenne du Pre-Nol est une femelle ou n’a pas de partenaire puissant. OUI NON (10) Ilexiste deux rennes du Pre-Nol diffrents dont l’un n’est pas puissant, l’autre femelle et qui ne sont pas partenaires. OUI NON

Exercice 3 (10 pts) SoitLun langage galitaire contenant un symbole de relation unaireP, un symbole de fonctionf etcun symbole de constante. SoientT 1 etT 2 les thories suivantes : T 1 ={ ∃x P(x),∀x(¬f(x) =c→ ¬P(x)),∃x∃y(P(x)∧ ¬P(y))}; T 2 ={ ∃x P(x),∀x(P(x)→f(x) =c)}. (1) LathorieT 1 est-elle consistante? Justifiez votre rponse. (2) LathorieT 2 est-elle consistante? Justifiez votre rponse. (3) Laformule∀x(P(x)→f(x) =c)est-elle quivalente À la formule∀x(¬f(x) =c→ ¬P(x))? Justifiez votre rponse. (4) Existe-t-ilun modle deT 1 qui ne soit pas un modle deT 2 ? Justifiez votre rponse. (5) Existe-t-ilun modle de la thorieT 1 ?avec un seul lment OUI NON (6) Quelleest la plus petite taille d’un modle deT 1 ? Justifiez votre rponse. (7) Existe-t-ilun modle de la thorieT 2 ?avec un seul lment OUI NON (8) Quelleest la plus petite taille d’un modle deT 2 ? Justifiez votre rponse. (9) Existe-t-ilun modle infini deT 1 ? Justifiez votre rponse. (10) Existe-t-ilun modle infini deT 2 ? Justifiez votre rponse.

Exercice 4 (14 pts = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 4 pts) 1 SoitL={6}un langage galitaire oÙ6est un symbole de relation binaire. On considre les formulesψ 1 etψ 2 suivantee :

ψ 1 =∀x x6xetψ 2 =∀x∀y∀z((x6y∧y6z)→x6z) Si la formuleψ 1 est vraie dans uneL-structure, cela signifie que6est interprt par une relation rflexive dans ce modle. Si la formuleψ 2 est vraie dans uneL-structure, cela signifie que6est interprt par une relation transitive dans ce modle. On considre la thorieTsuivante : T={ψ 1 , ψ 2 } Si la thorieTest vraie dans uneL-structure, cela signifie que6est interprt par une relation 2 d’ordre partiel dans ce modle. (1) LathorieTest-elle contradictoire? Justifiez votre rponse. (2) LathorieTest-elle vraie dans toutes lesL-structures ?Justifiez votre rponse. (3) Trouvezune formuleϕ 1 telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel admettant un plus petit lment. (4) Laformuleϕ 1 est-elle une consquence de la thorieT? Justifiez votre rponse. (5) Trouvezune formuleϕ 2 telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel n’admettant pas de plus grand lment. (6) Laformuleϕ 2 est-elle une consquence de la thorieT? Justifiez votre rponse. (7) Trouvezune formuleϕ 3 telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel dont tous les lments sont en 3 relation deux À deux. (8) Laformuleϕ 3 est-elle une consquence de la thorieT? Justifiez votre rponse. (9) Trouvez une formuleϕ 4 telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel telle que si deux lments 4 diffrents sont en relation, alors il en existe un troisime distinct entre les deux. (10) Laformuleϕ 4 est-elle une consquence de la thorieT? Justifiez votre rponse. (11) SoitMlaL-structure dont le domaine est les tudiants qui suivent le cours de logique M ordonn par leurs notes À l’examen, c’est À dire oÙ6est interprt par :x6ysi et seulement si «ya eu une meilleure note ou le mme rsultat quex». Les formulesϕ 1 ,ϕ 2 , ϕ 3 etϕ 4 sont-elles vraies dansM? Justifiez vos rponses.

1. Afind’allÉger les notations, on notera À l’image de l’ÉgalitÉ «x6y» pour«6(x, y)» 2. Unordre partielest une relation binairerÉflexiveettransitive. 3. Ondit alors que la relation esttotale. 4. Lesordres vÉrifiant cette propriÉtÉ sont ditsdenses.

Exercice 5 (6 pts) SoitLle langage galitaire comprenant un symbole de relation unairePet d’un symbole de relation binaireR. SoitMlaL-structure suivante : –|M|:=l’ensemble des entiers naturelsN; M –P;est la relation unaire « tre pair » M5 –Rest la relation unaire « tre plus petit ou gal À ».

Les formules suivantes sont-elles vraies dansM? Entourez les bonnes rponses. (1)∃x∀y∃z((P(x)→R(x, y))∧P(y)∧ ¬R(y, z))

OUI

(2)∃x∃z((R(z, x)→R(x, z))→ ∀y R(x, y))

OUI

(3)∀y(∃z∀t R(t, z)∧ ∀x(R(x, y)→ ¬R(x, y)))

OUI

NON

NON

NON

(4)∃x∀y((P(y)→R(y, x))∧(∀u(P(u)→R(u, y))→R(x, y)))

OUI

NON

(5)∀x∀y((P(x)∧R(x, y))→((P(y)∧ ¬R(y, x))→ ∃z(¬R(z, x)∧ ¬R(y, z))))

OUI

(6)∀z∀u∃x∀y((R(x, y)∧P(u))→(P(y)→R(z, x)))

OUI

NON

NON

M 5. C’estÀ dire pour tous entiersnetm,R(n, m)si et seulement sin6m.