Corrige UTBM Fondements theoriques de l informatique 2005 GI

Description

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 ...

Informations

• Publié par: shin
• Nombre de lectures: 86
• Langue: Français

Extrait

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 ,∙ ∙ ∙, φ n et 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 :

`(p→q)→((r→t)→((p∧r)→(q∧t)))

par la dduction naturelle. Fournir cette preuve.

1