Corrige UTBM Fondements theoriques de l informatique 2004 GI

Description

Médian MT42 Automne 2004 : Exercice de logiquePablo Gruer26 novembre 20041 Énoncé du problème1.1 Première partieÉtablir l’équivalence logique suivante :A^(B_C) · (A^B)_(A^C)1. par une méthode basée sur la décision2. par une méthode basée sur la déduction1.2 deuxième partieProuver que si U est un ensemble d’axiomes alors T(U) =fF 2 FCP j U † Fg(la théorie de U) est fermée pour la conséquence logique.2 Corrections2.1 Première partieOn constate (théorème 3) queA^(B_C) · (A^B)_(A^C)si et seulement si la formule(A^(B_C)) $ (A^B)_(A^C) (I)est valide. A partir de là,1. méthode basée sur la décision : N’importe quelle méthode de décision de la va-lidité appliquée à la formule (I) : table de vérité, méthode des tableaux, peut servir.1A^(B_C) A^(B_C)E(^) E(^)A [B] A [C]I(^) I(^)A^B A^CI(_) I(_)(A^B)_(A^C) (A^B)_(A^C)A^(B_C)E(^)[B]‘(A^B)_(A^C) [C]‘(A^B)_(A^C) B_CE(_)(A^B)_(A^C)Fig. 1 – Preuve de (II)2. méthode basée sur la déduction : Nous pouvons séparer la formule (I) en deuximplications :(A^(B_C)) ! ((A^B)_(A^C))((A^B)_(A^C))!(A^(B_C))ce qui, du point de vue de la déduction revient aux deux preuves suivantes :A^(B_C) ‘ (A^B)_(A^C) (II)c’est à dire prouver (A^B)_(A^C) avec l’hypothèse A^(B_C) et(A^B)_(A^C)‘A^(B_C) (III)c’est à dire prouver avec A^(B_C) l’hypothèse (A^B)_(A^C).Les preuves de ces propriétés en utilisant la déduction naturelle sont données respec-tivement par les figures 1 et 2. Pour identifier chaque règle utilisée nous ...

Informations

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

Extrait

MÉdian MT42 Automne 2004 : Exercice de logique

Pablo Gruer 26 novembre 2004

1 Enoncdu problÈme 1.1 PremiÈrepartie Etablir l’quivalence logique suivante : A∧(B∨C)≡(A∧B)∨(A∧C) 1. parune mthode base sur la dcision 2. parune mthode base sur la dduction

1.2 deuxiÈmepartie Prouver que siUest un ensemble d’axiomes alorsT(U) ={F∈F CP|U²F} (la thorie deU) est ferme pour la consquence logique.

2 Corrections 2.1 PremiÈrepartie On constate (thorÈme 3) que A∧(B∨C)≡(A∧B)∨(A∧C) si et seulement si la formule (A∧(B∨C))↔(A∧B)∨(A∧C) (I) est valide. A partir de lÀ,

1. mthodebase sur la dcision: N’importe quelle mthode de dcision de la va- lidit applique À la formule(I): table de vrit, mthode des tableaux, peut servir.

1