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)
m = 0 (E4)
(n+1)× m = m+(n× m) (E5)


1/ Montrons que x× 0 = 0 par récurrence sur x :
2/ Montrons que n× m = m+...+m(n fois) par récurrence sur n : 3/ Montrons que " m.n× m=m× n par récurrence sur n : Remarque on a une preuve par simple récurrence sur n en utilisant 2/ :



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) = ¬(IFa, ¬ b, ¬ c))
Ce qui donne la définition par cas suivante :
FI(T,b,c) = ¬(IF(Fb, ¬ c))
  = ¬ ¬ c
  = c
     
FI(F,b,c) = ¬(IF(Tb, ¬ c))
  = ¬ ¬ b
  = b



This document was translated from LATEX by HEVEA.