ISN Opérations booléennes
Les opérations booléennes.
Logique à deux états.
On appelle « logique à deux états », ou logique "booléenne", un système d'opérations qu'on peut faire sur des objets qui ne peuvent prendre que deux valeurs, appelées faux/vrai ou 0/1.
Les circuits logiques à deux états sont nombreux dans un ordinateur, il en existe plusieurs normes. Par exemple, selon le standard TTL, la valeur 0 est définie par un tension électrique comprise entre 0 et 0,5 V, la valeur 1 est définie par une tension comprise entre 2,4 et 5 V. On arrive à garantir que ces valeurs de tensions soient respectées en concevant correctement les montages logiques :
Circuits logiques CMOS.
Le standard CMOS est plus récent que le standard TTL. Il est basé sur l'utilisation de transistors Complémentaires utilisant une technologie Metal-Oxyde-Semiconducteur (d'ou l'acronyme CMOS). 
Un transistor MOS peut être considéré comme un petit barreau de semi-conducteur (en silicium dopé), avec deux extrémités nommées "drain" (D) et "source" (S), dont la conductivité électrique est contrôlée par une électrode nommée la "porte" ou la "grille" (G) : cette électrode métallique est placée très près du barreau, elle n'en est séparée que par film isolant en oxyde de silicium très fin (quelques nm).
Pour le standard CMOS, la valeur FAUSSE (0) est définie par une tension comprise entre 0 V et la moitié de la tension d'alimentation, la valeur VRAIE (1) est définie par une tension coprise entre la 0,5 fois et une fois la tension d'alimentation. La tension d'alimentation peut varier entre 3 et 18 V, ce qui facilite l'emploi de ces circuits électroniques dans divers montages.
Autres circuits logiques.
Il existe d'autres circuits logiques que les circuits logiques à deux états, par exemple des circuits dont la sortie peut être « fausse », « vraie » ou en haute impédance (ils se comporte alors comme s'ils étaient débranchés du circuit).
Opération booléenne NON.
L'opération NON est ue opération "unaire", c'est à dire à un seul opérande.
(NON a) est VRAI si A est FAUX; (NON a) est FAUX si a est VRAI.
(NON a) se note formula_1
Réalisation d'une porte NON avec un transistor MOS à effet de champ.
Le "barreau" semi-conducteur entre drain et source peut changer de conductivité électrique :
Il est donc possible de réaliser un simple porte NON à l'aide d'un transistor et d'une résistance électrique.
Voici un schéma qui montre comment, avec un signal logique 0 à l'entrée d'un tel montage, on obtient en sortie un signal de valeur logique 1 :
Le schéma suivant montre qu'avec un signal logique 1 à l'entrée du montage, on obtient en sortie un signal de valeur logique 0 :
Remarque : dans les circuits logiques CMOS, la résistance est remplacée par un autre transistor MOS dont le comportement est complémentaire : ça symétrise mieux le comportement des portes logiques.
Opération booléenne OU.
le résultat de (a OU b) est VRAI si et seulement si plus d'une valeur boolénnes a et b sont VRAIES (une seule VRAIE, ou les deux VRAIES en même temps).
(a OU b) se note : formula_4
Réalisation d'une porte OU avec des transistors MOS.
Le circuit ci-dessus fabrique à partir des signaux d'entrée formula_5 et formula_6 un signal intermédiaire formula_7 (à l'intérieur du circuit), puis un signal de sortie formula_8, par action d'un transistor monté en porte NON.
On peut montrer que formula_9, ou, noté autrement, formula_10. Comme formula_8 est la négation de formula_7 et que la double négation revient à une copie en logique binaire, formula_13.
Exercice : dessiner le schéma d'une porte "OU NON", réalisée à l'aide de transistors MOS canal N et de résistances. La table de vérité du "OU NON" est la suivante :
Opération booléenne ET.
le résultat de (a ET b) est VRAI si et seulement si les deux valeurs boolénnes de a et b sont VRAIES en même temps.
(a ET b) se note : formula_14 ou encore formula_15
La table de vérité faux/vrai de l'opérateur booléen ET est exactement identique à la la table de multiplication de deux chiffres binaires.
Table de vérité du ET.
autre présentation : table à deux entrées.
la table à "deux entrées" correspond point par point à la table de multiplication en binaire :
Exercice : trouver un schéma d'une porte ET réalisée à l'aide de transistors MOS canal N et de résistances.
Opération booléenne OU EXCLUSIF.
la valeur de formula_16 est VRAIE si et seulement si une seule des valeurs formula_5 ou formula_6 est VRAIE (donc l'autre est fausse, en même temps).
Équation logique du OU EXCLUSIF.
Cette opération peut se formuler comme : « a est VRAI ET b est FAUX, ou a est FAUX et B est VRAI ».
Donc l'équation logique de a OU EXCLUSIF b est : formula_21
Exercices sur les opérateurs logiques.
N.B. : le symbole formula_22 est celui de l'opération OU EXCLUSIF.
Exercice 1 :
Remplissez les cases de ce tableau de vérité :
Exercice 2 :
Montrez que formula_23 est une autre expression possible pour formula_5 OU EXCLUSIF formula_6.
Exercice 3 :
Donnez une expression logique pour l'opération "TRUC" dont la table de vérité est ci-dessous :
Montrer que l'opération "TRUC" peut aussi s'interpréter comme "a IMPLIQUE b", ou "si a est VRAI, alors b est VRAI".
Combinaisons de portes logiques.
On peut schématiser les portes logiques comme des rectangles branchés à des fils électriques. Par convention,
on place les fils de sorties des portes logiques du même côté, en général à droite quand c'est possible.
Une inscription sur le rectangle rappelle la fonction de la porte logique. 
On peut se procurer une « boîte à outils » contenant des portes logiques, par exemple en achetant des circuits intégrés logiques de la série CMOS, ou TTL. Les schémas de portes logiques ne contiennent pas les fils d'alimentation électrique qui permettent aux portes de fonctionne. Bien évidemment, quand on réalise un montage réel avec les portes logiques, il convient de bien brancher les fils d'alimentation.
Notre boîte à outils « de départ ».
Notre boîte à outil de départ contient les portes ET, OU et NON. La sortie de chaque porte est du côté arrondi du rectangle.
Exercices avec des portes logiques : quatre pour une.
Trouvez la table de vérité de la porte logique obtenue par des combinaisons ci-dessous :
Cette table de vérité permet-elle de créer une nouvelle porte pour notre « boîte à outils » ?
Exercices avec des portes logiques : OU EXCLUSIF.
Rappeler une formule logique utilisant les opérateurs ET, OU, NON, qui permet d'obtenir l'opération OU EXCLUSIF.
Câbler cette formule logique en utilisant des portes ET, OU, NON. À partir de là, on peut considérer qu'on a rajouté une porte OU EXCLUSIF à notre boîte à outils. On l'étiquettera "OUEX".
Exercices avec des portes logiques : demi-additionneur à 1 bit.
Voici une table d'addition pour le système binaire :
L'étoile en exposant, dans la case en bas à droite de la table, signifie qu'il y a une retenue : « un et un fait zéro et je retiens un ».
Voici un schéma de montage qui additionne deux bits formula_5 et formula_6 (les chiffres binaires sont des Binary digITs), calcule le bit de somme et le bit de retenue :
Peut-on associer des montages de ce genre pour faire un additionneur qui traite les deux fois 8 bits de deux octes à additionner, d'un seul coup ? Justifier le nom "demi-additionneur" de ce circuit.
Exercices avec des portes logiques : additionneur complet.
On trouve, publié dans Wikipedia, un schéma d'additionneur ; celui-ci se schématise comme ceci, avec notre convention de représentation des portes logiques :
Complétez la table de vérité de cette porte à trois entrées et deux sorties :
Vérifier que cette porte est effectivement utilisable pour additionner des mots de plusieurs bits, en en associant autant que nécessaire.
Exercices de programmation.
Recherche d'entiers pairs non divisibles par trois.
On veut la liste de tous les nombres pairs et non divisibles par trois compris entre 1 et 100. On utilisera l'opération "modulo", qui permet d'obtenir le reste de la division d'un nombre par un autre.
Soit formula_5 la proposition "le nombre formula_29 est pair". Cette proposition peut se transcrire par l'expression formula_30.
x "modulo 2" est nul, signifie que le reste de la division de x par 2 est nul.
Soit formula_6 la proposition "le nombre formula_29 n'est pas divisible par 3". On peut la transcrire par l'expression formula_33
On peut donc utiliser l'algorithme suivant pour trouver la liste des nombres pairs non divisibles par trois :
debut
 entier i
 liste l := []
 booleen a
 booleen b
 pour i dans intervalle [1,100]
 a := (x mod 2 = 0)
 b := (x mod 3 = 0)
 si a et non b alors
 l := ajout(l, x)
 fin si
 fin pour
 resultat := l
fin
Programmer cet algorithme dans un ou plusieurs langages et tester les programmes.
Recherche de nombres premiers.
Problème facile
La liste des nombres premiers inférieurs à 10 est : 2, 3, 5 et 7
Écrire un algorithme qui permet de trouver la liste des nombres premiers (c'est à dire divisibles seulement par eux-même et par 1) entre 11 et 49. Programmer l'algorithme et le tester.
Problème difficile
On donne un nombre, trouver la liste des nombres premiers plus petits que celui-ci.
Écrire un algorithme, programmer, tester.