432
13 L’ordinateur ` a ADN
On peut aussi d´ efinir `
a l’aide de fonctions primitives r´ ecursives les op´ erateurs
bool´ eens qui sont n´ ecessaires pour construire des propositions. Ces trois op´ erateurs
sont le NON (¬), le ET (∧), et le OU (∨) (voir aussi la section 15.7 du chapitre 15).
Cependant, il est n´ ecessaire de construire tout d’abord les fonctions sgn et cosgn qui
correspondent au « signe » d’un nombre naturel. Ces fonctions sont primitives r´ ecursives
(voir l’exercice 11) :
sgn(0) = 0,
sgn(y + 1) = 1;
cosgn(0) = 1,
cosgn(y + 1) = 0.
D´ efinition 13.26 Un pr´ edicat ` a n variables, ou proposition ouverte, est une proposition
qui devient vraie ou fausse selon la valeur attribu´ ee aux variables x 1 , . . . , x n qu’elle
contient. Nous noterons un pr´ edicat P (x 1 , . . . , x n ).
Exemple 13.27 Soient P 1 (x, y), P 2 (x, y) et P 3 (x, y) les trois ´ enonc´ es « x < y », « x >
y » et « x = y » respectivement. P 1 , P 2 et P 3 sont des pr´ edicats binaires.
Lorsqu’il est ´ evalu´ e, un pr´ edicat peut prendre les valeurs de v´ erit´ e VRAI ou FAUX,
comme mentionn´ e pr´ ec´ edemment. Cependant, comme nous voulons travailler sur des
valeurs num´ eriques, nous associerons le nombre 1 ` a la valeur de v´ erit´ e VRAI et le
nombre 0 ` a la valeur de v´ erit´ e FAUX.
D´ efinition 13.28 ´
Etant donn´ e un pr´ edicat P de n variables, sa fonction valeur,
not´ ee |P |, est la fonction qui, `
a des nombres x 1 , . . . , x n associe la valeur de v´ erit´ e de
P (x 1 , . . . , x n ). La fonction |P | prend ses valeurs dans {0, 1}.
Nous pouvons d´ efinir de fa¸ con primitive r´ ecursive les fonctions valeur des trois
pr´ edicats binaires introduits dans l’exemple pr´ ec´ edent.
|x < y| = pp(x, y) = sgn(sous(y, x)),
|x > y| = pg(x, y) = sgn(sous(x, y)),
|x = y| = eg(x, y) = cosgn(pp(x, y) + pg(x, y)),
(13.1)
o` u, par abus de notation, nous ´ ecrivons pp(x, y) + pg(x, y) plutˆ ot que add(pp(x, y),
pg(x, y)).
D´ efinissons maintenant les op´ erateurs bool´ eens. Soient P 1 et P 2 deux pr´ edicats tels
que |P 1 | = p 1 et |P 2 | = p 2 . Les ´ equations suivantes d´ efinissent les trois op´ erateurs
bool´ eens ` a partir des fonctions sgn et cosgn et de fonctions primitives r´ ecursives connues :
|¬P 1 | = cosgn(p 1 ),
|P 1 ∨ P 2 | = sgn(p 1 + p 2 ),
|P 1 ∧ P 2 | = p 1 ∗ p 2 ,
o` u, par abus de notation, nous ´ ecrivons p 1 ∗ p 2 plutˆ ot que mult(p 1 , p 2 ). Le lecteur pourra
v´ erifier dans l’exercice 6 que ces trois fonctions correspondent bien aux fonctions valeurs
des op´ erateurs bool´ eens.
13 L’ordinateur ` a ADN
On peut aussi d´ efinir `
a l’aide de fonctions primitives r´ ecursives les op´ erateurs
bool´ eens qui sont n´ ecessaires pour construire des propositions. Ces trois op´ erateurs
sont le NON (¬), le ET (∧), et le OU (∨) (voir aussi la section 15.7 du chapitre 15).
Cependant, il est n´ ecessaire de construire tout d’abord les fonctions sgn et cosgn qui
correspondent au « signe » d’un nombre naturel. Ces fonctions sont primitives r´ ecursives
(voir l’exercice 11) :
sgn(0) = 0,
sgn(y + 1) = 1;
cosgn(0) = 1,
cosgn(y + 1) = 0.
D´ efinition 13.26 Un pr´ edicat ` a n variables, ou proposition ouverte, est une proposition
qui devient vraie ou fausse selon la valeur attribu´ ee aux variables x 1 , . . . , x n qu’elle
contient. Nous noterons un pr´ edicat P (x 1 , . . . , x n ).
Exemple 13.27 Soient P 1 (x, y), P 2 (x, y) et P 3 (x, y) les trois ´ enonc´ es « x < y », « x >
y » et « x = y » respectivement. P 1 , P 2 et P 3 sont des pr´ edicats binaires.
Lorsqu’il est ´ evalu´ e, un pr´ edicat peut prendre les valeurs de v´ erit´ e VRAI ou FAUX,
comme mentionn´ e pr´ ec´ edemment. Cependant, comme nous voulons travailler sur des
valeurs num´ eriques, nous associerons le nombre 1 ` a la valeur de v´ erit´ e VRAI et le
nombre 0 ` a la valeur de v´ erit´ e FAUX.
D´ efinition 13.28 ´
Etant donn´ e un pr´ edicat P de n variables, sa fonction valeur,
not´ ee |P |, est la fonction qui, `
a des nombres x 1 , . . . , x n associe la valeur de v´ erit´ e de
P (x 1 , . . . , x n ). La fonction |P | prend ses valeurs dans {0, 1}.
Nous pouvons d´ efinir de fa¸ con primitive r´ ecursive les fonctions valeur des trois
pr´ edicats binaires introduits dans l’exemple pr´ ec´ edent.
|x < y| = pp(x, y) = sgn(sous(y, x)),
|x > y| = pg(x, y) = sgn(sous(x, y)),
|x = y| = eg(x, y) = cosgn(pp(x, y) + pg(x, y)),
(13.1)
o` u, par abus de notation, nous ´ ecrivons pp(x, y) + pg(x, y) plutˆ ot que add(pp(x, y),
pg(x, y)).
D´ efinissons maintenant les op´ erateurs bool´ eens. Soient P 1 et P 2 deux pr´ edicats tels
que |P 1 | = p 1 et |P 2 | = p 2 . Les ´ equations suivantes d´ efinissent les trois op´ erateurs
bool´ eens ` a partir des fonctions sgn et cosgn et de fonctions primitives r´ ecursives connues :
|¬P 1 | = cosgn(p 1 ),
|P 1 ∨ P 2 | = sgn(p 1 + p 2 ),
|P 1 ∧ P 2 | = p 1 ∗ p 2 ,
o` u, par abus de notation, nous ´ ecrivons p 1 ∗ p 2 plutˆ ot que mult(p 1 , p 2 ). Le lecteur pourra
v´ erifier dans l’exercice 6 que ces trois fonctions correspondent bien aux fonctions valeurs
des op´ erateurs bool´ eens.