Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Corrige UTBM Fondements theoriques de l informatique 2005 GI

6 pages
Médian MT42 Automne 2005 : Exercice de logiquePablo Gruer15 novembre 20051 Énoncé du problème1.1 Première partieÉtant données les formules ` ;` ;¢¢¢ ;` ;ˆ du calcul des propositions, prouver1 2 nque ` ;` ;¢¢¢ ;` † ˆ si et seulement si † ` ! (` ! ¢¢¢ ! (` ! ˆ)). Nous1 2 n 1 2 nrappelons que le symbole† représente la conséquence logique et que†’ signifie quela formule ’ est valide.Quelques suggestions :La preuve de : si † ` ! (` ! ¢¢¢ ! (` ! ˆ)) alors ` ;` ;¢¢¢ ;` † ˆ1 2 n 1 2 nse fait facilement en supposant qu’une certaine valuation rend vraies toutes les for-mules ` ;` ;¢¢¢ ;` et en voyant ce qu’on peut dire de ˆ compte tenu du fait qu’on1 2 nsuppose†` !(` !¢¢¢! (` !ˆ)).1 2 nLa preuve de : si ` ;` ;¢¢¢ ;` † ˆ alors † ` ! (` ! ¢¢¢ ! (` ! ˆ))1 2 n 1 2 nse fait facilement par contradiction : on commence par supposer qu’une certaine va-luation rend fausse la formule ` !(` !¢¢¢! (` !ˆ)) et on explique pourquoi1 2 ncela contredit la supposition que ` ;` ;¢¢¢ ;` † ˆ.1 2 n1.2 deuxième partieLa consistence et la complétude du calcul des séquants permet de dire :` ;` ;¢¢¢ ;` †’ si et seulement si ` ;` ;¢¢¢ ;` ‘’.1 2 n 1 2 nEn particulier, † ’ si et seulement si ‘ ’. Se servir de ce fait et de la propriétéétablie en première partie pour justifier une preuve de :‘(p!q)!((r!t)!((p^r)!(q^t)))par la déduction naturelle. Fournir cette preuve.1p^r p^rp!q p r!t rq tq^tFig. 1 – La preuve par déduction naturelle.2 Corrections2.1 Première partiePreuve de : si ...
Voir plus Voir moins
MÉdian MT42 Automne 2005 : Exercice de logique
Pablo Gruer 15 novembre 2005
1 Enoncdu problÈme 1.1 PremiÈrepartie Ètant donnes les formulesφ1, φ2,∙ ∙ ∙, φn, ψdu calcul des propositions, prouver queφ1, φ2,∙ ∙ ∙, φn²ψsi et seulement si²φ1(φ2∙ ∙→ ∙(φnψ)). Nous rappelons que le symbole²reprsente la consquence logique et que²ϕsignifie que la formuleϕest valide. Quelques suggestions : La preuve de :si²φ1(φ2∙ ∙→ ∙(φnψ))alorsφ1, φ2,∙ ∙ ∙, φn²ψ se fait facilement en supposant qu’une certaine valuation rend vraies toutes les for-mulesφ1, φ2,∙ ∙ ∙, φnet en voyant ce qu’on peut dire deψcompte tenu du fait qu’on suppose²φ1(φ2∙ ∙→ ∙(φnψ)).
La preuve de :siφ1, φ2,∙ ∙ ∙, φn²ψalors²φ1(φ2∙ ∙→ ∙(φnψ)) se fait facilement par contradiction : on commence par supposer qu’une certaine va-luation rend fausse la formuleφ1(φ2→ ∙∙ ∙(φnψ))et on explique pourquoi cela contredit la supposition queφ1, φ2,∙ ∙ ∙, φn²ψ.
1.2 deuxiÈmepartie La consistence et la compltude du calcul des squants permet de dire :
φ1, φ2,∙ ∙ ∙, φn²ϕsi et seulement siφ1, φ2,∙ ∙ ∙, φn`ϕ.
En particulier,²ϕsi et seulement si`ϕ. Se servir de ce fait et de la proprit tablie en premire partie pour justifier une preuve de :
`(pq)((rt)((pr)(qt)))
par la dduction naturelle. Fournir cette preuve.
1
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin