1.4 Appli ca tions élé men taires
© Dunod – Toute reproduction non autorisée est un délit.
27
Cepen dant, pour des exemples par ti cu liers de petite taille, un rai son ne ment spé ci -
fique au pro blème consi déré per met de s’affran chir d’une grande part de l’énu mé
ra tion. Voici un exemple où le rai son ne ment per met d’évi ter des lon gueurs.
Soit : F 5 (a 1
# b) # (c 1
# d) # (a # b) 1
# (a 1
# b 1 c) # (c 1
# d) 1
# c # (a 1 b).
On obtient :
F 5 a # b # c # d 1
# a # b # c puis F 5 F 5 b 1
# a # c 1
# a # d 1
# c # d 1
# a # c.
On voit faci le ment que F ne contient que trois mintermes : a # b # c # d, a # b # c # d
et a # b # c # d (soit m 9 , m 3 et m 2 ); d’où F en comporte treize. Il serait donc très
fas ti dieux d’avoir recours à un tableau tel que celui de la page 26 pour cher
cher les consti tuants essen tiels et la forme mini male. Mais la simple ins -
pec tion de la liste des consti tuants pre miers per met d’évi ter ici tout cal cul :
b est évi dem ment un consti tuant essen tiel ; a # c éga le ment, puisque a # b # c # d
n’est cou vert par aucun autre consti tuant ; de même a # c, à cause de a # b # c # d.
Res tent les consti tuants pre miers a # d et c # d ; un déve lop pe ment ne fai sant
appa raître que des mintermes non cou verts par b ne peut admettre b comme
fac teur ; d’où : a # b # d et b # cd.
Mais alors, tout déve lop pe ment du pre mier (resp. second) consti tuant, non cou vert
par a # c (resp. a # c), ne peut admettre c (resp. a) comme fac teur. L’un ou l’autre, ne
pou vant plus ser vir à cou vrir que le minterme a # b # c # d, peut être choisi pour être
adjoint aux consti tuants essen tiels. Ainsi y a- t-il deux formes mini males :
F 1 5 b 1
# a # c 1
# a # c 1
# a # d 5 b 1
# a # 1 c 1
# d 2 1
# a # c,
F 2 5 b 1
# a # c 1
# a # c 1
# c # d 5 b 1
# a # c 1
# c 1 a 1
# d 2 .
1.4 Appli cA tionS élé men tAireS
L’algèbre de Boole se prête à l’ana lyse et à la syn thèse des cir cuits logiques, s’applique
en élec tri cité, en élec tro nique et en auto ma tique, à l’étude de cer taines ques tions de
logique, etc. Nous allons voir quelques unes de ses appli ca tions élé men taires en
recherche opé ra tion nelle, notam ment à des pro blèmes combi na toires.
NB. Nous vou lons sim ple ment mon trer, au tra vers des exemples sui vants, comment l’algèbre de Boole per met de résoudre cer tains pro blèmes de la recherche opé -
ra tion nelle. Les méthodes pré sen tées ne sont pas nécessairement celles uti li sées en
pra tique pour la réso lu tion de ces pro blèmes. Nous ver rons en effet, au long de cet
ouvrage, qu’il peut exister des méthodes plus effi caces que celles pré sen tées ici.
1.4.1 Étude d’un iti né raire
Une per sonne veut, par tant de la ville A et y reve nant, choi sir parmi les moyens de
tran sport ceux qui lui per met tront de se rendre dans les villes B, C et D, de manière
à ce que son absence totale soit de durée mini male.
© Dunod – Toute reproduction non autorisée est un délit.
27
Cepen dant, pour des exemples par ti cu liers de petite taille, un rai son ne ment spé ci -
fique au pro blème consi déré per met de s’affran chir d’une grande part de l’énu mé
ra tion. Voici un exemple où le rai son ne ment per met d’évi ter des lon gueurs.
Soit : F 5 (a 1
# b) # (c 1
# d) # (a # b) 1
# (a 1
# b 1 c) # (c 1
# d) 1
# c # (a 1 b).
On obtient :
F 5 a # b # c # d 1
# a # b # c puis F 5 F 5 b 1
# a # c 1
# a # d 1
# c # d 1
# a # c.
On voit faci le ment que F ne contient que trois mintermes : a # b # c # d, a # b # c # d
et a # b # c # d (soit m 9 , m 3 et m 2 ); d’où F en comporte treize. Il serait donc très
fas ti dieux d’avoir recours à un tableau tel que celui de la page 26 pour cher
cher les consti tuants essen tiels et la forme mini male. Mais la simple ins -
pec tion de la liste des consti tuants pre miers per met d’évi ter ici tout cal cul :
b est évi dem ment un consti tuant essen tiel ; a # c éga le ment, puisque a # b # c # d
n’est cou vert par aucun autre consti tuant ; de même a # c, à cause de a # b # c # d.
Res tent les consti tuants pre miers a # d et c # d ; un déve lop pe ment ne fai sant
appa raître que des mintermes non cou verts par b ne peut admettre b comme
fac teur ; d’où : a # b # d et b # cd.
Mais alors, tout déve lop pe ment du pre mier (resp. second) consti tuant, non cou vert
par a # c (resp. a # c), ne peut admettre c (resp. a) comme fac teur. L’un ou l’autre, ne
pou vant plus ser vir à cou vrir que le minterme a # b # c # d, peut être choisi pour être
adjoint aux consti tuants essen tiels. Ainsi y a- t-il deux formes mini males :
F 1 5 b 1
# a # c 1
# a # c 1
# a # d 5 b 1
# a # 1 c 1
# d 2 1
# a # c,
F 2 5 b 1
# a # c 1
# a # c 1
# c # d 5 b 1
# a # c 1
# c 1 a 1
# d 2 .
1.4 Appli cA tionS élé men tAireS
L’algèbre de Boole se prête à l’ana lyse et à la syn thèse des cir cuits logiques, s’applique
en élec tri cité, en élec tro nique et en auto ma tique, à l’étude de cer taines ques tions de
logique, etc. Nous allons voir quelques unes de ses appli ca tions élé men taires en
recherche opé ra tion nelle, notam ment à des pro blèmes combi na toires.
NB. Nous vou lons sim ple ment mon trer, au tra vers des exemples sui vants, comment l’algèbre de Boole per met de résoudre cer tains pro blèmes de la recherche opé -
ra tion nelle. Les méthodes pré sen tées ne sont pas nécessairement celles uti li sées en
pra tique pour la réso lu tion de ces pro blèmes. Nous ver rons en effet, au long de cet
ouvrage, qu’il peut exister des méthodes plus effi caces que celles pré sen tées ici.
1.4.1 Étude d’un iti né raire
Une per sonne veut, par tant de la ville A et y reve nant, choi sir parmi les moyens de
tran sport ceux qui lui per met tront de se rendre dans les villes B, C et D, de manière
à ce que son absence totale soit de durée mini male.