Série 12 pour Non-Philosophes

Série 12 pour Non-Philosophes

Documents
5 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

Informations

Publié par
Nombre de visites sur la page 61
Langue Français
Signaler un problème
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)xy(A(x, y)f(x) =y); (3)x(x=c(f(x) =xR(x))); (4)x¬(P(x)F(x)); (5)xy((P(x)F(y))A(x, y)); (6)x(f(x) =xx=c); (7)xy(P(f(y))A(x, y)); (8)x f(f(x)) =x; (9)x(¬F(x)P(f(x))); (10)xy((¬x=yP(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. SoientT1etT2les thories suivantes : T1={ ∃x P(x),x(¬f(x) =c→ ¬P(x)),xy(P(x)∧ ¬P(y))}; T2={ ∃x P(x),x(P(x)f(x) =c)}. (1) LathorieT1est-elle consistante? Justifiez votre rponse. (2) LathorieT2est-elle consistante? Justifiez votre rponse. (3) Laformulex(P(x)f(x) =c)est-elle quivalente À la formulex(¬f(x) =c→ ¬P(x))? Justifiez votre rponse. (4) Existe-t-ilun modle deT1qui ne soit pas un modle deT2? Justifiez votre rponse. (5) Existe-t-ilun modle de la thorieT1?avec un seul lment OUI NON (6) Quelleest la plus petite taille d’un modle deT1? Justifiez votre rponse. (7) Existe-t-ilun modle de la thorieT2?avec un seul lment OUI NON (8) Quelleest la plus petite taille d’un modle deT2? Justifiez votre rponse. (9) Existe-t-ilun modle infini deT1? Justifiez votre rponse. (10) Existe-t-ilun modle infini deT2? 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ψ1etψ2suivantee :
ψ1=x x6xetψ2=xyz((x6yy6z)x6z) Si la formuleψ1est vraie dans uneL-structure, cela signifie que6est interprt par une relation rflexive dans ce modle. Si la formuleψ2est 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ϕ1telle 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ϕ1est-elle une consquence de la thorieT? Justifiez votre rponse. (5) Trouvezune formuleϕ2telle 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ϕ2est-elle une consquence de la thorieT? Justifiez votre rponse. (7) Trouvezune formuleϕ3telle 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ϕ3est-elle une consquence de la thorieT? Justifiez votre rponse. (9) Trouvez une formuleϕ4telle 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ϕ4est-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, ϕ3etϕ4sont-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)xyz((P(x)R(x, y))P(y)∧ ¬R(y, z))
OUI
(2)xz((R(z, x)R(x, z))→ ∀y R(x, y))
OUI
(3)y(zt R(t, z)∧ ∀x(R(x, y)→ ¬R(x, y)))
OUI
NON
NON
NON
(4)xy((P(y)R(y, x))(u(P(u)R(u, y))R(x, y)))
OUI
NON
(5)xy((P(x)R(x, y))((P(y)∧ ¬R(y, x))→ ∃z(¬R(z, x)∧ ¬R(y, z))))
OUI
(6)zuxy((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.