Série 12 pour Non-Philosophes
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
5
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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.
Voir
- 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
INTRODUCTION A LA LOGIQUE I Prof. J. Duparc
Section : Nom : Nom : Nom : Nom :
Prnom : Prnom : Prnom : Prnom :
SÉrie 12 pour Non-Philosophes
23dcembre2011
La sÉrie est À rendre au maximum par quatre Étudiants non-philosophes, et au plus o tard le mercredi soir dans la bote 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 considre la L-structureMsuivante : –|M|:={Tornade, Danseuse , Furie , Fringante, Comte, Cupidon, Tonerre, Èclair, Rudolphe}, l’ensemble des rennes du Pre Nol. 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},{Comte, Cupidon},{Cupidon, Comte},{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-mme. M –cest Rudolphe. Les formules suivantes sont-elles vraies ou fausses dansM? Justifiez brivement vos rponses. (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 modle considrs À l’exercice 1. Les phrases du langage naturel sont elles quivalentes À la signification des ngations des formules de l’exercice 1 une fois interprte 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 Pre-Nol sont soit puissants soit máles. OUI NON (5) Ilexiste deux rennes du Pre Nol dont l’un est puissant et l’autre femelle, mais qui ne sont pas partenaires. OUI NON (6) Ilexiste un renne du Pre-Nol diffrent de Rudolphe qui est son propre partenaire. OUI NON (7) Pourtout renne du Pre Nol il existe un renne qui n’est pas son partenaire dont le partenaire est puissant. OUI NON (8) Ilexiste un renne du Pre Nol qui n’est pas le partenaire de son partenaire. OUI NON (9) Chaquerenne du Pre-Nol est une femelle ou n’a pas de partenaire puissant. OUI NON (10) Ilexiste deux rennes du Pre-Nol diffrents 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. SoientT1etT2les thories suivantes : T1={ ∃x P(x),∀x(¬f(x) =c→ ¬P(x)),∃x∃y(P(x)∧ ¬P(y))}; T2={ ∃x P(x),∀x(P(x)→f(x) =c)}. (1) LathorieT1est-elle consistante? Justifiez votre rponse. (2) LathorieT2est-elle consistante? Justifiez votre rponse. (3) Laformule∀x(P(x)→f(x) =c)est-elle quivalente À la formule∀x(¬f(x) =c→ ¬P(x))? Justifiez votre rponse. (4) Existe-t-ilun modle deT1qui ne soit pas un modle deT2? Justifiez votre rponse. (5) Existe-t-ilun modle de la thorieT1?avec un seul lment OUI NON (6) Quelleest la plus petite taille d’un modle deT1? Justifiez votre rponse. (7) Existe-t-ilun modle de la thorieT2?avec un seul lment OUI NON (8) Quelleest la plus petite taille d’un modle deT2? Justifiez votre rponse. (9) Existe-t-ilun modle infini deT1? Justifiez votre rponse. (10) Existe-t-ilun modle infini deT2? Justifiez votre rponse.
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 considre les formulesψ1etψ2suivantee :
ψ1=∀x x6xetψ2=∀x∀y∀z((x6y∧y6z)→x6z) Si la formuleψ1est vraie dans uneL-structure, cela signifie que6est interprt par une relation rflexive dans ce modle. Si la formuleψ2est vraie dans uneL-structure, cela signifie que6est interprt par une relation transitive dans ce modle. On considre la thorieTsuivante : T={ψ1, ψ2} Si la thorieTest vraie dans uneL-structure, cela signifie que6est interprt par une relation 2 d’ordre partiel dans ce modle. (1) LathorieTest-elle contradictoire? Justifiez votre rponse. (2) LathorieTest-elle vraie dans toutes lesL-structures ?Justifiez votre rponse. (3) Trouvezune formuleϕ1telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel admettant un plus petit lment. (4) Laformuleϕ1est-elle une consquence de la thorieT? Justifiez votre rponse. (5) Trouvezune formuleϕ2telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel n’admettant pas de plus grand lment. (6) Laformuleϕ2est-elle une consquence de la thorieT? Justifiez votre rponse. (7) Trouvezune formuleϕ3telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel dont tous les lments sont en 3 relation deux À deux. (8) Laformuleϕ3est-elle une consquence de la thorieT? Justifiez votre rponse. (9) Trouvez une formuleϕ4telle que celle-ci est vrifie dans uneL-structure vrifiantTsi et seulement si6est interprt par une relation d’ordre partiel telle que si deux lments 4 diffrents sont en relation, alors il en existe un troisime distinct entre les deux. (10) Laformuleϕ4est-elle une consquence de la thorieT? Justifiez votre rponse. (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 interprt par :x6ysi et seulement si «ya eu une meilleure note ou le mme rsultat quex». Les formulesϕ1,ϕ2, ϕ3etϕ4sont-elles vraies dansM? Justifiez vos rponses.
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 rponses. (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.
