Cours de logique mathématique — Exercices sur le calcul des ...

Description

Cours de logique mathématique — Exercices sur le calcul des ...

Sujets

• exercice
• cours
• mathématiques
• exercices
• mathématique
• cours de

Informations

• Publié par: eqevewit
• Nombre de lectures: 381
• Langue: Français

Extrait

Universit ´ eParis8atememh´iqatsueD—e´aptrmenedt

Premier semestre 02-03

Coursdelogiquemath´ematique—Exercicessurlecalculdespre´dicats

exercices`arendrele18novembre2002:2,4,5,7,12,14,18,20.

Langage — Structure

Exercice 1:geonssmatinforLesissinfie´dsetnaviugaannlsuleelt-ena)L={R, f, g}avecR symbole de relation etfetgsymboles de fonction ;b)L={R, f}avecRetfbinaires ?

Exercice 2Pour chacun des langages suivants, donner deux exemples de structures dans ce langage.a)L 0 ={R, f}avecRsymbole de relation binaire etfsymbole de fonction unaire. b)L 1 ={f, g, h, c}avecf,gsymboles de fonction binaires,hsymbole de fonction unaire etcsymbole de constante. c)L 2 ={P n :n∈IN}`oluseP n sont des symboles de relation, tous unaires.

Sous-structures

Exercice 3SoitL={R}avecRsymbole de relation binaire et soitMuneL-structure. A a)SoitAun sous-ensemble non vide deMe´rpretnnoitatr.oOttoauindvreiuneruvRdeRsur A A Atelle que (A, R) soit une sous-structure deMpossible ? A-t-on le choix pour. Est-ce R? M b)On suppose queRuresnclevauieq’´dnoitalerenutseM(i.e.ttraqueeetrisym´vi,eflexe´r-isn N tive).D´emontrerquesiNest une sous-structure deMalorsR´eesqtuuinvearlelationd’neec surN.

Exercice 4SoitL={f}avecfsymbole de fonction unaire et soitMuneL-structure. A a)SoitAun sous-ensemble non vide deMovduartirtuoevurneinterpr´etationnO.fdefsurA A ` telle que (A, f) soit une sous-structure deMA-t-on alors. A quelle condition est-ce possible ? A le choix pourf? M N b)On suppose quefsejnitqzeuis´emontreective.DNest une sous-structure deMalorsf est injective. c)SoientM= (Z, n7→n+ 1) etN= (IN, n7→n+ueV.)1ire´qzefiMetNsont desL-structures et queNest une sous-structure deMque dans la question. Pensez-vous bci-dessus on pourrait remplacer “injective” par “surjective” ?

Termes — Valeurs

? Exercice 5SoitL={R, f, g, h, c}avecRsymbole de relation binaire, et les symboles de fonctions :funaire,gbinaire,hternaire etcPour chacune des expressionssymbole de constante. suivantes : si vous pensez qu’il s’agit d’un terme deLre,´eprntse-lezsuovis;ebrard’meorsfoues pensezlecontraire,justifiezvotrere´ponse. a)∀(x, y)b)α(x, y)c)f(x, y)d)g(x, y)e)R(x, y)f)h(x, y)g)(f x) h)f(g(c, y))i)h(x, c, x)j)h(xc, x)k)f(h(x, y, c))l)h(f(x, y, c)) m)g(f(h(x, y, c)), h(f(x), f(y), f(c)))n)f(f(g(x, f(y))))o)g(x, f(h(c, z, g(y, f(v))))) p)g(g(f(h(x, y, c)), h(f(x), f(y), f(c))), g(x, f(h(c, z, g(y, f(v))))))

Exercice 6Un algorithme pour reconnaˆıtre les termes : -dansl’expressione´tudie´e,chaquefoisqu’onrencontreunesous-expressiondelaformec,f(x), g(x, y) ouh(x, y, zex.), on la remplace par une variable (p. x) -onrecommencecetteop´erationjusqu’a`cequ’onnepuisseplus.