# Logique Combinatoire **Accueil : [[Logique Combinatoire]]** >*Objectif : découvrir les bases de la logique combinatoire au travers d'un exemple simple* >[!tip] Conseil >1. Chaque vidéo présente une ou plusieurs notions importantes. Il est conseillé de les regarder attentivement et en mode plein écran pour bien comprendre les idées. >2. Les parties textuelles apportent des compléments **nécessaires** à la formation. --- ## Introduction et premières fonctions logiques Dans cette première vidéo, Nous allons à la boulangerie ce qui nous permet d'introduire la logique combinatoire. Nous y voyons aussi les 2 premières fonctions/portes logiques (OUI et NON) ainsi que les tables (ou tableaux) de vérité. <div style="position: relative; width: 100%; padding-bottom: 56.25%; height: 0;"> <iframe style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;" src="https://www.youtube.com/embed/k-rdkvSYOIs?si=xy0579yadZZdj9cL" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </div> ### Variable Logique > [!info] Définition > une variable logique est une **donnée binaire** n'ayant que deux états possibles : > - 1 ou 0 > - VRAI ou FAUX > - Signal ou Pas de Signal > - ... --- ### Fonctions Logiques > [!info] Définition > Une **fonction logique** est une fonction qui admet une ou plusieurs **variables logiques en entrée** et qui retourne **une donnée binaire en sortie**. On parle aussi d'**opérateur logique** ou de **porte logique**. #### Fonctions Logiques de bases Voici la liste des fonctions de base à connaitre | Nom de l'opération | Symbole | Comportement | | ------------------ | ---------------------- | ----------------------------------------------- | | OU | $A + B$ | Sortie à 1 si au moins une des entrées est à 1 | | ET | $A \cdot B$ | Sortie à 1 si toutes les entrées sont à 1 | | OU EXCLUSIF | $A \oplus B$ | Sortie à 1 si seulement une des entrées est à 1 | | NON | $\overline{A}$ | Sortie à 1 si l’entrée est à 0 | | NON OU | $\overline{A + B}$ | Sortie à 0 si au moins une des entrées est à 1 | | NON ET | $\overline{A \cdot B}$ | Sortie à 0 si toutes les entrées sont à 1 | #### Expressions Algébriques Avec plusieurs variables logiques et plusieurs fonctions logiques il est possible de faire des expressions logiques plus complexes. >[!Example] Exemple $S= \overline{A} + B.C + \overline{A}.C$ --- ## La fonction logique *"ET"* Maintenant que nous sommes devant la boulangerie, nous voulons acheter des croissants ! <div style="position: relative; width: 100%; padding-bottom: 56.25%; height: 0;"> <iframe style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;" src="https://www.youtube.com/embed/dIe1_iXC0iw?si=OXnzOtGhTWXU3RLI" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </div> --- ## La fonction logique *"OU"* Pourquoi s'arrêter aux croissants ?... Regardons si nous pouvons acheter des viennoiseries ! ***Attention :*** *On relance la guerre des régions ! 🙂* <div style="position: relative; width: 100%; padding-bottom: 56.25%; height: 0;"> <iframe style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;"src="https://www.youtube.com/embed/58CYTjNhly4?si=ebxyISwVLmp2uCKS" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </div> --- ## Les tables de vérité ### Définition > [!info] Définition > Une table de vérité est un tableau permettant de décrire toutes les possibilités de sorties en fonction des entrées Si on a **n variables logiques d'entrées**, nous avons **$2^n$ combinaisons d'entrée**. >[!tip] >Nous vous conseillons d'utiliser le code binaire pour écrire toutes les combinaisons d'entrée possibles. >[!Example] Exemple > >| A | B | C | ... | S | >| :-: | :-: | :-: | :-: | :-: | >| 0 | 0 | 0 | | | >| 0 | 0 | 1 | | | >| 0 | 1 | 0 | | | >| 0 | 1 | 1 | | | >| 1 | 0 | 0 | | | >| 1 | 0 | 1 | | | >| 1 | 1 | 0 | | | >| 1 | 1 | 1 | | | ### Tables de vérité à connaitre #### Fonction **NON** : $\overline{A}$ | A | $\overline{A}$ | | :-: | :------------: | | 0 | 1 | | 1 | 0 | --- #### Fonction **OUI** (identité) | A | A | |:--:|:--:| | 0 | 0 | | 1 | 1 | --- #### Fonction **ET** : $A \cdot B$ | A | B | $A \cdot B$ | |:--:|:--:|:---------:| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | --- #### Fonction **OU** : $A + B$ | A | B | $A + B$ | |:--:|:--:|:------:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | --- #### Fonction **NON ET** : $\overline{A \cdot B}$ | A | B | $\overline{A \cdot B}$ | |:--:|:--:|:--------------------:| | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | --- #### Fonction **NON OU** : $\overline{A + B}$ | A | B | $\overline{A + B}$ | |:--:|:--:|:----------------:| | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 0 | --- #### Fonction **OU Exclusif** : $A \oplus B$ | A | B | $A \oplus B$ | |:--:|:--:|:-----------:| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | --- ## Créer une table de vérité, en déduire l'expression logique Dans cette nouvelle vidéo, nous partons d'une situation pour en déduire une table de vérité et nous les règles qui permettent de déterminer l'expression logique de cette table de vérité. <div style="position: relative; width: 100%; padding-bottom: 56.25%; height: 0;"> <iframe style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;" src="https://www.youtube.com/embed/m9PANSr75gY?si=vivwBX2ytBd0tYtq" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </div> >[!info] Règles > Pour passer de la table de vérité à l'expression logique : > 1. On repère toutes les lignes de la table où la sortie est égale à 1. > 2. On combine les variables concernées avec le ET logique (si la variable vaut 0, on prend son inverse). > 3. On combine les fonctions logiques obtenues avec le OU logique. >[!example] Exemple >| A | B | S | >|:-:|:-:|:--:| >| ***0*** | ***0*** | ***1*** | >| 0 | 1 | 0 | >| ***1*** | ***0*** | ***1*** | >| 1 | 1 | 0 | >Cette table de vérité donne : $S = \overline{A} \cdot \overline{B} + A \cdot \overline{B}$ >[!note] Remarque > Vous verrez dans la partie approfondissement comment déterminer la table de vérité d'une expression logique : [[02_Approfondisssement Logique Combinatoire]] --- ## Simplifier une expression logique à l'aide des *Lois de composition* Maintenant que nous avons obtenu une expression logique de notre situation, nous allons voir, à l'aide des lois de composition s'il est possible de la simplifier. <div style="position: relative; width: 100%; padding-bottom: 56.25%; height: 0;"> <iframe style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;" src="https://www.youtube.com/embed/KYIQp1moI7U?si=EcHwAzv4qAD-ixKj" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </div> ### Définition >[!info] Définition >Les lois de composition sont des règles logiques qui permettent de simplifier l'écriture des expressions algébriques ### Les lois de composition >[!note] Commutativité > $A + B = B + A$ > > $A \cdot B = B \cdot A$ >[!note] Associativité > $(A + B) + C = A + (B + C)$ > > $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ >[!note] Distributivité > $A \cdot (B + C) = A \cdot B + A \cdot C$ > > $A + (B \cdot C) = (A + B) \cdot (A + C)$ >[!note] Idempotence > $A + A = A$ > > $A \cdot A = A$ >[!note] Identité > $A + 0 = A$ > > $A \cdot 1 = A$ >[!note] Nullité > $A + 1 = 1$ > > $A \cdot 0 = 0$ >[!note] Inversion > $A + \overline{A} = 1$ > > $A \cdot \overline{A} = 0$ >[!note] Absorption > $A \cdot (A + B) = A$ > > $A + (A \cdot B) = A$ >[!note] Loi de Morgan > $\overline{A + B} = \overline{A} \cdot \overline{B}$ > > $\overline{A \cdot B} = \overline{A} + \overline{B}$ >[!note] Loi d'involution > $\overline{\overline{A}} = A$ --- ## Utiliser un tableau de Karnaugh pour simplifier une expression logique Dans cette vidéo, nous découvrirons **les tableaux de Karnaugh** qui permettent de simplifier rapidement une expression logique. C'est rapide, facile ***MAIS*** attention à bien suivre chaque étape et de respecter toutes les règles annoncées ! <div style="position: relative; width: 100%; padding-bottom: 56.25%; height: 0;"> <iframe style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;" src="https://www.youtube.com/embed/q13laB4w3Mk?si=qP5Pwxh-3jGuv79O" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </div> >[!note] Remarque > Vous verrez dans la partie approfondissement comment utiliser les tableaux de Karnaugh en partant de l'expression logique et non de la table de vérité : [[02_Approfondisssement Logique Combinatoire]] ### Tableau de Karnaugh > [!definition] Tableau de Karnaugh > Un **tableau de Karnaugh** est une représentation graphique d’une **table de vérité** utilisée pour simplifier les **expressions logiques**. > Il s’agit d’un tableau à deux dimensions dans lequel les variables ou combinaisons des variables d’entrée sont placées en entête de ligne et colonne selon un ordre de **code Gray**, de manière à ce que deux cases adjacentes ne diffèrent que d’un seul bit. > > Chaque case correspond à une combinaison unique des variables et contient la **valeur de sortie** de la fonction pour cette combinaison. > > En regroupant les cases où la sortie est 1, on peut **identifier des simplifications** logiques selon les lois de l’algèbre de Boole. > >**Le résultat est une forme disjonctive** (somme de produit) **la plus simple possible de l'expression logique de départ** --- ### Les règles de construction 1. On crée un table de $2^n$ cases (n étant le nombre de variable d'entrée) 2. En entête de ligne et de colonne, nous mettons plaçons toutes les combinaisons d'états des variables d'entrée en respectant le Code Gray (un changement d'état en passant d'une case à l'autre) >[!Example] Exemple avec 4 variables d'entrée (A, B, C et D) >| | $A.B$ | $A.\overline{B}$ | $\overline{A}.\overline{B}$ | $\overline{A}.B$ | >| :-------------------------: | :---: | :--------------: | :-------------------------: | :--------------: | >| $C.D$ | | | | | >| $C.\overline{D}$ | | | | | >| $\overline{C}.\overline{D}$ | | | | | >| $\overline{C}.D$ | | | | | 3. On remplit chaque case avec la valeur de sortie correspondant à la combinaison des variables d'entrée 4. On regroupe les 1 en respectant les règles suivantes : 1. Le regroupement doit être rectangulaire 2. Le nombre de 1 doit être une puissance de 2 (1,2,4,8,16) 3. Faire les plus grands regroupements possibles : On essaie 16 puis 8 puis 4 puis 2 et enfin 1. 4. Un 1 peut appartenir à plusieurs regroupements 5. On cherche les regroupements tant qu'au moins un 1 n'appartient à aucun groupement 6. Une fois que tous les 1 sont au moins dans un regroupement, on reprend chaque regroupement et on vérifie qu'il existe au moins un 1 qui n'appartient qu'au regroupement étudié. *(si tous les 1 appartiennent à d'autres regroupements, c'est que ce regroupement ne sert à rien)* 7. On en déduit l'expression logique simplifiée en appliquant les règles suivantes : 1. Pour chaque regroupement, on ne retient que les variables dont l'état ne change pas et on réalise la **multiplication logique** des variables ainsi obtenues 2. On effectue la **somme logique** de toutes parties d'expression trouvées --- >[!note] Dans la suite du cours > Dans la page approfondissement, nous utiliserons tout ce que nous venons de voir pour > 1. faire la table de vérité d'une expression logique > 2. simplifier une expression logique à l'aide du tableau de Karnaugh SANS faire la table de vérité. --- **Approfondissement : [[02_Approfondisssement Logique Combinatoire]]** ---