La llei de De Morgan és la llei més comuna en la teoria de conjunts i l'àlgebra de Boole, així com en la teoria de conjunts. En aquest article, coneixerem la llei de De Morgan, la llei de De Morgan en teoria de conjunts i la llei de De Morgan en àlgebra booleana juntament amb les seves demostracions, taules de veritat i diagrames de portes lògiques. L'article també inclou l'exemple resolt de la llei de De Morgan i les preguntes freqüents sobre la llei de De Morgan. Coneixem la llei de De Morgan.
Taula de contingut
- Què és la llei de De Morgan
- Llei de De Morgan en la teoria de conjunts
- Primera llei de De Morgan
- Second De Morgan’s Law
- Demostració utilitzant àlgebra de conjunts
- Llei de De Morgan en àlgebra de Boole
- De Morgan’s Law Formula
- Exemples resolts sobre la llei de De Morgan
- Aplicacions lògiques de la llei de De Morgan
Què és la llei de De Morgan
La llei de De Morgan és la llei que dóna la relació entre unió, intersecció i complements en la teoria de conjunts. En l'àlgebra booleana, dóna la relació entre AND, OR i complements de la variable, i en lògica, dóna la relació entre AND, OR o Negació de l'enunciat. Amb l'ajuda de la Llei de De Morgan, podem optimitzar diversos circuits booleans que impliquen portes lògiques que ens ajuden a realitzar la mateixa operació però amb molt pocs aparells.
Llei de De Morgan en la teoria de conjunts
La llei de De Morgan en el teoria de conjunts defineix la relació entre la unió, la intersecció i els complements dels conjunts, i es dóna tant per al complement d'unió com per a la intersecció de dos conjunts. En la teoria de conjunts, hi ha dues lleis de De Morgan que són:
- Primera llei de De Morgan
- Second De Morgan’s Law
Entenem aquestes lleis en detall com a continuació:
Primera llei de De Morgan
Primer ho diu la llei de De Morgan El complement de la unió de dos conjunts és igual a la intersecció dels complements de cada conjunt.
Siguin A i B dos conjunts, aleshores matemàticament la primera llei de De Morgan es dóna com:
(A ∪ B)’ = A’ ∩ B’
On
- EN representa l'operació de la Unió entre conjunts,
- ∩ representa l'operació d'intersecció entre conjunts, i
- ‘ representa l'operació del complement en un conjunt.
També s'anomena Llei d'unió de De Morgan.
Detalleu la prova de la llei de De Morgan
| Pas | Explicació |
|---|---|
| Pas 1: declara la llei | La llei de De Morgan inclou dues parts: ¬(A ∪ B) = ¬A ∩ ¬B i ¬(A ∩ B) = ¬A ∪ ¬B. |
| Pas 2: trieu un element | Demostrem ¬(A ∪ B) = ¬A ∩ ¬B. Suposem un element x que no està en A ∪ B. |
| Pas 3: entendre l'assumpció | Si x no està en A ∪ B, aleshores x no és ni en A ni en B. |
| Pas 4: aplicar la definició | Per la definició de complement, si x no està en A i no en B, aleshores x està en ¬A i en ¬B. |
| Pas 5: conclou la prova | Com que x és a ¬A i ¬B, x és a ¬A ∩ ¬B. Així, hem mostrat ¬(A ∪ B) = ¬A ∩ ¬B. |
Demostració utilitzant àlgebra de conjunts
Hem de demostrar, (A ∪ B)’ = A’ ∩ B’
Sigui X = (A ∪ B)’ i Y = A’ ∩ B’
Sigui p qualsevol element de X, aleshores p ∈ X ⇒ p ∈ (A ∪ B)’
⇒ p ∉ (A ∪ B)
⇒ p ∉ A o p ∉ B
⇒ p ∈ A’ i p ∈ B’
⇒ p ∈ A’ ∩ B’
⇒ p ∈ I
∴ X ⊂ Y . . . (i)
De nou, siguem q qualsevol element de Y, aleshores q ∈ Y ⇒ q ∈ A’ ∩ B’
⇒ q ∈ A’ i q ∈ B’
⇒ q ∉ A o q ∉ B
⇒ q ∉ (A ∪ B)
⇒ q ∈ (A ∪ B)’
⇒ q ∈ X
∴ I ⊂ X . . . (ii)
De (i) i (ii) X = Y
(A ∪ B)’ = A’ ∩ B’
Llegeix també - Prova de les lleis de De-Morgan en àlgebra booleana
Prova utilitzant el diagrama de Venn
Diagrama de Venn per a (A ∪ B)’
Diagrama de Venn per a A’ ∩ B’
A partir dels dos diagrames, podem dir clarament:
(A ∪ B)’ = A’ ∩ B’
Aquesta és la primera llei de De Morgan.
Second De Morgan’s Law
La segona llei de De Morgan ho diu El complement d'intersecció de dos conjunts és igual a la unió dels complements de cada conjunt.
Siguin A i B dos conjunts, aleshores matemàticament la primera llei de De Morgan es dóna com:
(A ∩ B)’ = A’ ∪ B’
On
- EN representa l'operació de la Unió entre conjunts,
- ∩ representa l'operació d'intersecció entre conjunts, i
- ‘ representa l'operació del complement en un conjunt.
També s'anomena Llei de la intersecció de De Morgan .
Demostració utilitzant àlgebra de conjunts
Segona llei de De Morgan: (A ∩ B)’ = A’ ∪ B’
Sigui X = (A ∩ B)’ i Y = A’ ∪ B’
Sigui p qualsevol element de X, aleshores p ∈ X ⇒ p ∈ (A ∩ B)’
⇒ p ∉ (A ∩ B)
⇒ p ∉ A i p ∉ B
⇒ p ∈ A’ o p ∈ B’
⇒ p ∈ A’ ∪ B’
⇒ p ∈ I
∴ X ⊂ Y ————–(i)
De nou, siguem q qualsevol element de Y, aleshores q ∈ Y ⇒ q ∈ A’ ∪ B’
⇒ q ∈ A’ o q ∈ B’
⇒ q ∉ A i q ∉ B
⇒ q ∉ (A ∩ B)
⇒ q ∈ (A ∩ B)’
⇒ q ∈ X
∴ I ⊂ X ————–(ii)
De (i) i (ii) X = Y
(A ∩ B)’ = A’ ∪ B’
Prova utilitzant el diagrama de Venn
Diagrama de Venn per a (A ∩ B)’
Diagrama de Venn per a A’ ∪ B’
A partir dels dos diagrames, podem dir clarament
(A ∩ B)’ = A’ ∪ B’
Aquesta és la Segona Llei de De Morgan.
Llei de De Morgan en àlgebra de Boole
L'àlgebra booleana de la llei de De Morgan defineix la relació entre l'OR, I i els complements de variables, i es dóna tant per al complement de I com per a l'OR de dos valors. A l'àlgebra de Boole hi ha dues lleis de De Morgan que són:
- Primera llei de De Morgan
- Second De Morgan’s Law
Entenem aquestes lleis en detall com a continuació:
Primera llei de De Morgan en àlgebra de Boole
Primer ho diu la llei de De Morgan El complement de OR de dues o més variables és igual al AND del complement de cada variable.
Siguin A i B dues variables, aleshores matemàticament la primera llei de De Morgan es dóna com:
(A + B)’ = A’ . B'
On
- + representa l'operador OR entre variables,
- . representa l'operador AND entre variables, i
- ‘ representa l'operació del complement sobre la variable.
Primera llei de De Morgan, portes lògiques
En el context de les portes lògiques i l'àlgebra de Boole, la llei de De Morgan estableix que els dos circuits de la porta lògica, és a dir, la porta NOT s'afegeix a la sortida de la porta OR i la porta NOT s'afegeix a l'entrada de la porta AND, són equivalents. Aquests dos circuits de porta lògica es donen de la següent manera:
Primera taula de veritat de la llei de De Morgan
La taula de veritat de la primera llei de De Morgan es dóna de la següent manera:
patró de disseny singleton java
| A | B | A + B | (A + B)' | A' | B' | A’. 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 |
Segona llei de De Morgan en àlgebra de Boole
La segona llei de De Morgan ho diu El complement de AND de dues o més variables és igual a l'OR del complement de cada variable.
Siguin A i B dues variables, aleshores matemàticament la Segona Llei de De Morgan es dóna com:
(A. B)’ = A’ + B’
On
- + representa l'operador OR entre variables,
- . representa l'operador AND entre variables, i
- ‘ representa l'operació del complement sobre la variable.
Portes lògiques de la segona llei de De Morgan
En el context de les portes lògiques i l'àlgebra de Boole, la llei de De Morgan estableix que els dos circuits de la porta lògica, és a dir, la porta NOT s'afegeix a la sortida de la porta AND i la porta NOT s'afegeix a l'entrada de la porta OR, són equivalents. Aquests dos circuits de porta lògica es donen de la següent manera:
Taula de veritat de la segona llei de De Morgan
La taula de veritat de la segona llei de De Morgan es dóna de la següent manera:
| A | B | A . B | (A.B)' | A' | 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 Morgan's Law Logic
A la llei de De Morgan per a la lògica, les preposicions següents són tautologia:
∼ (a ∧ b) ≡ ∼ a ∨ ∼ b
∼ (a ∨ b) ≡ ∼ a ∧ ∼ b
On,
- ∧ representa la conjunció d'enunciats,
- ∨ representa la disjunció d'afirmacions,
- ~ representa la negació de l'enunciat, i
- ≡ representa l'equivalència d'enunciats.
De Morgan’s Law Formula
Recopilem totes les fórmules de la Llei de De Morgan, a la llista següent.
Per a la teoria de conjunts:
- (A ∪ B)’ = A’ ∩ B’
- (A ∩ B)’ = A’ ∪ B’
Per a l'àlgebra de Boole:
- (A + B)’ = A’ . B'
- (A. B)’ = A’ + B’
Per a la lògica:
- ∼ (a ∧ b) ≡ ∼ a ∨ ∼ b
- ∼ (a ∨ b) ≡ ∼ a ∧ ∼ b
Exemples resolts sobre la llei de De Morgan
Problema 1: donat que U = {2, 3, 7, 8, 9}, A = {2, 7} i B = {2, 3, 9}. Proveu la segona llei de De Morgan.
Solució:
U = {2, 3, 7, 8, 9}, A = {2, 7} i B = {2, 3, 9}
Per demostrar: (A ∩ B)’ = A’ ∪ B’
(A ∩ 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}
A’ = {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’
Problema 2: Donat que U = {1, 4, 6, 8, 9}, A = {1, 9} i B = {4, 6, 9}. Proveu la primera llei de De Morgan.
Solució:
U = {1, 4, 6, 8, 9}, A = {1, 9} i B = {4, 6, 9}
Per demostrar: (A ∪ B)’ = A’ ∩ B’
(A ∪ B) = {1, 4, 6, 9}
(A ∪ B)’ = U – (A ∪ B) = {1, 4, 6, 8, 9} – {1, 4, 6, 9}
(A ∪ B)’ = {8}
A’ = U – A = {1, 4, 6, 8, 9} – {1, 9}
A’ = {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’
Per tant, demostrat
Problema 3: Simplifica l'expressió booleana: Y = [(A + B).C]’
Solució:
I = [(A + B).C]’
Aplicant la llei de De Morgan (A. B)’ = A’ + B’
I = (A + B)' + C'
Aplicant la llei de De Morgan (A + B)’ = A’. B'
I = A'. B' + C'
Problema 4: Simplifica l'expressió booleana: X = [(A + B)’ + C]’
Solució:
X = [(A + B)’ + C]’
Aplicant la llei de De Morgan (A + B)’ = A’. B'
X = [(A + B)’]’ . C'
X = (A + B). C'
Consulteu aquestes fonts per obtenir més informació:
| Tema per a l'enllaç | Relacionat amb |
|---|---|
| Àlgebra de Boole | De Morgan's Law Boolean Algebra |
| Teoria de conjunts | Llei de De Morgan en la teoria de conjunts |
| Portes lògiques | De Morgan's Law Logic |
| Matemàtiques discretes | De Morgan's Law Discrete Math |
| Exemples de programació Java | De Morgan's Law Java |
Mostra exemples de la llei de De Morgan
| Context | Exemple |
|---|---|
| Trencaclosques de lògica | Trencaclosques : Si no és cert que plou i fa fred, què podem inferir? Aplicació de la llei de De Morgan : Podem inferir que no plou o no fa fred. Això utilitza la llei de De Morgan per simplificar la negació d'una conjunció en una disjunció. |
| Programació | Escenari : Comprovar si un número no és positiu ni tan sols en un llenguatge de programació. Fragment de codi (pseudocodi) :if !(number>0 i nombre % 2 == 0)>es pot simplificar mitjançant la llei de De Morganif (number <= 0 or number % 2 != 0)>. Això demostra com la llei de De Morgan ajuda a simplificar les declaracions condicionals. |
| Proves matemàtiques | Declaració : Demostreu que el complement de la intersecció de dos conjunts A i B és igual a la unió dels seus complements. Aplicació de la llei de De Morgan : Segons la llei de De Morgan, (A ∩ B)’ = A’ ∪ B’. Això mostra com s'utilitza la llei de De Morgan per simplificar expressions en la teoria de conjunts. |
De Morgan's Law Practical Examples
Exemple 1: cobertura de pizza
Imagineu-vos que esteu a una festa de pizza i us diuen que podeu triar qualsevol complement, excepte els bolets i les olives junts.
- Utilitzant la llei de De Morgan : Això vol dir que si no voleu tant bolets com olives (No (Bolets i olives)), no podeu tenir bolets (No bolets) o no tenir olives (No olives) a la vostra pizza. Per tant, podríeu prendre una pizza només amb bolets, només olives, o cap de les dues coses!
Exemple 2: Llibres de la biblioteca
El teu professor diu que no pots portar llibres sobre bruixots o dracs a l'aula.
- Utilitzant la llei de De Morgan : Això vol dir que si no se't permeten llibres sobre mags o dracs (No (Magos o Dracs)), no pots portar llibres sobre mags (No Mags) i no pots portar llibres sobre dracs (No Dracs). Per tant, els llibres sobre l'espai o els animals encara estan bé!
Exemple 3: Jugar a l'exterior
La teva mare diu que no pots jugar fora si plou i fa fred alhora.
- Utilitzant la llei de De Morgan : Això vol dir que si no sortiu perquè plou i fa fred (Not (Raining and Cold)), no sortiríeu si només plou (Not Raining) o només fred (Not Cold). Però si fa sol i calor, ja estàs a punt!
Exemple 4: escollir una pel·lícula
El teu amic diu que no vol veure una pel·lícula que fa por o avorrida.
- Utilitzant la llei de De Morgan : Això vol dir que si el teu amic no vol una pel·lícula que faci por o avorrida (No (Sery or Boring)), no vol una pel·lícula de por (Not Scary) i no vol una pel·lícula avorrida (Not Boring) . Per tant, una pel·lícula divertida o emocionant seria perfecta!
Aplicacions lògiques de la llei de De Morgan
| Àrea d'aplicació | Descripció |
|---|---|
| Raonament lògic | En trencaclosques o arguments lògics, la Llei de De Morgan ajuda a simplificar les negacions complexes. Per exemple, negar Totes les pomes són vermelles a No totes les pomes són vermelles implica que Algunes pomes no són vermelles. |
| Ciències de la Computació | La llei de De Morgan és crucial per optimitzar les declaracions condicionals a la programació. Permet als programadors simplificar condicions lògiques complexes, fent que el codi sigui més eficient i llegible. |
| Disseny de circuits electrònics | En electrònica digital, la llei de De Morgan s'utilitza per dissenyar i simplificar circuits. Per exemple, ajuda a convertir les portes AND en portes OR (i viceversa) utilitzant portes NOT, facilitant la creació de dissenys de circuits més eficients. |
De Morgan's Law – FAQs
State la primera declaració de llei de De Morgan en teoria de conjunts.
La primera llei de De Morgan en teoria de conjunts estableix que el complement d'unió de dos conjunts és igual a la intersecció dels seus complements individuals.
State la segona llei de De Morgan en àlgebra de Boole.
La segona llei de De Morgan en àlgebra booleana diu que el complement de AND de dues o més variables és igual a l'OR del complement de cada variable.
Escriu la fórmula de la llei de De Morgan en la teoria de conjunts.
La fórmula de la llei de De Morgan en la teoria de conjunts:
(i) (A ∪ B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ ∪ B’
Escriu la fórmula de la llei de De Morgan en àlgebra de Boole.
La fórmula de la llei de De Morgan en àlgebra de Boole:
(i) (A + B)’ = A’ . B'
(ii) (A. B)’ = A’ + B’
Escriu algunes aplicacions de la llei de De Morgan.
Algunes de les aplicacions de la llei de De Morgan són minimitzar la complexa expressió booleana i simplement-la.
Com demostrar la llei de De Morgan?
La llei de De Morgan a la teoria de conjunts es pot demostrar amb els diagrames de Venn i la llei de De Morgan a l'àlgebra de Boole es pot demostrar amb taules de veritat.