La loi de De Morgan est la loi la plus courante en théorie des ensembles et en algèbre booléenne ainsi qu'en théorie des ensembles. Dans cet article, nous découvrirons la loi de De Morgan, la loi de De Morgan en théorie des ensembles et la loi de De Morgan en algèbre booléenne ainsi que ses preuves, tables de vérité et diagrammes de portes logiques. L’article comprend également l’exemple résolu de la loi de De Morgan et une FAQ sur la loi de De Morgan. Découvrons la loi de De Morgan.
tableau en chiffres romains 1 100
Table des matières
- Quelle est la loi de De Morgan
- La loi de De Morgan dans la théorie des ensembles
- Première loi de De Morgan
- Deuxième loi de De Morgan
- Preuve utilisant l'algèbre des ensembles
- Loi de De Morgan en algèbre booléenne
- De la formule de la loi de Morgan
- Exemples résolus sur la loi de De Morgan
- Applications logiques de la loi de De Morgan
Quelle est la loi de De Morgan
La loi de De Morgan est la loi qui donne la relation entre union, intersection et compléments dans la théorie des ensembles. En algèbre booléenne, il donne la relation entre AND, OR et les compléments de la variable, et en logique, il donne la relation entre AND, OR ou la négation de l'énoncé. Avec l’aide de la loi de De Morgan, nous pouvons optimiser divers circuits booléens impliquant des portes logiques qui nous aident à effectuer la même opération mais avec très peu d’appareils.
La loi de De Morgan dans la théorie des ensembles
La loi de De Morgan dans le théorie des ensembles définit la relation entre l'union, l'intersection et les compléments des ensembles, et est donné à la fois pour le complément de l'union et l'intersection de deux ensembles. En théorie des ensembles, il existe deux lois de De Morgan :
- Première loi de De Morgan
- Deuxième loi de De Morgan
Comprenons ces lois en détail comme ci-dessous :
Première loi de De Morgan
Premièrement, la loi de De Morgan stipule que Le complément de l’union de deux ensembles est égal à l’intersection des compléments de chaque ensemble.
Soient A et B deux ensembles, alors mathématiquement, la première loi de De Morgan est donnée comme suit :
(A ∪ B)’ = A’ ∩ B’
Où
- DANS représente l'opération Union entre ensembles,
- ∩ représente l'opération d'intersection entre les ensembles, et
- ' représente l'opération de complément sur un ensemble.
On l'appelle aussi La loi de l’union de De Morgan.
Détailler la preuve de la loi de De Morgan
| Étape | Explication |
|---|---|
| Étape 1 : Énoncez la loi | La loi de De Morgan comprend deux parties : ¬(A ∪ B) = ¬A ∩ ¬B et ¬(A ∩ B) = ¬A ∪ ¬B. |
| Étape 2 : Choisissez un élément | Montrons ¬(A ∪ B) = ¬A ∩ ¬B. Supposons un élément x qui n'est pas dans A ∪ B. |
| Étape 3 : Comprendre l'hypothèse | Si x n’est pas dans A ∪ B, alors x n’est ni dans A ni dans B. |
| Étape 4 : Appliquer la définition | Par la définition du complément, si x n'est ni dans A ni dans B, alors x est dans ¬A et dans ¬B. |
| Étape 5 : Conclure la preuve | Puisque x est à la fois dans ¬A et ¬B, x est dans ¬A ∩ ¬B. Ainsi, nous avons montré ¬(A ∪ B) = ¬A ∩ ¬B. |
Preuve utilisant l'algèbre des ensembles
Nous devons prouver que (A ∪ B)’ = A’ ∩ B’
Soit X = (A ∪ B)’ et Y = A’ ∩ B’
Soit p n'importe quel élément de X, alors p ∈ X ⇒ p ∈ (A ∪ B)'
⇒ p ∉ (UNE ∪ B)
⇒ p ∉ A ou p ∉ B
⇒ p ∈ A’ et p ∈ B’
⇒ p ∈ A’ ∩ B’
⇒ p ∈ Oui
∴X ⊂ Oui. . . (Yo)
Encore une fois, soit q n’importe quel élément de Y, alors q ∈ Y ⇒ q ∈ A’ ∩ B’
⇒ q ∈ A’ et q ∈ B’
⇒ q ∉ A ou q ∉ B
⇒ q ∉ (UNE ∪ B)
⇒ q ∈ (A ∪ B)’
⇒ q ∈X
∴Y ⊂X. . . (ii)
De (i) et (ii) X = Y
(A ∪ B)’ = A’ ∩ B’
Lire aussi – Preuve des lois de De-Morgan en algèbre booléenne
Preuve à l'aide du diagramme de Venn
Diagramme de Venn pour (A ∪ B)'
Diagramme de Venn pour A’ ∩ B’
À partir des deux diagrammes, nous pouvons clairement dire :
(A ∪ B)’ = A’ ∩ B’
C’est la première loi de De Morgan.
Deuxième loi de De Morgan
Deuxièmement, la loi de De Morgan stipule que Le complément d'intersection de deux ensembles est égal à l'union des compléments de chaque ensemble.
Soient A et B deux ensembles, alors mathématiquement, la première loi de De Morgan est donnée comme suit :
(A ∩ B)’ = A’ ∪ B’
Où
- DANS représente l'opération Union entre ensembles,
- ∩ représente l'opération d'intersection entre les ensembles, et
- ' représente l'opération de complément sur un ensemble.
On l'appelle aussi Loi d'intersection de De Morgan .
Preuve utilisant l'algèbre des ensembles
Deuxième loi de De Morgan : (A ∩ B)’ = A’ ∪ B’
Soit X = (A ∩ B)’ et Y = A’ ∪ B’
Soit p n'importe quel élément de X, alors p ∈ X ⇒ p ∈ (A ∩ B)'
⇒ p ∉ (UNE ∩ B)
⇒ p ∉ A et p ∉ B
⇒ p ∈ A’ ou p ∈ B’
⇒ p ∈ A’ ∪ B’
⇒ p ∈ Oui
∴ X ⊂ Oui ————–(i)
Encore une fois, soit q n'importe quel élément de Y, alors q ∈ Y ⇒ q ∈ A' ∪ B'
⇒ q ∈ A’ ou q ∈ B’
⇒ q ∉ A et q ∉ B
⇒ q ∉ (UNE ∩ B)
⇒ q ∈ (A ∩ B)’
⇒ q ∈X
∴ Oui ⊂ X ————–(ii)
De (i) et (ii) X = Y
(A ∩ B)’ = A’ ∪ B’
Preuve à l'aide du diagramme de Venn
Diagramme de Venn pour (A ∩ B)'
Diagramme de Venn pour A’ ∪ B’
À partir des deux diagrammes, nous pouvons clairement dire
(A ∩ B)’ = A’ ∪ B’
C’est la deuxième loi de De Morgan.
Loi de De Morgan en algèbre booléenne
La loi d'algèbre booléenne de De Morgan définit la relation entre le OU, le ET et les compléments de variables, et est donnée à la fois pour le complément du ET et du OU de deux valeurs. En algèbre booléenne, il existe deux lois de De Morgan :
- Première loi de De Morgan
- Deuxième loi de De Morgan
Comprenons ces lois en détail comme ci-dessous :
Première loi de De Morgan en algèbre booléenne
Premièrement, la loi de De Morgan stipule que Le complément du OU de deux variables ou plus est égal au ET du complément de chaque variable.
Soit A et B deux variables, alors mathématiquement, la première loi de De Morgan est donnée comme suit :
(A + B)’ = A’ . B'
Où
- + représente l'opérateur OU entre variables,
- . représente l'opérateur ET entre les variables, et
- ' représente l'opération de complément sur une variable.
Premières portes logiques de la loi de De Morgan
Dans le contexte des portes logiques et de l'algèbre booléenne, la loi de De Morgan stipule que les deux circuits de porte logique, c'est-à-dire que la porte NON est ajoutée à la sortie de la porte OU et que la porte NON est ajoutée à l'entrée de la porte ET, sont équivalents. Ces deux circuits de portes logiques sont donnés comme suit :
Première table de vérité sur la loi de De Morgan
La table de vérité de la première loi de De Morgan est donnée comme suit :
| UN | B | A+B | (A + B)’ | UN' | B' | UN'. B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Deuxième loi de De Morgan en algèbre booléenne
Deuxièmement, la loi de De Morgan stipule que Le complément de ET de deux ou plusieurs variables est égal au OU du complément de chaque variable.
Soit A et B deux variables, alors mathématiquement la deuxième loi de De Morgan est donnée comme suit :
(A . B)' = A' + B'
Où
- + représente l'opérateur OU entre variables,
- . représente l'opérateur ET entre les variables, et
- ' représente l'opération de complément sur une variable.
Deuxième porte logique de la loi de De Morgan
Dans le contexte des portes logiques et de l'algèbre booléenne, la loi de De Morgan stipule que les deux circuits de porte logique, c'est-à-dire que la porte NON est ajoutée à la sortie de la porte ET et que la porte NON est ajoutée à l'entrée de la porte OU, sont équivalents. Ces deux circuits de portes logiques sont donnés comme suit :
Deuxième table de vérité sur la loi de De Morgan
La table de vérité de la deuxième loi de De Morgan est donnée comme suit :
| UN | B | UN . B | (UN B)' | UN' | B' | A' + B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
De la logique de la loi de Morgan
Dans la loi logique de De Morgan, les prépositions ci-dessous sont une tautologie :
∼ (une ∧ b) ≡ ∼ une ∨ ∼ b
∼ (une ∨ b) ≡ ∼ une ∧ ∼ b
Où,
- ∧ représente la conjonction d'énoncés,
- ∨ représente la disjonction des déclarations,
- ~ représente la négation de l'énoncé, et
- ≡ représente l’équivalence des déclarations.
De la formule de la loi de Morgan
Compilons toutes les formules de la loi de De Morgan, dans la liste suivante.
Pour la théorie des ensembles :
- (A ∪ B)’ = A’ ∩ B’
- (A ∩ B)’ = A’ ∪ B’
Pour l'algèbre booléenne :
- (A + B)’ = A’ . B'
- (A . B)' = A' + B'
Pour la logique :
- ∼ (une ∧ b) ≡ ∼ une ∨ ∼ b
- ∼ (une ∨ b) ≡ ∼ une ∧ ∼ b
Exemples résolus sur la loi de De Morgan
Problème 1 : étant donné que U = {2, 3, 7, 8, 9}, A = {2, 7} et B = {2, 3, 9}. Démontrez la deuxième loi de De Morgan.
Solution:
U = {2, 3, 7, 8, 9}, A = {2, 7} et B = {2, 3, 9}
Pour prouver : (A ∩ B)’ = A’ ∪ B’
(UNE ∩ B) = {2}
(A ∩ B)’ = U – (A ∩ B) = {2, 3, 7, 8, 9} – {2}
(A ∩ B)’ = {3, 7, 8, 9}
A' = U – A = {2, 3, 7, 8, 9} – {2, 7}
UNE' = {3, 8, 9}
B' = U – B = {2, 3, 7, 8, 9} – {2, 3, 9}
B' = {7, 8}
A' ∪ B' = {3, 8, 9} ∪ {7, 8}
A' ∪ B' = {3, 7, 8, 9}
(A ∩ B)’ = A’ ∪ B’
Problème 2 : Étant donné que U = {1, 4, 6, 8, 9}, A = {1, 9} et B = {4, 6, 9}. Démontrez la première loi de De Morgan.
Solution:
U = {1, 4, 6, 8, 9}, A = {1, 9} et B = {4, 6, 9}
Pour prouver : (A ∪ B)’ = A’ ∩ B’
(UNE ∪ B) = {1, 4, 6, 9}
(A ∪ B)’ = U – (A ∪ B) = {1, 4, 6, 8, 9} – {1, 4, 6, 9}
(UNE ∪ B)’ = {8}
A' = U – A = {1, 4, 6, 8, 9} – {1, 9}
UNE' = {4, 6, 8}
B' = U – B = {1, 4, 6, 8, 9} – {4, 6, 9}
B' = {1, 8}
A' ∩ B' = {4, 6, 8} ∩ {1, 8}
A' ∩ B' = {8}
(A ∪ B)’ = A’ ∩ B’
Donc prouvé
Problème 3 : Simplifier l’expression booléenne : Y = [(A + B).C]’
types de jointures dans rdbms
Solution:
Y = [(A + B).C]’
Application de la loi de De Morgan (A . B)’ = A’ + B’
Y = (A + B)’ + C’
En appliquant la loi de De Morgan (A + B)’ = A’. B'
Y = A'. B' + C'
Problème 4 : Simplifier l'expression booléenne : X = [(A + B)' + C]'
Solution:
X = [(A + B)’ + C]’
En appliquant la loi de De Morgan (A + B)’ = A’. B'
X = [(A + B)’]’ . C'
X = (A + B). C'
Consultez ces sources pour en savoir plus :
| Sujet pour l'interconnexion | Relatif à |
|---|---|
| Algèbre de Boole | Extrait de l'algèbre booléenne de la loi de Morgan |
| Théorie des ensembles | La loi de De Morgan dans la théorie des ensembles |
| Portes logiques | De la logique de la loi de Morgan |
| Mathématiques discrètes | De la loi de Morgan Mathématiques discrètes |
| Exemples de programmation Java | De la loi de Morgan Java |
Présentez des exemples de la loi de De Morgan
| Contexte | Exemple |
|---|---|
| Puzzles logiques | Puzzle : S'il n'est pas vrai qu'il pleut et qu'il fait froid, que pouvons-nous en déduire ? Application de la loi de De Morgan : On peut en déduire qu'il ne pleut pas ou qu'il ne fait pas froid. Cela utilise la loi de De Morgan pour simplifier la négation d’une conjonction en disjonction. |
| La programmation | Scénario : Vérifier si un nombre n'est ni positif ni pair dans un langage de programmation. Extrait de code (pseudocode) :if !(number>0 et nombre % 2 == 0)>peut être simplifié en utilisant la loi de De Morgan pourif (number <= 0 or number % 2 != 0)>. Cela démontre comment la loi de De Morgan aide à simplifier les instructions conditionnelles. |
| Preuves mathématiques | Déclaration : Montrer que le complément de l'intersection de deux ensembles A et B est égal à l'union de leurs compléments. Application de la loi de De Morgan : D’après la loi de De Morgan, (A ∩ B)’ = A’ ∪ B’. Cela montre comment la loi de De Morgan est utilisée pour simplifier les expressions dans la théorie des ensembles. |
Tiré d'exemples pratiques de la loi de Morgan
Exemple 1 : garnitures de pizza
Imaginez que vous êtes à une soirée pizza et qu’on vous dit que vous pouvez choisir n’importe quelle garniture, à l’exception des champignons et des olives ensemble.
- Utiliser la loi de De Morgan : Cela signifie que si vous ne voulez pas à la fois de champignons et d'olives (Pas (Champignons et Olives)), vous pouvez soit ne pas avoir de champignons (Pas de champignons), soit ne pas avoir d'olives (Pas d'olives) sur votre pizza. Ainsi, vous pourriez avoir une pizza avec juste des champignons, juste des olives, ou ni l'un ni l'autre !
Exemple 2 : livres de bibliothèque
Votre professeur dit que vous ne pouvez pas apporter de livres sur les sorciers ou les dragons en classe.
- Utiliser la loi de De Morgan : Cela signifie que si vous n'êtes pas autorisé à apporter des livres sur les sorciers ou les dragons (Not (Wizards or Dragons)), vous ne pouvez pas apporter de livres sur les sorciers (Not Wizards) et vous ne pouvez pas apporter de livres sur les dragons (Not Dragons). Donc, les livres sur l’espace ou les animaux sont toujours acceptables !
Exemple 3 : Jouer dehors
Ta mère dit que tu ne peux pas jouer dehors s’il pleut et qu’il fait froid en même temps.
- Utiliser la loi de De Morgan : Cela signifie que si vous ne sortez pas parce qu’il pleut et qu’il fait froid (Pas (Paining and Cold)), vous ne sortirez pas s’il pleut juste (Pas de pluie) ou s’il fait juste froid (Pas froid). Mais s’il fait beau et chaud, vous pouvez y aller !
Exemple 4 : Choisir un film
Votre ami dit qu’il ne veut pas regarder un film effrayant ou ennuyeux.
- Utiliser la loi de De Morgan : Cela signifie que si votre ami ne veut pas d'un film effrayant ou ennuyeux (Pas (Effrayant ou ennuyeux)), il ne veut pas d'un film effrayant (Pas effrayant) et il ne veut pas d'un film ennuyeux (Pas ennuyeux) . Alors, un film drôle ou passionnant serait parfait !
Applications logiques de la loi de De Morgan
| Champ d'application | Description |
|---|---|
| Raisonnement logique | Dans les énigmes ou arguments logiques, la loi de De Morgan aide à simplifier les négations complexes. Par exemple, nier Toutes les pommes sont rouges à Toutes les pommes ne sont pas rouges implique Certaines pommes ne sont pas rouges. |
| L'informatique | La loi de De Morgan est cruciale pour optimiser les instructions conditionnelles en programmation. Il permet aux programmeurs de simplifier des conditions logiques complexes, rendant le code plus efficace et plus lisible. |
| Conception de circuits électroniques | En électronique numérique, la loi de De Morgan est utilisée pour concevoir et simplifier les circuits. Par exemple, il aide à convertir les portes ET en portes OU (et vice versa) à l'aide de portes NON, facilitant ainsi la création de configurations de circuits plus efficaces. |
De la loi de Morgan – FAQ
Énoncez le premier énoncé de loi de De Morgan en théorie des ensembles.
La première loi de De Morgan dans la théorie des ensembles stipule que le complément de l’union de deux ensembles est égal à l’intersection de leurs compléments individuels.
Énoncez la deuxième déclaration de loi de De Morgan en algèbre booléenne.
La deuxième loi de De Morgan en algèbre booléenne stipule que le complément de ET de deux variables ou plus est égal au OU du complément de chaque variable.
Écrivez la formule de la loi de De Morgan en théorie des ensembles.
La formule de la loi de De Morgan en théorie des ensembles :
(i) (A ∪ B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ ∪ B’
Écrivez la formule de la loi de De Morgan en algèbre booléenne.
La formule de la loi de De Morgan en algèbre booléenne :
(i) (A + B)’ = A’ . B'
(ii) (A . B)’ = A’ + B’
Écrivez quelques applications de la loi de De Morgan.
Certaines des applications de la loi de De Morgan consistent à minimiser l’expression booléenne complexe et à la simplifier.
Comment prouver la loi de De Morgan ?
La loi de De Morgan dans la théorie des ensembles peut être prouvée par les diagrammes de Venn et la loi de De Morgan dans l'algèbre booléenne peut être prouvée par des tables de vérité.