| UNIVERSITÉPIERRE & MARIE CURIE |
| Licence informatique |
| Outils Mathématiques pour l'Informatique |
| 2000-01
|
Interrogation écrite
Corrigé
Novembre 2000
Groupe 8
--°--
Question 1 On se donne les axiomes équationnels suivants:
| 0+m |
= |
m |
(E1) |
| (n+1)+m |
= |
n+(m+1) |
(E2) |
| n+m |
= |
m+n |
(E3) |
| 0× m |
= |
0 |
(E4) |
| (n+1)× m |
= |
m+(n× m) |
(E5)
|
1/ Montrons que x× 0 = 0 par récurrence sur x :
- si x=0, on a 0× 0 = 0 par (E4).
- si x=x'+1, notre hypothèse de récurrence est x'× 0 = 0.
Montrons que (x'+1)× 0 = 0 :
| (x'+1)× 0 |
= |
0 + (x'× 0) |
par (E5) |
| |
= |
x'× 0 |
par (E1) |
| |
= |
0 |
par hypothèse de récurrence
|
2/ Montrons que n× m = m+...+m(n fois)
par récurrence sur n :
- si n=0, on a (par convention)
m+...+m(0 fois) = 0. D'où0 × m = 0 = m+...+m(0 fois).
- si n=n'+1, notre hypothèse de récurrence est que
n'× m = m+...+m(n' fois), montrons que
(n'+1)× m = m+...+m(n'+1 fois).
| (n'+1)× m |
= |
m+(n'× m) |
par (E5) |
| |
= |
|
par hypothèse de récurrence |
| |
= |
|
3/ Montrons que " m.n× m=m× n par récurrence sur n :
- si n=0, le résultat nous est donnépar 1/.
- si n=n'+1, notre hypothèse de récurrence est
(HR1) : " m.n'× m=m× n'. Il faut montrer, pour un m
quelconque que : (n'+1)× m = m×(n'+1); c'est-à-dire (par
(E5), m+(n'× m) = m×(n'+1). Ce que nous allons montrer
par récurrence sur m :
- si m=0, on a
| 0+(n'× 0) |
= |
n'× 0 |
par (E1) |
| |
= |
0 |
par 1/ |
| |
= |
0×(n'+1) |
par (E4)
|
- si m=m'+1 on a une seconde hypothèse de récurrence :
(HR2) : m'+ (n'× m') = m'×(n'+1). Il faut montrer que
(m'+1)+ (n'× (m'+1)) = (m'+1)×(n'+1)
On a alors :
| (m'+1)×(n'+1) |
= |
(n'+1)+(m'×(n'+1)) |
par (E5) |
| |
= |
(n'+1)+(m'+(n'× m')) |
par (HR2) |
| |
= |
(m'+1)+(n'+(n'× m')) |
par ass. et com. de + |
| |
= |
(m'+1)+(n'+(m'× n')) |
par (HR1) |
| |
= |
(m'+1)+((m'+1)× n')) |
par (E5) |
| |
= |
(m'+1)+(n'×(m'+1)) |
par (HR1)
|
Notez qu'il a étéutile de conserver le <<" m>> dans
(HR1) pour utiliser cette hypothèse en instanciant une première
fois m avec m' et une seconde fois avec m'+1.
Remarque on a une preuve par simple récurrence sur n en
utilisant 2/ :
- si n=0, on utilise ici encore 1/.
- si n=n'+1, on a comme hypothése de récurrence que
n'× m = m× n' (on n'a pas besoin ici du <<" m>>).
| (n'+1)× m |
= |
m + (n'× m) |
par (E5) |
| |
= |
m + (m× n') |
par hyp. de réc. |
| |
= |
|
par 2/ |
| |
= |
|
|
| |
= |
|
|
| |
= |
m×(n'+1) |
|
Question 2 Soient T et F les deux constantes
booléennes et IF la fonction booléenne ternaire (bien
connue) définie par :
| IF(T,a,b) |
= |
a |
| IF(F,a,b) |
= |
b
|
1/
| IF(T,T,b) |
= |
T |
| IF(T,F,b) |
= |
F |
| IF(F,T,b) |
= |
b |
| IF(F,F,b) |
= |
b
|
2/
| ¬ a |
= |
IF(a,F,T) |
| aÚ b |
= |
IF(a,T,b) |
| aÙ b |
= |
IF(a,b,F) |
| aÞ b |
= |
IF(a,b,T)
|
Question 3 Appelons FI la fonction duale de IF. On
l'obtient en utilisant :
FI(a,b,c) = ¬(IF(¬ a, ¬ b, ¬ c))
Ce qui donne la définition par cas suivante :
| FI(T,b,c) |
= |
¬(IF(F,¬ b, ¬ c)) |
| |
= |
¬ ¬ c |
| |
= |
c |
| |
|
|
| FI(F,b,c) |
= |
¬(IF(T,¬ b, ¬ c)) |
| |
= |
¬ ¬ b |
| |
= |
b
|
This document was translated from LATEX by HEVEA.