UTBM fondements theoriques de l informatique 2006 gi

Description

Utbm mt42 Examen médian Automne 2006Nb: Lesexercices1et2serontrédigéssurdesfeuillesséparées. Parailleurs, onpourraadmettretoutrésultatintermédiaireafindepoursuivrelarésolutiond’unexercice.Exercice 1 Equivalence logique1.1 Première partieNous rappelons que ...

Informations

• Publié par: shura
• Nombre de lectures: 199
• Langue: Français

Extrait

Utbm mt42Examen médianAutomne 2006 Nb :Les exercices 1 et 2 seront rédigés sur des feuilles séparées.Par ailleurs, on pourra admettre tout résultat intermédiaire afin de poursuivre la résolution d’un exercice.

Exercice 1

1.1Première partie

Equivalence logique

Nous rappelons que deux formulesF 1 etF 2 sont logiquement équivalentes (ce qui est notéF 1 ≡F 2 ) lorsqu’elles sont satisfaites par les mêmes valuations. Etant donnée la formulep→(q∨r), indiquer lesquelles des formules suivantes lui sont logiquement équivalentes :

•q∨(¬p∨r) •(q∧ ¬r)→p •(p∧ ¬r)→q •(¬q∧ ¬r)→ ¬p

Expliquer la méthode utilisée pour décider des équivalences logiques précédentes.

1.2Deuxième partie a)Rappels Nous rappelons qu’une formuleFest conséquence logique des formulesF 1 , F 2 . . ,, .F n ce qui est noté F 1 , F 2 , .. . ,F n |=F,

lorsque toute valuation qui satisfaitF 1 , F 2 F, .. . , n satisfait aussiF. Nous savons aussi que, quelles que soient les formulesF 1 , F 2 etF, on a : F 1 , F 2 |=Fsi et seulement si|= (F 1 ∧F 2 →F),

où|=Qsignifie que la formuleQest valide. b)Utiliser l’équivalence logique pour montrer qu’on a aussi : F 1 , F 2 |=Fsi et seulement si|= (F 1 →(F 2 →F)).

1

.../...