13.7 Exercices
457
est une fonction primitive r´ ecursive.
Syst` emes d’insertion–d´ el´ etion
15.
´
Elaborer un algorithme pour additionner deux nombres par le mod` ele d’insertion–d´ el´ etion. Prendre l’alphabet X = {0, 1}.
Satisfaisabilit´ e
16. Donner le graphe associ´ e ` a l’´ enonc´ e logique de l’exemple 13.45 (comme dans la
figure 13.10).
17. a) On consid` ere l’´ enonc´ e logique
γ = (x 1 ∧ x 2 ) ∨ (¬x 3 ∧ x 4 )
o` u x 1 , x 2 , x 3 et x 4 sont des variables bool´ eennes. Mettre γ sous forme conjonctive
normale.
b) Mˆ eme question pour l’´ enonc´ e
δ = (¬(x 1 ∨ x 2 )) ∨ (¬(x 3 ∨ ¬x 4 )).
c) Donner le graphe associ´ e ` a l’´ enonc´ e logique γ.
457
est une fonction primitive r´ ecursive.
Syst` emes d’insertion–d´ el´ etion
15.
´
Elaborer un algorithme pour additionner deux nombres par le mod` ele d’insertion–d´ el´ etion. Prendre l’alphabet X = {0, 1}.
Satisfaisabilit´ e
16. Donner le graphe associ´ e ` a l’´ enonc´ e logique de l’exemple 13.45 (comme dans la
figure 13.10).
17. a) On consid` ere l’´ enonc´ e logique
γ = (x 1 ∧ x 2 ) ∨ (¬x 3 ∧ x 4 )
o` u x 1 , x 2 , x 3 et x 4 sont des variables bool´ eennes. Mettre γ sous forme conjonctive
normale.
b) Mˆ eme question pour l’´ enonc´ e
δ = (¬(x 1 ∨ x 2 )) ∨ (¬(x 3 ∨ ¬x 4 )).
c) Donner le graphe associ´ e ` a l’´ enonc´ e logique γ.