Master Pro Ingenierie Mathematique Cryptographie

Publié par

Niveau: Supérieur, Master
Master Pro – Ingenierie Mathematique – Cryptographie Introduction aux fonctions booleennes CHAPITRE 2. INTRODUCTION AUX FONCTIONS BOOLEENNES

  • loi de demorgan

  • theoreme de representation normale logique

  • regles de calcul logique

  • valeurs opposees

  • ordre des operateurs

  • ¬a ?

  • ¬b ¬


Publié le : vendredi 8 juin 2012
Lecture(s) : 39
Source : math.univ-lyon1.fr
Nombre de pages : 17
Voir plus Voir moins
MasterProIng´einreeiaMhte´amitequypCrgrtohiaptnIeudoroitcxuantionfoncl´eesboonnse
INTRODUCTION AUX ´ FONCTIONS BOOLEENNES
CHAPITRE 2.
http://math.univ-lyon1.fr/~roblot/masterpro.html
tsreaMrieMenieIng´ProyrCeuqitame´htaodtrIniephraogptobsne´loennenoFstiucauononxfioctsctionsbool´eenne
The´or`eme . Il y a 2 (2 n ) fonctionsbool´eennessur { 0 , 1 } n .
f : { 0 , 1 } n → { 0 , 1 }
De´nition . Une fonctionboole´enne est une fonction
0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0
C’est la tabledeve´rite´ de la fonction f .
Exemple . Pour n = 5 , il y a 4 294 967 296 fonctions. Pour n = 7 , il y a 10 38 fonctions. (Soit 10 22 anne´esa` 1 milliard de fonctions/seconde.)
Exemple . La fonction suivante de { 0 , 1 } 3 → { 0 , 1 }
Fonctionsbool´eennesetoperateurslogiques ´ On rappelle les op´erateurslogiques : non, et, ou, ou exclusif
f ( a, b, c ) = ( ¬ a c ) ( ¬ ( b c ( a ∧ ¬ b )))
negation ou et ´ a ¬ a a b 0 1 a b 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 Ilspermettentdeconstruiredesfonctionsbool´eennes. Exercice .Onconsid`erelafonctionsur { 0 , 1 } 3
ou exclusif a b 0 1 0 0 1 1 1 0
Construire sa table de ´ it´. ver e Attention`alordredesope´rateurs . ¬ alaplusfortepriorite´,maisil n’y a pas d’ordre entre et .Lexpressionsuivanteestambig¨ue ¬ a b a
Exercice .Donnerlesdeux´ecrituresnonambigu¨esdecetteexpressionet d´ntrerquellesnesontpas´egales. emo
aMtsrerPonIboolionsonctauxfitnodocunIrthpeiraogptryCueiqatme´htaMeireine´goliguqseretauesrsenep´toolboen´etcnosnoinee´Fsen
Pourledeuxi`emepoint,onutiliselaloideDeMorgan ( a 1 a 2 ∨ ∙ ∙ ∙ ∨ a n ) = ¬ ( ¬ a 1 ∧ ¬ a 2 ∧ ∙ ∙ ∙ ∧ ¬ a n )
Exercice .Construireunerepre´sentationnormalelogiquepourlafonction boole´ennesuivante 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1
The´ore`mederepr´esentationnormalelogique Toutefonctionbool´eennepeutsexprimeruniquementa`laidedes op´erateurslogiques ¬ , et ,etmˆemeuniquement ¬ et (ou ¬ et ).
Preuve .Pourchaquelignedelatabledev´erite´quidonnelavaleur 1 , on construita`laidede ¬ et une expression qui vaut 1 uniquement pour les entr´eescorrespondantes.Puis,onassemblecesexpressionsavecdes .
Fonctionsboole´enneto´ateurslogiques s e per
itnobsoonnseoFcnsbool´eefonctionoitcxuantnIeudorgrtohiapequypCramithte´eiaMinreng´eroIterPMasogslurtesueiqsennee´lare´pote
R`eglesdecalcullogique
a ( b c ) = ( a b ) ( a c )
a b = b a
a a = a
( a b ) c = a ( b c )
a ( b c ) = ( a b ) ( a c )
a b = b a
a ( a b ) = a
¬ ( a b ) = ¬ a ∧ ¬ b
a 1 = 1 a 0 = a
a ∨ ¬ a = 1
Exercice .D´emontrercesformules.
¬ ( a b ) = ¬ a ∨ ¬ b
( a b ) c = a ( b c )
¬¬ a = a
a a = a
Valeursoppose´es
a ∧ ¬ a = 0
a 0 = 0 a 1 = a
a ( a b ) = a
Double negation ´
Loi de DeMorgan
Absorption
Valeurs constantes
Associativite´
Commutativit´ e
Distributivite´
Idempotent
ontixfautrInucodargoeihpCeutpyrh´ematiqierieMatonI´gneaMtsrerPnese´eenerattop´oliguesruqsensioctonen´eolbotcnoFsenloobsnoi
Exercice .Utiliserlesre`glesdecalculetlarepr´tationtrouve´e esen pr´ece´demmentpourde´montrerquelafonctionboole´ennesuivante
0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1
est en fait la fonction ( ¬ a b ) ( a c ) .
Indication . Partager l’expression en deux parties. Utiliser la distributivit´e,puislabsorption.
nteIduroioctuxnaeuqpyrCrgotihpanierieMath´ematiMsaetProrIgne´´eraetopnnesl´eesqieulsgoetrueel´oosbontincfooobsnoitcnoFsenn
2[X1,...,Xn]ptlonyoˆemdsnaFsnsioolboen´eseneloobnee´FsentcnotsaMrPreucodtrIniephraogsnoitcnofxuanoiteMatierig´enoInyrtpeuCtaqi´hme
X 1 a 1 X 2 a 2 ∙ ∙ ∙ X an n avec a 1 , . . . , a n 0
De´nition .Unpolynoˆmede F 2 [ X 1 , . . . , X n ] est une somme finie de termesmonˆomiauxdelaforme(ou` F 2 estlecorps`adeuxe´le´ments)
Fonctionsboole´ennesetpolynˆomesdans F 2 [ X 1 , . . . , X n ]
Exercice .D´eterminerledegre´dupolynˆome X 13 + X 12 X 2 + X 15 X 37 .
Degre´ .Onde´nitledegr´edutermemonˆomial X 1 a 1 X 2 a 2 ∙ ∙ ∙ X an n par a 1 + ∙ ∙ ∙ + a n .Etledegr´edunpolynˆomecommelemaximumdesdegr´es desestermesmonoˆmiaux.
3 Exemple . X 1 + X 12 X 2 + X 15 X 37 estun´ele´mentde F 2 [ X 1 , X 2 , X 3 ]
rCeuqitame´htaMronteIhiapgrtoypsaetMerie´eniIngrPro[X1,nsF2Xn]...,tincsbonl´oonneeteseylopmoˆnadseductionauxfonctinobsoo´leennseoF
d´enitlameˆmefonctionboole´ennequelepolynoˆme
X 13 + X 12 X 2 + X 15 X 37
X 1 + X 1 X 2 + X 1 X 3
Remarque . Puisque 1 n = 1 et 0 n = 0 , pour tout n 1 , on peut remplacer X in par X i sans changer les valeurs.
Construction .Unepolynˆomedans F 2 [ X 1 , . . . , X n ] permet de construire unefonctionbool´eennede { 0 , 1 } n enconsid´erant 0 et 1 comme les e´le´mentsde F 2 .
Exemple . Le l ˆ e po ynom
Exercice .Construirelatabledeve´rite´delafonctioncorrespondantau polynoˆme X 13 + X 12 X 2 + X 15 X 37 .
The´ore`mederepr´esentationnormalealg´ebrique Toutefonctionbool´eennepeutsexprimer demanie`reunique comme un polynˆomer´eduit.
X 1 X 3 + X 2 X 3 + X 3
Exemple .Lepolynˆomesuivantestr´eduit
De´nition .Unpolynomedonttouslestermesmonoˆmiauxsontdela ˆ forme X 1 a 1 X 2 a 2 ∙ ∙ ∙ X na n avec a 1 , . . . , a n = 0 ou 1 estunpolynˆome r´eduit .
Polynˆomesr´eduits
Fs[21X.,..X,]nobsne´loennenoFstiucauononxfioctesptlonyoˆemdsnactionsbool´eenne´gnIorPMeireineerstMaarhptpgortdoeinIematath´Cryique
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.