En 1971, Gilbert Labelle a introduit la fonction chapeau qui est une traduction entre deux représentations de fonctions booléennes. Cette fonction intimement liée au calcul propositionnel possède de remarquables propriétés et permet de trouver le polynôme associé à une table de vérité et réciproquement. La fonction chapeau est involutive et nous en fournissons une démonstration car l'article original de Gilbert Labelle n'en présentait pas. Pour une base de numération fixée p où p est premier, un nombre entier est identifié par une suite de chiffres appelés «pits» par analogie aux bien connus bits. Toute fonction définie sur N est exprimable par une fonction définie sur les pits. Une telle fonction est décomposable en une suite de sous-fonctions qui expriment individuellement chaque chiffre de sortie de la fonction originelle à partir des chiffres en entrée. Différentes décompositions de fonctions en pits sont présentées.
Les calculs liés à ces décompositions sont difficiles et des algorithmes astucieux sont développés en Maple pour obtenir quelques résultats qui suggèrent des formules générales que nous prouvons par la suite. Un bit est un cas particulier des pits et il y a une bijection entre les opérateurs d'addition/produit et les portes logiques. Il est alors possible pour un concepteur en électronique de réaliser une implémentation parallèle de fonctions logiques/arithmétiques à partir des décompositions. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Représentations de fonctions, Calcul propositionnel, Décompositions de fonctions, Programmation Maple, Calcul parallèle.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMUQ.3232 |
| Date | January 2006 |
| Creators | Simard, Patrick |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Detected Language | French |
| Type | Mémoire accepté, NonPeerReviewed |
| Format | application/pdf |
| Relation | http://www.archipel.uqam.ca/3232/ |
Page generated in 0.0013 seconds