:: wikimiki.org ::

Table De Vérité

Table de vérité

Une table de vérité est un outil permettant de représenter un phénomène logique passif. Ces outils sont couramment utilisés en électronique (porte logique) et en informatique (tests). Une table de vérité est un tableau qui représente des entrées (en colonne) et des états binaire (0/1, faux/vrai, éteint/allumé, etc.). Une sortie, également représentée sous forme de colonne, est la résultante des états d'entrée, elle-même exprimée sous forme d'état binaire. Comment lire une table de vérité :
On recherche dans la liste des entrées l'état souhaité pour en déterminer la sortie (qui se trouve donc sur la même ligne). Dans l'exemple suivant, pour répondre à la question « quel est l'état de la sortie quand a et b sont activés », il faut se placer sur la derniere ligne. Exemple de base : Exemple composé: Voir aussi :
- Algèbre de Boole
- Table de Karnaugh Catégorie:Logique

Logique

ko:논리학 ms:Logik ja:論理学 simple:Logic th:ตรรกศาสตร์ Catégorie:Philosophie Catégorie:Algorithmique Catégorie:Sciences cognitives Catégorie:Logique Catégorie:Rhétorique La logique est initialement l'une des grandes disciplines de la philosophie, elle est devenue au une partie des mathématiques. Aujourd'hui, elle est en outre partie intégrante de : l'ingénierie informatique, la linguistique, la psychologie cognitive et, la communication sociale.

Généralités

La logique est l'étude de la nature, des concepts, de la vérité, des jugements et, de la validité des raisonnements. Elle se déploie ainsi aujourd'hui selon les quatre grands axes que sont :
- la théorie des ensembles,
- la théorie des modèles,
- la théorie de la démonstration,
- la théorie de la calculabilité. Cette classification en quatre grands axes, généralement admise, est celle proposée par J. Barwise dans son ouvrage [http://www.elsevier.com/wps/find/bookdescription.cws_home/501736/description Handbook of Mathematical Logic]. Depuis, un cinquième grand axe semble se dessiner avec les travaux sur la théorie des types.

Disciplines de la logique

- Les syllogismes aristotéliciens
- Le calcul des propositions
- Le calcul des prédicats
- La logique intuitionniste
- La logique classique
- Les logiques multivalentes :
- La logique trivalente
- La logique tétravalente
- Les logiques à plus de 4 valences
- Les logiques à une infinité de valences (cf. probabilités)
- Les logiques modales :
- La logique épistémique
- La logique déontique
- La logique temporelle
- Les paradoxes
- L'algorithme d'unification en logique
- La logique floue

Philosophie

Antiquité

La logique est à l'origine une réflexion sur l'accord du discours (logos) avec lui-même. On peut dire qu'elle est un effort de la pensée pour rendre sa propre expression non contradictoire. Par suite, elle est un outil (organon) assurant la cohérence de la reflexion. La philosophie se sert donc de la logique pour organiser son discours et lui assurer une pertinence concernant ses hypothèses sur le monde.
La cohérence d'un discours a deux aspects qui correspondent aux différents sens du concept de vérité :
- La cohérence interne du discours lui-même : c'est la logique dans son aspect purement formel.
- La cohérence externe : c'est la définition matérielle de la vérité : « adequatio rei et intellectus », l'accord du contenu avec la réalité.
Le premier type de cohérence peut se faire en vue du second, mais s'en détache aussi pour constituer un domaine conceptuel autonome.
En philosophie, la logique pose le problème des relations entre le langage et la pensée : la logique semble être en effet à la fois l'effet et la cause du discours. Elle découle du logos en philosophie (le sens du discours) ; mais, en mathématique (la forme), la cohérence formelle semble s'engendrer d'elle-même. La logique a très tôt été utilisée contre elle-même, c'est-à-dire contre les conditions mêmes du discours : le sophiste Gorgias l'utilise dans son Traité du non-être afin de prouver qu'il n'y a pas d'ontologie possible : « ce n'est pas l'être qui est l'objet de nos pensées ». La vérité matérielle de la logique est ainsi ruinée. Le langage acquiert ainsi sa propre loi, qui est celle de la logique, indépendante de la réalité. Mais les sophistes ont été écartés de l'histoire de la philosophie (sophiste a pris un sens péjoratif), si bien que la logique, dans la compréhension qu'on en a eu par exemple au Moyen Âge, est restée soumise à la pensée de l'être.

Kant, quant à lui, définit la logique comme une science qui expose dans le détail et prouve de manière stricte, uniquement les règles formelles de toute pensée. L'œuvre d'Aristote appelée l'Organon, où figure notamment l'étude du syllogisme, fut longtemps considérée comme le manuel de référence sur ce sujet. Mais la naissance d'une logique formelle non prédicative, à partir du , a quelque peu changé cet état de fait. Ainsi Frege remplace-t-il l'analyse prédicative par une distinction entre fonction et concept. La logique a pour origine la lutte du vrai et du faux, de l'être et du non-être. Il a fallu attendre le début du pour que l'évidence de cette bivalence soit remise en question : des logiques trivalentes, ajoutant une valeur indéterminée, sont alors inventées (Kleene, Lukasiewicz, Bochvar). Mais celles-ci, se généralisant en logiques polyvalentes, ne remettaient néanmoins pas en question l'appartenance stricte d'une proposition à l'une (et une seule) de ces valeurs. C'est à partir de 1965 que Zadeh élabore une logique floue (fuzzy logic) dans laquelle une proposition est vraie selon un certain degré de probabilité (degré auquel on assigne lui-même un degré de probabilité). Loin du monde tranché de la certitude classique, un monde flou se révèle dans toute sa complexité.

Mathématiques

Dans ce dernier cas, sa position est un peu particulière d'un point de vue épistémologique, puisqu'elle est à la fois un outil de définition des mathématiques, et une branche de ces mêmes mathématiques, donc un objet.

Notions élémentaires de logique formelle

Un langage logique est défini par une syntaxe, c'est-à-dire un système de symboles et de règles pour les combiner sous formes de formules. De plus, une sémantique est associée au langage. Elle permet de l'interpréter, c'est-à-dire d'attacher à ces formules ainsi qu'aux symboles une signification. Un système de preuve nous permet également de calculer la signification des formules en construisant des démonstrations. La logique comprend classiquement :
- la logique des propositions,
- la logique des prédicats. Considérons un langage logique. Ce dernier est : soit un langage propositionnel, on parle alors de logique des propositions ; soit un langage du premier ordre, on parle alors de logique des prédicats. Bien évidemment, ces langages logiques diffèrent de par leur syntaxe. Considérons leurs syntaxes respectives. La syntaxe de la logique des propositions est fondée sur des variables de propositions appelées également atomes que nous notons avec des lettres minuscules (p, q, r, s, etc.). Ces symboles représentent des propriétés qui sont, soit vraies, soit fausses. Ces variables sont combinées au moyen de connecteurs logiques qui sont : # le connecteur binaire disjonctif (ou), # le connecteur binaire conjonctif (et), # le connecteur binaire de l'implication (->), # le connecteur monadique de la négation (non). Ces variables forment alors des formules appelées également propositions. Nous les notons par des lettres grecques minuscules (phi, psi, thêta, etc.). La syntaxe de la logique d'ordre un, contrairement à celle d'ordre zéro, considère d'une part les termes qui représentent les objets étudiés, et d'autre part les formules qui sont des propriétés sur ces objets. Dans la suite de ce manuscript, nous noterons V l'ensemble des variables (x,y,z…), F l'ensemble des symboles de fonctions (f,g…) et P l'ensemble des symboles de prédicats (P,Q…). On dispose également d'une application dite d'arité m. Qu'en est-il de la signification d'une formule? C'est l'objet de la sémantique. Là encore, elle diffère selon le langage envisagé. En logique propositionnelle, une formule est soit vraie soit fausse. Plus formellement, l'ensemble des valeurs de vérité est un ensemble B de deux booléens : le vrai (1) et le faux (0). La signification des booléens est définie à l'aide de fonctions de booléens vers des booléens. Ces fonctions peuvent être représentées sous la forme de table de vérité. La signification d'une formule dépend donc de la valeur de vérité de ses variables. On parle d'interprétation ou d'affectation. Comme dans le cas propositionnel, la sémantique de la logique du premier ordre est décrite par une interprétation. Cependant le langage de la logique du premier ordre est plus riche. En conséquence, de nouvelles définitions sont nécessaires. Contrairement au langage propositionnel, les interprétations et les affectations sont des objets différents. Une affectation donne une valeur à chaque variable, alors qu'une interprétation décrit le domaine des valeurs et la sémantique des symboles de fonctions et de prédicats. Nous avons doté la logique propositionnelle ainsi que la logique du premier ordre d'une sémantique. Toutefois, il est difficile, au sens de la complexité algorithmique, de l'utiliser pour décider si une formule est satisfiable (ou non) voire valide (ou non). Il faudrait pour cela énumérer toutes les interprétations. Leur nombre est exponentiel. Une alternative consiste à examiner les preuves bien formées, et à considérer leurs conclusions. Pour cela nous utilisons un système de preuve. Un système de preuve est un couple (A,R), où A est un ensemble de formules appelées axiomes et R un ensemble de règles d'inférence, c'est-à-dire de relations entre des ensembles de formules (les prémisses) et des formules (la conclusion). On appelle dérivation à partir d'un ensemble d'hypothèses une suite non vide de formules qui sont : soit des axiomes, soit des formules déduites des formules précédentes de la suite. Une preuve d'une formule phi à partir d'un ensemble de formules Gamma est une dérivation à partir de Gamma dont la dernière formule est phi.

Quantification

On introduit essentiellement deux quantificateurs en logique classique :
-

\exists

(il existe au moins un), appelé quantificateur existentiel.
-

\forall

(pour tout), appelé quantificateur universel. Un troisième quantificateur, qui peut être défini à partir des quantificateurs précédents, est souvent introduit :
-

\exists

! (il existe un seul). Grâce à la négation, les quantificateurs existentiels et universels jouent des rôles duals et donc, en logique classique, on peut fonder le calcul des prédicats sur un seul quatificateur.

Automatisme et Informatique

Dans ces deux domaines la logique est omniprésente et représente le fondement de ces diciplines.
- En automatisme, afin de pouvoir ordonner des processus en fonction de conditions précises, un fonctionnement logique est nécessaire. À l'aide d'opérateurs logiques simples et combinés, la logique combinatoire permet de déterminer des conditions et des prises de décisions automatisées. Autrefois, les automates contenaient de multiples relais assurant ces fonctions. Aujourd'hui, ce sont en fait des micro-ordinateurs spécialisés disposant d'une partie d'électronique de puissance pour interagir avec son environnement et, une interface homme/machine adaptée.
- En informatique :
- dans la partie électronique numérique, les mêmes opérateurs logiques sont utilisés en grand nombres ;
- dans la partie logiciel, les opérateurs de logique booléenne des langages de programmation sont très utilisés, comme système de comparaison et de prise de décision ;
- au niveau des langages de programmation, il existe des relations profondes entre la logique intuitionniste et le lambda-calcul (et donc les langages fonctionnels). La correspondance de Curry-Howard propose de voir les propositions comme des types, et une preuve d'une proposition P comme un terme ayant le type P. On obtient alors des règles identiques à celles utilisées pour le typage des termes du lambda-calcul. Cette approche est utilisée dans un certain nombre de logiciels d'aide à la preuve, comme Coq ou [http://www.cl.cam.ac.uk/Research/HVG/HOL/ HOL]. Enfin, l'ajout de continuations au langage permet de retrouver la logique classique, le type de ces nouveaux termes pouvant être rapproché du tiers-exclus.
- Afin de spécifier un système (protocole, logiciel...), notamment en model-checking, on fait appel aux logiques temporelles.

Voir aussi

- Tractatus logico-philosophicus
- Fonction logique

Porte logique

Les types de fonctions logique

Il existe deux grands types de fonctions logiques :
- les fonctions logiques "combinatoire" bases du calcul booléens : Qui résulte de l'analyse combinatoire des variations des grandeurs d'entrées uniquement.
- les fonctions logiques "séquentielle" ou : bascule, résultant de l'association de plusieurs fonctions logique "combinatoire" : Les grandeurs de sorties dépendent, de la variation des grandeurs d'entrées mais également de la valeurs de la sortie à l'instant précédent. Les fonctions logiques "combinatoire" directement issues des mathématique (algèbre de Boole) sont les outils de base de l'électronique numérique animant automatisme et informatique. Elles sont utilisées en électronique sous forme de portes logiques.
- Ces portes électroniques sont construites à partir de plusieurs transistors reliés entre eux.
- Selon la modélisation utilisée, on prendra en compte les temps de retard ou pas dans les calculs.

Classification

Les portes peuvent se classer suivant leur nombre d'entrées :
- « Portes » sans entrée : VRAI,- FAUX.
- Porte à une entrée : NON.
- Portes à deux entrées : ET, NON-ET, OU, NON-OU OU exclusif, coïncidence dite aussi NON-OU exclusif ou équivalence, implication.
- À partir de trois entrées, le nombre de fonctions commence à subir l'influence de l'explosion combinatoire. On note toutefois l'existence de : ET, OU, etc. à plus de deux entrées. Des fonctions plus complexes, bascule, compteur, additionneur voire puce complète. Ces fonctions sont entre autres utilisées dans les fonctions de chip select indispensables à l'adressage mémoire, ou pour le multiplexage.

Représentation

Pour définir chacune des fonctions logiques, nous donnerons plusieurs représentations :
- une représentation électrique : schéma développé à contacts
- une représentation algébrique : équation
- une représentation arithmétique : table de vérité
- une représentation temporelle : chronogramme
- une représentation logique : symbole logique

Fonction OUI

Exemple : une lampe est montée en série avec le contact, elle s'allume quand le contact « a » est actionné. ; Schéma : Image:Fonctions_logiques(1-a).png ; Équation :

L = a

; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(1-d).png ; Symbole : Image:Fonctions_logiques(1-e).png ;Voir aussi
- identité
- relation d'équivalence

Fonction NON

NON (NOT en anglais)
Exemple : une lampe est montée en série avec le contact, elle s'éteint quand le contact « a » est actionné. ; Schéma : Image:Fonctions_logiques(2-a).png ; Équation :

L = \bar

: L = ¬A ; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(2-d).png ; Symbole : Image:Fonctions_logiques(2-e).png

Fonction ET

ET (AND en anglais)
Exemple : une lampe s'allume si l'on appuie sur « a » ET « b » et seulement dans ce cas là. La fonction « ET » est caractérisé par des contacts montés en série. ; Schéma : Image:Fonctions_logiques(3-a).png ; Équation :

L = a \cdot b

; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(3-d).png ; Symbole : Image:Fonctions_logiques(3-e).png ; Conjonction : P ∧ Q

Fonction OU

OU (OR en anglais)
Exemple : une lampe s'allume si l'on appuie sur « a » OU « b » à plus forte raison si l'on appuie sur « a » et sur « b ». La fonction « OU » est caractérisée par des contacts montés en parallèle. ; Schéma : Image:Fonctions_logiques(4-a).png ; Équation :

L = a + b

; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(4-d).png ; Symbole : Image:Fonctions_logiques(4-e).png ; Disjonction : P ∨ Q

Fonction OU exclusif

OU exclusif (XOR en anglais)
Exemple : une lampe s'allume si l'on appuie sur « a » ou « b » seulement, mais pas si l'on appuie sur « a » et « b » simultanément. ; Schéma : Image:Fonctions_logiques(5-a).png ; Équation :

L = a \oplus b

; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(5-d).png ; Symbole : Image:Fonctions_logiques(5-e).png Pour plus de détail : OU exclusif

Fonction NON-ET

NON-ET (NAND en anglais)
Exemple : une lampe s'allume sauf si l'on appuie sur « a » et « b » et seulement dans ce cas là. La fonction « NON-ET » est caractérisé par des contacts montés en parallèle. ; Schéma : Image:Fonctions_logiques(6-a).png ; Équation :

L = \overline = \bar + \bar

; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(6-d).png ; Symbole : Image:Fonctions_logiques(6-e).png

Fonction NON-OU

NON-OU (NOR en anglais)
Exemple : une lampe s'allume sauf si l'on appuie sur « a » ou « b » et seulement dans ce cas là. La fonction « NON-OU » est caractérisé par des contacts montés en série. ; Schéma : Image:Fonctions_logiques(7-a).png ; Équation :

L = \overline = \bar . \bar

; Table de vérité : ; Chronogramme : Image:Fonctions_logiques(7-d).png ; Symbole : Image:Fonctions_logiques(7-e).png

Universalité de l'opérateur NON-ET

Universalité de l'opérateur NON-OU

Fonction NON

Image:Fonctions_logiques(9-1).png

Fonction OU

Image:Fonctions_logiques(9-2).png

Fonction ET

Image:Fonctions_logiques(9-3).png

Voir aussi

- Sortance
- Table de Karnaugh Catégorie:Électronique Catégorie:Logique Catégorie:Automatisme ja:論理回路

Système binaire

Cet article est consacré au système de numération binaire. En astrophysique, un système binaire est également un système constitué de deux astres tournant l'un autour de l'autre (voir étoile binaire). ---- Le système binaire est un système de numération utilisant la base 2. On nomme couramment bit (de l'anglais binary digit, soit « chiffre binaire ») les chiffres de la numérotation binaire. Ceux ci ne peuvent prendre que deux valeurs, notées par convention 0 et 1.

Usage

Le système binaire est utilisé pour représenter un ensemble de deux valeurs antinomiques, comme vrai/faux, blanc/noir, marche/arrêt (on et off en anglais) tel le système des booléens. Il convient notamment pour représenter le fonctionnement de l'électronique numérique utilisée dans les ordinateurs, d'où son usage en informatique. S'il se montre peu intuitif pour l'usage humain (plus habitué à compter avec ses doigts, donc en base décimale), il permet d'utiliser en électronique des circuits de commutation, dont le coût unitaire est si faible (quelques picoeuros) que la charge des traductions depuis et vers le système décimal ne constitue plus un problème.

Exemple de conversion du système décimal vers le système binaire

Pour développer l'exemple ci-dessus, le nombre 45 853 écrit en base décimale provient de la somme de nombres ci-après écrits en base décimale. 32 768 1 fois 32 768 en fait 2 multiplié 15 fois par lui même soit 2¹⁵ + 0 0 fois 16 384 en fait 2 multiplié 14 fois par lui même soit 2¹⁴ + 8 192 1 fois 8 192 idem 13 idem 2¹³ + 4 096 1 fois 4 096 idem 12 idem 2¹² + 0 0 fois 2 048 idem 11 idem 2¹¹ + 0 0 fois 1 024 idem 10 idem 2¹⁰ + 512 1 fois 512 idem 9 idem 2⁹ + 256 1 fois 256 idem 8 idem 2⁸ + 0 0 fois 128 idem 7 idem 2⁷ + 0 0 fois 64 idem 6 idem 2⁶ + 0 0 fois 32 idem 5 idem 2⁵ + 16 1 fois 16 idem 4 idem 2⁴ + 8 1 fois 8 idem 3 idem 2³ + 4 1 fois 4 idem 2 idem 2² + 0 0 fois 2 idem 1 idem 2¹ = 2 + 1 1 fois 1 idem 0 idem 2⁰ = 1 =45 853 Soit écrit en système positionnel et en numération décimale (en écrivant les puissances de 2) : 45 853 = 1×2¹⁵ + 0×2¹⁴ + 1×2¹³ + 1×2¹² + 0×2¹¹ + 0×2¹⁰ + 1×2⁹ + 1×2⁸ + 0×2⁷ + 0×2⁶ + 0×2⁵ + 1×2⁴ + 1×2³ + 1×2² + 0×2¹ + 1×2⁰ Soit en système positionnel et en numération binaire puisque l'on ne reporte pas les puissances de 2 45 853 décimal s'écrit 1011 0011 0001 1101 binaire (séparés par groupes de 4 bits) On voit qu'il y a 16 bits.

Codage binaire

Il existe différents systèmes numériques basés sur la représentation binaire.

Numération de position

Le codage le plus courant est l'équivalent en base deux de la numération de position que nous utilisons quotidiennement en base 10.

Représentation des entiers positifs

Pour trouver la représentation binaire d'un nombre, on le décompose en somme de puissances de 2. Par exemple avec le nombre dont la représentation décimale est 59 : 59 = 1×32 + 1×16 + 1×8 + 0×4 + 1×2 + 1×1 59 = 1×2⁵ + 1×2⁴ + 1×2³ + 0×2² + 1×2¹ + 1×2⁰ 59 = 111011 en binaire Avec n bits, ce système permet de représenter les nombres entre 0 et 2ⁿ-1. Il est donc possible de compter sur ses dix doigts jusqu'à 1023 (2¹⁰-1) en binaire. Il suffit d'affecter à chaque doigt une valeur binaire (pouvant être représenté par un doigt plié). [Pour Robertv, avec 10 doigts on peut compter jusqu'à 1023. En effet si chaque doigt représente une puissance de 2 avec la convention doigt levé, alors la puissance de 2 est retenue (1 en binaire); doigt replié, alors la puissance de 2 n'est pas retenue (0 en binaire). Doigt Main Puis. Valeur en de 2 numération décimale Auriculaire de la main droite levé 2^0 1 Annulaire = 2^1 + 2 Majeur = 2^2 + 4 Index = 2^3 + 8 Pouce = 2^4 + 16 Pouce de la main gauche levé 2^5 + 32 Index = 2^6 + 64 Majeure = 2^7 + 128 Annulaire = 2^8 + 256 Auriculaire = 2^9 + 512 ------- Somme =1 023 (Pour mémoire 2^10 =1 024) Ce qui confirme la formule 2^10-1=1 024-1 =1 023 On remarque qu'avec 10 doigts on peut prendre en compte les 10 premières puissances de 2 s'échelonnant de 2^0 à 2^9 c'est à dire la somme des 10 premières puissances de 2]

Représentation des entiers négatifs

Pour compléter la représentation des entiers, il faut pouvoir écrire des entiers négatifs. On ajoute pour cela à la représentation un bit de signe, placé en tête. Un bit de signe nul indique une valeur positive, un bit de signe positionné à un une valeur négative. Cette règle permet de rester cohérent avec le système de représentation des entiers positifs : il suffit d'ajouter un 0 en tête de chaque valeur.

Complément à un

Ce codage, fort simple, consiste à inverser la valeur de chaque bit composant une valeur binaire. Par exemple, pour obtenir -5 : 0101 valeur décimale 5 1010 complément à un Le souci avec un tel système est qu'il y a toujours deux représentations de la valeur 0 pour un nombre de bit donné. voir article détaillé : complément à un

Complément à deux

Afin de palier ce défaut, on a introduit la représentation par complément à deux. Celle-ci consiste à réaliser un complément à un de la valeur, puis d'ajouter 1 au résultat. Par exemple pour obtenir -5: 0101 codage de 5 en binaire 1010 complément à un 1011 on ajoute 1 : représentation de -5 en complément à deux Ce codage à l'avantage de ne pas nécessiter de différenciation spéciale des nombres positifs et négatifs, et évite en particulier le problème d'ordinateurs anciens (Control Data 6600) qui avaient un « +0 » et un « -0 » dont il fallait faire comprendre aux circuits de tests que c'était le même nombre ! Voici une addition de -5 et +7 réalisée en complément à deux sur 4 bits : -5 1011 +7 0111 __ ____ 2 (1) 0010 (on 'ignore' la retenue) Avec n bits, ce système permet de représenter les nombres entre -2^n-1 et 2^n-1-1. voir article détaillé : Complément à deux

Code Gray ou binaire réfléchi

Ce codage permet de ne faire changer qu'un seul bit à la fois quand un nombre est augmenté d'une unité. 0 0000 1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100 Pour passer d'une ligne à la suivante, on inverse le bit le plus à droite possible conduisant à un nombre nouveau. Le nom de code binaire réfléchi vient d'une méthode de construction plus pratique pour choisir quel bit inverser quand on passe d'un nombre au suivant:
- On choisit un code de départ: zéro est codé 0 et un est codé 1.
- Puis, à chaque fois qu'on a besoin d'un bit supplémentaire,on symétrise les nombres déjà obtenus (comme une reflexion dans un miroir) et on rajoute un 1 au début des nouveaux nombres: 0 0 0 .0 0 00 0 .00 0 000 1 1 1 .1 1 01 1 .01 1 001 miroir->------ 2 .11 2 011 2 .1 2 11 3 .10 3 010 3 .0 3 10 ------- 4 .10 4 110 5 .11 5 111 6 .01 6 101 7 .00 7 100 Ce code est surtout utilisé pour des capteurs de positions, par exemple sur des règles optiques. En effet si on utilise le code binaire standard, lors du passage de la position un (01) à deux (10) -- permutation simultanée de 2 bits -- il y a risque de passage transitoire par trois (11) ou zero (00), ce qu'évite le code Gray. On remarquera que le passage du maximum (sept sur 3 bits) à zéro se fait également en ne modifiant qu'un seul bit. Ceci permet par exemple d'encoder un angle, comme la direction d'une girouette: 0=Nord, 1=Nord-Est, 2=Est, ... 7=Nord-Ouest. Le passage de Nord-Ouest à Nord se fait également sans problème en ne changeant qu'un seul bit. Voir Roue de codage. Le code Gray sert également dans les tables de Karnaugh utilisées lors de la conception de circuits logiques.

Décimal codé binaire (« binary coded decimal », ou BCD)

Ce codage consiste à représenter chacun des chiffres de la numérotation décimale sur 4 bits: 1994 = 0001 1001 1001 0100 1×1000 + 9×100 + 9×10 + 4×1 Il présente l'avantage de simplifier la conversion avec la notation décimale. Avec n bits (n multiple de 4), il est possible de représenter les nombres entre 0 et 10^n/4-1. Soit approximativement entre 0 et 1.778ⁿ-1. Le BCD est un code redondant, en effet certaines combinaisons ne sont pas utilisées (comme 1111 par exemple). Cette représentation évite par construction tous les problèmes gênants de cumul d'arrondi qui interviendraient lors de la manipulation de grands nombres dépassant la taille des circuits en arithmétique entière et obligent à recourir au flottant. Il est cependant possible de manipuler des nombres à précision arbitraire en utilisant un codage plus efficient que le BCD. Il existe des variantes du codage BCD:
- code Aiken où 0, 1, 2, 3, 4 sont codés comme en BCD et 5, 6, 7, 8, 9 sont codés de 1011 à 1111. Il permet d'obtenir le complément à 9 en permutant les 1 et les 0.
- codage binaire excédent 3 qui consiste à représenter le chiffre à coder + 3.

Applications

Théorie de l'information

En théorie de l'information, on peut utiliser le bit comme unité de mesure de l'information. La théorie elle-même est indifférente à la représentation des grandeurs qu'elle utilise.

Logique

La logique classique est une logique bivalente: une proposition est soit vraie, soit fausse. Il est donc possible de représenter la vérité d'une proposition par un chiffre binaire. On peut par exemple modéliser les opérations de l'arithmétique binaire à l'aide de l'algèbre de Boole. L'algèbre de Boole représente un cas très particulier d'usage des probabilités ne faisant intervenir que les seules valeurs de vérité 0 et 1. Voir Théorème de Cox-Jaynes.
Informatique
Le binaire est utilisé en informatique car il permet de modéliser le fonctionnement des composants de commutation comme le TTL ou le CMOS. La présence d'un seuil de tension au bornes des transistors, en négligeant la valeur exacte de cette tension, représentera 0 ou 1. Par exemple le chiffre 0 sera utilisé pour signifier une absence de tension à 0,5V près, et le chiffre 1 pour signifier sa présence à plus de 0,5V. cette marge de tolérance permet de pousser les cadences des microprocesseurs à des valeurs atteignant sans problème (hormis d'échauffement) plusieurs gigahertz. Ne sachant pas techniquement réaliser des composants électroniques à plus de deux états stables (0 ou plus de 0,5V), on n'utilise que la logique (bivalente) et donc le système binaire. En informatique, la représentation binaire permet de clairement manipuler des bits : chaque chiffre binaire correspond à un bit. La représentation binaire nécessitant l'usage de beaucoup de chiffres (même pour des nombres assez petits), ce qui entraînerait d'importants problèmes de lisibilité et donc de risques d'erreur de transcription pour les programmeurs on lui préfère pour eux une représentation parfois octale ou plus fréquemment hexadécimale. La quasi totalité des microprocesseurs actuels travaillant avec des mots de 8, 16, 32 ou 64 bits, la notation hexadécimale permet de manipuler l'information par paquets de 4 bits (contre 3 pour la notation octale plus populaire du temps des premiers mini-ordinateurs DEC à 12 ou 36 bits).
- 63 ₍₁₀₎ = 111111 ₍₂₎ = 77 ₍₈₎ = 3F ₍₁₆₎
- 64 ₍₁₀₎ = 1000000 ₍₂₎ = 100 ₍₈₎ = 40 ₍₁₆₎
- 255 ₍₁₀₎ = 11111111 ₍₂₎ = 377 ₍₈₎ = FF ₍₁₆₎
- 256 ₍₁₀₎ = 100000000 ₍₂₎ = 400 ₍₈₎ = 100 ₍₁₆₎
Voir aussi

- Format des données
- Arithmétique binaire
- Préfixe binaire
- Virgule flottante
- Système bibi-binaire de Boby Lapointe Catégorie:Numération Catégorie:Informatique Catégorie:Automatisme ko:이진법 ja:二進記数法 th:เลขฐานสอง

Algèbre de Boole (logique)

L'algèbre de Boole est la partie des mathématiques, de la logique et de l'électronique qui s'intéresse aux opérations et aux fonctions sur les variables logiques. Pour la structure algébrique d'algèbre de Boole voir Algèbre de Boole (structure). Le nom provient de George Boole, un mathématicien britannique qui durant le milieu du restructura complètement la logique en un système formel. Plus spécifiquement, l'algèbre booléenne permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs de la logique des propositions. Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphoniques par Claude Shannon. L'algèbre de Boole des fonctions logiques permet de modéliser des raisonnements logiques, en exprimant un « état » en fonction de conditions. Par exemple : : Communication = Émetteur ET Récepteur :: Communication est « VRAI » Si Émetteur actif ET Récepteur actif (c'est une fonction logique dépendant des variables Émetteur et Récepteur) : Décrocher = ( Décision de répondre ET Sonnerie ) OU décision d'appeler :: Décrocher est « VRAI » Si on entend la sonnerie ET que l'on décide de répondre OU si l'on décide d'appeler. L'algèbre de Boole étant un domaine commun à trois disciplines, on rencontre des notations différentes pour désigner un même objet. Dans le reste de l'article, on indiquera les diverses notations, mais on en privilégiera une pour conserver une certaine homogénéité.

Algèbre de Boole des valeurs de vérité

On appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité . Cet ensemble est aussi noté
- B =
- B =

\

. On privilégiera dans la suite la notation B = . Sur cet ensemble on peut définir deux lois (ou opérations ou foncteurs), les lois ET et OU et une transformation appelée le complémentaire, l'inversion ou le contraire.

La loi ET

Elle est définie de la manière suivante : a ET b est VRAI si et seulement si a est VRAI et b est VRAI. Cette loi est aussi notée
-

\cdot \,

\wedge

.
- « & » ou « && » dans quelques langages de programmation (Perl, C...)
- « AND » dans certains langages de programmation
- « ∧ » dans quelques notations algébriques, ou en APL On privilégiera dans la suite la notation

\cdot \,

On peut construire la table de cette loi (comme une table d'addition ou de multiplication de notre enfance) mais on ne la confondra pas avec une table de vérité

La loi OU

Elle est définie de la manière suivante : a OU b est VRAI si et seulement si a est VRAI ou b est VRAI. (notons que si a est vrai et que b est vrai aussi, alors a OU b est vrai.) Cette loi est aussi notée
-

+ \,

- « | » ou « || » dans quelques langages de programmation
- « OR » dans certains langages de programmation
- « ∨ » dans quelques notations algébriques ou en APL. On privilégiera dans la suite la notation

+ \,

mais on prendra garde que cette loi n'a pas de rapport avec l'addition que l'on connaît. On peut construire la table de cette loi:

Le contraire

Le contraire de "a" est VRAI si et seulement si a est FAUX. Le contraire de a est noté
- non-a
-

\bar

\neg (a)

- « ! » dans quelques langages de programmation
- « NOT » dans certains langages de programmation
- « ~ » dans quelques notations algébriques ou en APL. On privilégiera dans la suite la notation

\bar

. On obtient alors

\bar=1

\bar=0

Propriétés

Associativité

Comme avec les opérations habituelles, certaines parenthèses sont inutiles:
( a + b ) + c = a + (b + c) = a + b + c
( a . b ) . c = a . (b . c) = a . b . c

Commutativité

L'ordre est sans importance.
a + b = b + a
a . b = b . a

Distributivité

Comme avec les opérations habituelles, il est possible de distribuer:
a . ( b + c ) = a . b + a . c
Attention: comportement différent par rapport aux opérateurs + et
- habituels:
a +( b . c ) = ( a + b ) . ( a + c )

Idempotence

a + a + a [...] = a
a . a . a [...] = a

Complémentarité

a = \overline

: (« La lumière est allumée » = « la lumière n'est pas non allumée »)

a + \overline = 1

: (« VRAI » SI lumière_allumée OU SI lumière_non_allumée → c'est toujours le cas → vrai dans tous les cas → toujours VRAI, donc =1)

a . \overline = 0

: (« VRAI » SI lumière_allumée ET SI lumière_non_allumée → impossible → faux dans tous les cas → toujours FAUX donc =0)

Structure

On retrouve alors toutes les propriétés qui confèrent à B une structure d'algèbre de Boole)

Priorité

Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux mêmes règles que les opérations « de tous les jours », la fonction ET (multiplication logique) est ainsi prioritaire par rapport à la fonction OU (somme logique) ; on peut, pour s'aider, placer des parenthèses dans les opérations. : Exemple : :
: On cherche a . b + c = ???
: D'abord on calcule a . b:
: a . b = 0 . 1
: 0 . 1 = 0
: Puis, on calcule 0 + c:
: 0 + c = c
: c = 1
: Le résultat final est donc:
: a . b + c = 1

Théorème de De Morgan

\overline = \overline . \overline

: Dans les deux cas, l'expression ne sera VRAIE que si a et b sont fausses.

\overline = \overline + \overline

: Dans les deux cas, l'expression ne sera VRAIE que si a ou b sont fausses.

Fonctions logiques

Mathématiquement, une fonction logique ou opérateur logique est une application de Bⁿ dans B. En électronique, une fonction logique est une boîte noire qui reçoit en entrée un certain nombre de variables logiques et qui rend en sortie une variable logique dépendant des variables d'entrée. L'article fonction logique précise comment construire les boîtes noires de quelques fonctions fondamentales Une table de vérité permet de préciser l'état de la sortie en fonction des états des entrées. On démontre que toute fonction logique peut se décrire à l'aide des trois opérations de base.
-

+\,

\cdot\,

\bar\,

Fonctions logiques fondamentales

Elles sont issues des trois opérations de base et définissent alors
- une fonction de B dans B : le complémentaire ou inversion
- deux fonctions de B² dans B qui sont la somme (ou OU) et le produit (ou ET)

Fonctions logiques composées

Ce sont les fonctions logiques à deux variables. Parmi celles-ci, on en dénombre certaines suffisamment intéressantes pour qu'on leur donne un nom.

OU exclusif

Le OU étudié jusqu'à présent doit se comprendre de la manière suivante : « l'un ou l'autre ou les deux ». Il est également appelé « OU inclusif ». Le OU exclusif (ou XOR) s'entend comme : « l'un ou l'autre mais pas les deux ». Il se compose de la manière suivante : :

a\ XOR\ b = (a+b).\overline

Le « ou exclusif » est parfois noté par le signe arithmétique différent de, auquel il est équivalent. Fonctionnellement, on utilise aussi un + entouré: a ⊕ b.

Équivalence

L'équivalence (notée EQV) est vrai si les deux entrées ont la même valeur et faux sinon. Elle se compose comme suit : :

a\ EQV\ b = \overline+(a.b)

On peut aussi dire que : :

a\ EQV\ b = \overline

Il arrive que l'équivalence soit notée par le signe « = », bien que ce choix ne soit pas recommandé compte-tenu des autres sens possibles attachés à ce signe.

Implication

L'implication (notée IMP) s'écrit de la manière suivante :

a\ IMP\ b = \overline+b

Cette opération n'est pas commutative. a est une condition suffisante pour b, qui, elle, est une condition nécessaire pour a.

Inhibition

L'inhibition (notée INH) se compose comme suit : :

a\ INH\ b = a.\overline

Cette opération n'est pas commutative.

Exemple de fonctions logiques à trois ou quatre variables

Fonction logique à trois variables

Si on reprend l'exemple du téléphone, on se trouve en présence de 3 variables :
- a = "le téléphone sonne"
- b = "on a envie de répondre"
- c= "on a envie d'appeler quelqu'un" la variable d = "on décroche" est fonction logique des 3 précédentes. On écrira que :d = ab + c car on décroche quand ça sonne et qu'on a envie de répondre ou quand on a envie d'appeller quelqu'un. La table de vérité de cette fonction d est alors la suivante. L'observation de la table montre que notre analyse première comportait une situation absurde : si le téléphone sonne et qu'on n'a pas envie de répondre, on ne décroche pas même si on a envie d'appeler quelqu'un. Il faut donc modifier la table de vérité ainsi :

Fonction logique à quatre variables

Un bon élève s'interroge s'il est sage de sortir un soir. Il doit décider en fonction de quatre propositions :
- a = il a assez d'argent
- b = il a fini ses devoirs
- c = le transport en commun est en grève
- d = l'auto de son père est disponible Cet élève pourra sortir si :
- il a assez d'argent, a = vrai
- il a fini ses devoirs, donc b = vrai
- le transport en commun n'est pas en grève, donc c = faux
- ou si l'auto de papa est disponible, donc d = vrai Donc l'expression logique de sortir en fonction de l'état des variables a, b, c et d ; et elle peut s'écrire ainsi : :Sortir =

a.b.(+d)

Minimisation d'une expression

Une fonction logique peut être déterminée
- soit sous forme d'une expression faisant intervenir les 3 opérations (

+\,

\cdot\,

\bar\,

)
- soit sous forme de sa table de vérité. Dans ce cas il sera toujours possible d'écrire cette fonction comme une somme de produits. Exemple: Dans l'exemple de "téléphoner2", on s'aperçoit que le résultat est à 1 quand (a, b , c) = (0 , 0 , 1) ou (0 , 1 , 1) ou (1 , 1 , 0) ou (1 , 1 , 1). :Cela permet de définir d2 par

d2 =\bar a.\bar b.c + \bar a.b.c + a.b.\bar c + a.b.c

Il est alors intéressant de trouver une expression minimisant le nombre de termes et le nombre de lettres dans chaque terme. C'est l'objectif de certaines techniques comme la méthode de Quine-Mc Cluskey, les diagrammes de Karnaugh… Exemple (suite) : la somme précédente peut être réduite en :

d2 =\bar a.c + a.b

par factorisation des deux premiers termes par

\bar a.c

et factorisation des deux derniers termes par

a.b \,

Arbre d'expression

Les expressions logiques sont souvent représentées en informatique sous forme d'arborescence. Cette dernière comporte un sommet (la racine en fait) auquel sont rattachés différents sous arbres (ou branches). Les bifurcations sont des sommets internes. Le nombre de sous-arbres reliés à un même sommet est appelé arité. Les sommets sans issue sont appelés feuilles. Chaque sommet interne est identifié par un opérateur booléen alors que les feuilles représentent les variables qui subissent ces opérations.

Voir aussi

Liens internes

Fonction logique ~ Calcul des propositions ~ Systèmes de numération ~ Électronique numérique ~ Neurone ~ George Boole ~ Opérations sur les bits

Lien externe

[http://stielec.ac-aix-marseille.fr/cours/abati/algboole.htm Algèbre de Boole appliquée à l'électronique] Catégorie:Algèbre abstraite Catégorie:Automatisme Catégorie:Logique ja:ブール代数 th:พีชคณิตแบบบูล

Table de Karnaugh

Cet article explique ce qu'est un tableau de Karnaugh, seulement dans une application logique binaire. Cet article n'explique pas les principes de base de la logique. Pour cela, voir l'article Fonctions logiques. Un tableau de Karnaugh sert à simplifier des équations logiques ou à trouver l'équation logique correspondant à une table de vérité. La méthode utilisée est graphique et simple. Elle utilise également le binaire réfléchi ou Code Gray.

Principe

Le tableau de Karnaugh est un tableau étudié pour pouvoir trouver la plus simple équation d'une table de vérité. Elle se présente comme ceci : Bien sûr, il peut y avoir plus ou moins de 4 variables (Ici A, B, C et D).
- La colonne 1 correspond aux valeurs de S pour C=0 et D=0
- La colonne 2 correspond aux valeurs de S pour C=0 et D=1
- La colonne 3 correspond aux valeurs de S pour C=1 et D=1
- La colonne 4 correspond aux valeurs de S pour C=1 et D=0
- La ligne 1 correspond aux valeurs de S pour A=0 et B=0
- La ligne 2 correspond aux valeurs de S pour A=0 et B=1
- La ligne 3 correspond aux valeurs de S pour A=1 et B=1
- La ligne 4 correspond aux valeurs de S pour A=1 et B=0 Ainsi, la case de la colonne 2 de la ligne 4 correspond à la valeur de S pour laquelle A=1, B=0, C=0 et D=1. Sa valeur peut-être trouvée dans la table de vérité ou par une équation à simplifier. On remplit de cette manière le tableau de Karnaugh. Les valeurs du tableau de Karnaugh correspondent au valeurs de la table de vérité suivante :

Méthode de recherche de l'équation

Pour trouver l'équation de S, c'est simple. Il y a deux méthodes :
- Former une somme
- Former un produit

La somme

Pour trouver une somme, il faut regrouper les valeurs de S égales à 1. Les groupes formés doivent être les moins nombreux possibles, mais il doivent englober tous les 1. Un 1 peut être compris dans plus d'un groupe, mais un 0 ne doit être inclus dans aucun. Il doivent être composé de colonne(s) et/ou de ligne(s). Si possible, il faut les assembler par valeurs d'entrées communes. Par exemple la colonne 2 et la colonne 3 ont pour valeur commune D=1. La ligne 1 et la ligne 4 ont la valeur B=0 en commun; Pour les tables de 4 variables, il faut faire de préférence :
- le rectangle 16 cases,
- puis les rectangles 8 cases, Code Gray
- puis les rectangles 4 cases,
- puis les rectangles 2 cases,
- et enfin les cases uniques. Dans l'exemple pris ci-dessus, On peut former un rectangle de 8 cases, puis un de 4 : le rectangle des colonnes 2 et 3 et le carré au croisement des lignes 2-3 et des colonnes 3-4. Le rectangle correspond à l'équation « D » car dans ces deux colonnes, D est toujours égal à 1, et dans ces deux colonnes uniquement. Le carré correspond à l'équation « B·C » car dans ces cases et dans ces cases seulement B=1 et C=1. On fait ensuite la somme des deux équations et on obtient pour équation de S : « S = D + B·C ». Cette méthode, une fois assimilée, permet de trouver une équation au premier coup d'œil, et propose une alternative simple à la simplification d'équation, qui peut rapidement devenir fastidieuse.

Le Produit

Cette méthode a pour but non pas de regrouper les « 1 » mais les « 0 », pour trouver non pas une somme de produits mais un produit de sommes.

Utilisation

Les tables/tableaux de Karnaugh sont surtout utilisé(e)s en électronique. En effet, la simplification de l'expression algébrique booléenne permet d'économiser des opérateurs logiques (portes logiques) et donc des circuits. Elle engendre aussi une économie de temps de conception et de fonds, tout en augmentant la fiabilité de l'ensemble.

Voir aussi

- Système binaire
- Électronique numérique
- Algèbre de Boole Catégorie:Automatisme Catégorie:Logique

Catégorie:Logique

Catégorie:Sciences Catégorie:Philosophie Catégorie:Sciences formelles

Article principal

- Logique

Catégories connexes

- :Catégorie:Mathématiques
- :Catégorie:Philosophie
- :Catégorie:Informatique théorique ja:Category:論理学

Категорија:User is-2

Категорија:User is

Opony �mieszne gry zycie zycie spielautomaten

:: RELATED NEWS ::

Измерване на температурата на въздуха
В метеорологичните обсерватории и станции у нас за измерване на температурата на въздуха се използват течностни термометри и термографи.

Термометър

Термометърът е универсално възприет уред за моментно отчитане на температурата на въздуха. Той се състои от 3 части: стъклена капилярна тръбица, завършваща с резервоар; стъ