TRAVAIL NUMERO 1IFT-1000 : Logique et techniques de preuve

Automne 2011, section en classe

Consignes1. Echeance : Le travail doit etre remis au plus tard le mardi 4 octobre 2011 a` 22 h.

2. Le travail doit etre fait individuellement. Aucune collaboration nest permise.

3. Indiquez votre nom sur la premie`re page.

4. Laissez de lespace en haut de la premie`re page pour que nous puissions ecrire les pointsobtenus. Presentez la solution des proble`mes en laissant de lespace pour que nous puissionsfaire des commentaires sur vos erreurs (autrement dit, necrivez pas trop serre).

5. Remise du travail

(a) La solution des proble`mes (a` lexception du proble`me 1) peut etre redigee a` la main ouavec un traitement de texte. Si vous la redigez a` la main, vous pouvez la remettre sousPixel en la numerisant. Si vous la redigez avec un traitement de texte et que celui-ci nepermet pas decrire certains symboles utilises dans le cours, utilisez dautres symbolesapre`s avoir explique vos conventions.

(b) Votre travail doit etre remis au moyen de votre guichet etudiant sous Pixel. Vous pourrezfaire des essais de remise avec Pixel de`s le 20 septembre, pour vous assurer que toutfonctionne bien ; vous eviterez ainsi de devoir menvoyer votre travail par courriel a` ladernie`re minute. Pour faire lessai, remettez un fichier quelconque pour le TP intitulePour retour dexamens. Ceci agira comme un genre dinscription dans le syste`me et mepermettra de vous retourner vos examens numerises le moment venu.

(c) Remise sous Pixel Une seconde apre`s lecheance indiquee ci-dessus, Pixel nacceptera plusde travaux.

Le fichier pour la reponse au proble`me 1 est en format wld. Le fichier contenant lareponse aux autres questions doit etre en format pdf. Si vous avez plusieursfichiers pdf (obtenus par exemple a` la suite dune numerisation de plusieurs pages),fusionnez-les en un seul fichier pdf. Compressez le ou les fichiers pdf et wld dans unfichier zip. Si vous ne remettez quun fichier, il nest pas necessaire de le compresser.

Faites attention de ne pas ecraser votre travail avec le travail dun autrecours. Verifiez que vous avez remis le bon travail. Verifiez que le fichierremis nest pas vide. Ne remettez pas un fichier pdf crypte ou encode.Faites attention a` ce que vous faites (je ne suis pas capable de prevoirtoutes les gaes possibles et de les enoncer ici).

(d) Si vous etes en retard, envoyez votre travail a` Jules.Desharnais@ift.ulaval.ca. Ladate et lheure indiquee par le logiciel de courriel seront utilisees pour determiner lapenalite.

Penalites (points perdus)100 : Travail remis avec plus de 24 heures de retard.

20 : Travail remis avec moins de 24 heures de retard.

20 : Solution remise dans un fichier qui nest pas un fichier pdf (sauf pour la question 1).

20 : Travail remis a` temps en classe, a` mon bureau ou par courriel. Utilisez Pixel.

10 : Francais (0 a` 10, selon le nombre de fautes ; voyez le plan de cours).

2 : Fichiers pdf non fusionnes en un fichier unique.

1 : Omission du nom sur la premie`re page du travail.

1 : Espace insusant pour ecrire les notes sur la premie`re page.

1 : Utilisation comprehensible de symboles autres que ceux du cours sans donner la convention.Penalise pour chaque question ou` la faute est faite. Si cest incomprehensible, cest pluscouteux.

1 (25 points)

Pour faire cet exercice, vous devez utiliser le logiciel Tarskis World. Telechargez le fichierTP1A11.SEN du site web du cours et placez-le dans C:\Tarski\EXERCISE. Construisez un mondedans lequel toutes les expressions du fichier TP1A11.SEN sont vraies. Enregistrez votre monde dansun fichier WLD et remettez-le comme resultat de lexercice.

Voici les formules du fichier TP1A11.SEN.

1. Cube(a) Tet(b) Dodec(c) Cube(d)2. Cube(d) Tet(f)3. Dodec(c) Tet(f)4. Dodec(c) Cube(f)5. Tet(b) Cube(a)6. Cube(a) (LeftOf(a, b) Cube(a))7. (Cube(c) Dodec(e)) (Cube(c) Medium(c))8. Cube(d) (Cube(b) BackOf(c, d))9. LeftOf(a, b) RightOf(c, d)10. (Tet(a) Larger(a, b)) (LeftOf(a, b) RightOf(a, b))11. LeftOf(a, b) (LeftOf(a, b) RightOf(b, a))12. LeftOf(d, e) (LeftOf(d, e) (LeftOf(d, e) FrontOf(a, b)))13. Larger(b, a) (Larger(b, a) Large(d))14. Cube(c) (Large(c) (Cube(c) Large(c)))15. (Tet(a) Large(a)) (Tet(a) Large(a))16. Large(d) Small(a)17. FrontOf(a, d) ((BackOf(a, b) BackOf(b, a)) FrontOf(c, d))18. Tet(a) Cube(b)19. Large(e) Between(e, d, f)20. (Small(c) (Cube(a) Cube(d))) ((Small(c) Cube(a)) (Small(c) Cube(d)))21. (Cube(b) (Cube(c) Large(c)))22. FrontOf(d, e) (BackOf(d, e) Smaller(a, a))

23. (Larger(a, b) Smaller(a, b)) Cube(c)24. (Small(a) Cube(b) Larger(a, b)) (FrontOf(a, d) Large(f))25. LeftOf(b, c) LeftOf(c, b)26. (LeftOf(b, c) LeftOf(c, b))27. (Small(e)Medium(e)Large(e))((Between(e, d, f)Cube(e))(Between(e, d, f)Tet(e)))28. (Tet(c) Large(c))29. Tet(c) Large(c)30. Between(c, a, f) (Between(c, a, f) Between(c, e, b))Comme il y a un assez grand nombre de formules, voici quelques indices. Certaines de ces

formules sont des tautologies. On peut le voir soit en faisant une table de verite (cest plutot long)ou en utilisant les lois du chapitre 3 ; elles napportent donc aucune information sur le placement dessolides. Dautres lois ne sont pas a` proprement parler des tautologies, mais elles sont valides danstous les mondes de Tarski. Cest le cas, par exemple, de la formule Cube(a)Tet(a)Dodec(a) ; cetteformule napporte aucune information. Il y a aussi des formules equivalentes parmi les formulesdonnees, ainsi que des formules qui apportent moins dinformation que dautres.

Pensez donc a` simplifier ou a` transformer les formules plus complexes en utilisant les lois duchapitre 3. Une des lois qui est utile pour certaines formules est la definition alternative de (3.81).

2 (15 points)

1. Construisez la table de verite de lexpression q p = r qp q r. Suivez le format desnotes de cours pour la presentation de votre table et tenez compte des exercices 2.4 et 2.5des notes de cours (vous perdrez des points si vous ne respectez pas mes preferences).

2. Lexpression est-elle satisfiable ?

3. Lexpression est-elle valide ?

3 (6 points)

Eectuez les substitutions suivantes. Eliminez les parenthe`ses superflues. Donnez la reponsefinale seulement. Utilisez la table de preseance de lannexe A des notes de cours.

1. q (r = (p r))[p, q, r := x p, s t, u w]2. r (p r)[r := x p][s := u w][p := s t]

4 (15 points)

Dites quelle re`gle de substitution et quelle re`gle de Leibniz sont utilisees dans la transforma-tion suivante. Apre`s avoir donne les re`gles, redonnez-les en y eectuant les substitutions quellescontiennent et supprimez les parenthe`ses superflues. Regardez dans le chapitre 11 la solution duproble`me 1 du chapitre 3 pour savoir comment presenter votre reponse.

((r s r s) p) s r s r s= h Definition alternative de (3.82), avec p, q := r, s, deux fois (cest-a`-dire que

la loi est appliquee de la meme manie`re a` deux endroits de la formule) i(r p) s r

5 (4 points)

Completez la transformation suivante en donnant la formule qui suit la justification. Supprimezles parenthe`ses superflues. Une loi de commutativite est utilisee sans mention.

p q (r s) q (r s) s= h Re`gle dor (3.60), avec p, q := q, r s i

6 (35 points)

Demontrez le theore`me r s (((sr)(sr) q q)s)r s. Vous pouvez utilisertoutes les lois et methodes de preuve du chapitre 3. Indiquez toutes les lois utilisees, incluant leslois de commutativite, en donnant leur nom lorsquelles en ont un et leur numero. Donnezaussi toutes les substitutions. Il y a une exception : vous navez pas a` mentionner les usages delassociativite. Appliquez une seule loi (appliquee une seule fois) a` chaque transformation lorsquecest possible.