La legge di De Morgan è la legge più comune nella teoria degli insiemi, nell'algebra booleana e nella teoria degli insiemi. In questo articolo impareremo la legge di De Morgan, la legge di De Morgan nella teoria degli insiemi e la legge di De Morgan nell'algebra booleana insieme alle sue dimostrazioni, tabelle di verità e diagrammi di porte logiche. L'articolo include anche l'esempio risolto della legge di De Morgan e le domande frequenti sulla legge di De Morgan. Cerchiamo di conoscere la legge di De Morgan.
Tabella dei contenuti
- Cos'è la legge di De Morgan
- La legge di De Morgan nella teoria degli insiemi
- Prima legge di De Morgan
- Seconda legge di De Morgan
- Dimostrazione utilizzando l'algebra degli insiemi
- Legge di De Morgan nell'algebra booleana
- Dalla formula della legge di Morgan
- Esempi risolti sulla legge di De Morgan
- Applicazioni logiche della legge di De Morgan
Cos'è la legge di De Morgan
La legge di De Morgan è la legge che fornisce la relazione tra unione, intersezione e complementi nella teoria degli insiemi. Nell'algebra booleana fornisce la relazione tra AND, OR e i complementi della variabile e, in logica, fornisce la relazione tra AND, OR o negazione dell'affermazione. Con l’aiuto della Legge di De Morgan possiamo ottimizzare diversi circuiti booleani che coinvolgono porte logiche che ci aiutano a compiere la stessa operazione ma con pochissimi apparati.
La legge di De Morgan nella teoria degli insiemi
La legge di De Morgan nel insiemistica definisce la relazione tra l'unione, l'intersezione e i complementi degli insiemi ed è dato sia per il complemento dell'unione che per l'intersezione di due insiemi. Nella teoria degli insiemi, ci sono due leggi di De Morgan che sono:
- Prima legge di De Morgan
- Seconda legge di De Morgan
Comprendiamo queste leggi in dettaglio come di seguito:
Prima legge di De Morgan
Lo afferma innanzitutto la legge di De Morgan Il complementare dell'unione di due insiemi è uguale all'intersezione dei complementari di ciascun insieme.
Siano A e B due insiemi, allora matematicamente la Prima Legge di De Morgan è data come:
(A ∪ B)’ = A’ ∩ B’
Dove
- IN rappresenta l'operazione di unione tra insiemi,
- ∩ rappresenta l'operazione di intersezione tra insiemi e
- ' rappresenta l'operazione di complemento su un insieme.
È anche chiamato Legge dell’Unione di De Morgan.
Dettaglia la dimostrazione della legge di De Morgan
| Fare un passo | Spiegazione |
|---|---|
| Passaggio 1: dichiarare la legge | La legge di De Morgan comprende due parti: ¬(A ∪ B) = ¬A ∩ ¬B e ¬(A ∩ B) = ¬A ∪ ¬B. |
| Passaggio 2: scegli un elemento | Dimostriamo ¬(A ∪ B) = ¬A ∩ ¬B. Assumiamo un elemento x che non sia in A ∪ B. |
| Passaggio 3: comprendere il presupposto | Se x non è in A ∪ B, allora x non è né in A né in B. |
| Passaggio 4: applicare la definizione | Per la definizione di complemento, se x non è in A e non in B, allora x è in ¬A e in ¬B. |
| Passaggio 5: concludere la dimostrazione | Poiché x è sia in ¬A che in ¬B, x è in ¬A ∩ ¬B. Quindi abbiamo dimostrato che ¬(A ∪ B) = ¬A ∩ ¬B. |
Dimostrazione utilizzando l'algebra degli insiemi
Dobbiamo dimostrare che (A ∪ B)’ = A’ ∩ B’
Sia X = (A ∪ B)’ e Y = A’ ∩ B’
Sia p un elemento qualsiasi di X, allora p ∈ X ⇒ p ∈ (A ∪ B)’
⇒ p ∉ (A ∪ B)
⇒ p ∉ A oppure p ∉ B
⇒ p ∈ A’ e p ∈ B’
⇒ p ∈ A’ ∩ B’
⇒ p ∈ Y
∴X ⊂ Y. . . (Io)
Di nuovo, sia q un elemento qualsiasi di Y, allora q ∈ Y ⇒ q ∈ A’ ∩ B’
⇒ q ∈ A’ e q ∈ B’
⇒ q ∉ A oppure q ∉ B
⇒ q ∉ (A ∪ B)
⇒ q ∈ (A ∪ B)’
⇒ q ∈ X
∴Y ⊂X. . . (ii)
Da (i) e (ii) X = Y
(A ∪ B)’ = A’ ∩ B’
Leggi anche – Dimostrazione delle leggi di De-Morgan in algebra booleana
Dimostrazione utilizzando il diagramma di Venn
Diagramma di Venn per (A ∪ B)’
Diagramma di Venn per A’ ∩ B’
Da entrambi i diagrammi possiamo chiaramente dire:
(A ∪ B)’ = A’ ∩ B’
Questa è la prima legge di De Morgan.
Seconda legge di De Morgan
Lo afferma la seconda legge di De Morgan Il complementare dell'intersezione di due insiemi è uguale all'unione dei complementari di ciascun insieme.
Siano A e B due insiemi, allora matematicamente la Prima Legge di De Morgan è data come:
(A ∩ B)’ = A’ ∪ B’
Dove
- IN rappresenta l'operazione di unione tra insiemi,
- ∩ rappresenta l'operazione di intersezione tra insiemi e
- ' rappresenta l'operazione di complemento su un insieme.
È anche chiamato Legge dell’intersezione di De Morgan .
Dimostrazione utilizzando l'algebra degli insiemi
Seconda legge di De Morgan: (A ∩ B)’ = A’ ∪ B’
Sia X = (A ∩ B)’ e Y = A’ ∪ B’
Sia p un elemento qualsiasi di X, allora p ∈ X ⇒ p ∈ (A ∩ B)’
⇒ p ∉ (A ∩ B)
⇒ p ∉ A e p ∉ B
⇒ p ∈ A’ oppure p ∈ B’
⇒ p ∈ A’ ∪ B’
⇒ p ∈ Y
∴ X ⊂ Y ————–(i)
Di nuovo, sia q un elemento qualsiasi di Y, allora q ∈ Y ⇒ q ∈ A’ ∪ B’
⇒ q ∈ A’ oppure q ∈ B’
⇒ q ∉ A e q ∉ B
⇒ q ∉ (A ∩ B)
⇒ q ∈ (A ∩ B)’
pendenza indefinita
⇒ q ∈ X
∴ Y ⊂ X ————–(ii)
Da (i) e (ii) X = Y
(A ∩ B)’ = A’ ∪ B’
Dimostrazione utilizzando il diagramma di Venn
Diagramma di Venn per (A ∩ B)’
Diagramma di Venn per A’ ∪ B’
Da entrambi i diagrammi possiamo dire chiaramente
(A ∩ B)’ = A’ ∪ B’
Questa è la seconda legge di De Morgan.
Legge di De Morgan nell'algebra booleana
L'algebra booleana della legge di De Morgan definisce la relazione tra OR, AND e i complementi delle variabili, ed è data sia per il complemento di AND che per OR di due valori. Nell’algebra booleana esistono due leggi di De Morgan che sono:
- Prima legge di De Morgan
- Seconda legge di De Morgan
Comprendiamo queste leggi in dettaglio come di seguito:
Prima legge di De Morgan nell'algebra booleana
Lo afferma innanzitutto la legge di De Morgan Il complemento di OR di due o più variabili è uguale all'AND del complemento di ciascuna variabile.
Siano A e B due variabili, allora matematicamente la Prima Legge di De Morgan è data come:
(A + B)’ = A’ . B'
Dove
- + rappresenta l'operatore OR tra le variabili,
- . rappresenta l'operatore AND tra le variabili e
- ' rappresenta l'operazione di complemento sulla variabile.
I cancelli logici della prima legge di De Morgan
Nel contesto delle porte logiche e dell'algebra booleana, la legge di De Morgan afferma che entrambi i circuiti della porta logica, ovvero la porta NOT viene aggiunta all'uscita della porta OR e la porta NOT viene aggiunta all'ingresso della porta AND, sono equivalenti. Questi due circuiti di porte logiche sono dati come segue:
Prima tabella della verità della legge di De Morgan
La tavola di verità della prima legge di De Morgan è la seguente:
| UN | B | A+B | (A+B)’ | UN' | B' | UN'. B' attraversamento degli ordini per corrispondenza dell'albero binario |
|---|---|---|---|---|---|---|
| 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 |
Seconda legge di De Morgan in algebra booleana
Lo afferma la seconda legge di De Morgan Il complemento AND di due o più variabili è uguale all'OR del complemento di ciascuna variabile.
Siano A e B due variabili, allora matematicamente la Seconda Legge di De Morgan è data come:
(A . B)’ = A’ + B’
Dove
- + rappresenta l'operatore OR tra le variabili,
- . rappresenta l'operatore AND tra le variabili e
- ' rappresenta l'operazione di complemento sulla variabile.
Porte logiche della seconda legge di De Morgan
Nel contesto delle porte logiche e dell'algebra booleana, la legge di De Morgan afferma che entrambi i circuiti della porta logica, ovvero la porta NOT viene aggiunta all'uscita della porta AND e la porta NOT viene aggiunta all'ingresso della porta OR, sono equivalenti. Questi due circuiti di porte logiche sono dati come segue:
Tabella della verità della seconda legge di De Morgan
La tavola di verità della seconda legge di De Morgan è la seguente:
| UN | B | UN . B | (A.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 |
Dalla logica della legge di Morgan
Nella legge della logica di De Morgan le seguenti preposizioni sono tautologiche:
∼ (a ∧ b) ≡ ∼ a ∨ ∼ b
∼ (a ∨ b) ≡ ∼ un ∧ ∼ b
Dove,
- ∧ rappresenta la congiunzione di affermazioni,
- ∨ rappresenta la disgiunzione delle affermazioni,
- ~ rappresenta la negazione dell'affermazione, e
- ≡ rappresenta l'equivalenza delle affermazioni.
Dalla formula della legge di Morgan
Compiliamo tutte le formule della Legge di De Morgan, nell'elenco seguente.
Per la teoria degli insiemi:
- (A ∪ B)’ = A’ ∩ B’
- (A ∩ B)’ = A’ ∪ B’
Per l'algebra booleana:
- (A + B)’ = A’ . B'
- (A . B)’ = A’ + B’
Per la logica:
- ∼ (a ∧ b) ≡ ∼ a ∨ ∼ b
- ∼ (a ∨ b) ≡ ∼ un ∧ ∼ b
Esempi risolti sulla legge di De Morgan
Problema 1: Dato che U = {2, 3, 7, 8, 9}, A = {2, 7} e B = {2, 3, 9}. Dimostrare la seconda legge di De Morgan.
Soluzione:
U = {2, 3, 7, 8, 9}, A = {2, 7} e B = {2, 3, 9}
Per dimostrare: (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}
ordinare un elenco di arrayA’ = {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: Dato che U = {1, 4, 6, 8, 9}, A = {1, 9} e B = {4, 6, 9}. Dimostrare la prima legge di De Morgan.
Soluzione:
U = {1, 4, 6, 8, 9}, A = {1, 9} e B = {4, 6, 9}
Per dimostrare: (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’
Quindi dimostrato
Problema 3: semplificare l'espressione booleana: Y = [(A + B).C]'
Soluzione:
Y = [(A + B).C]’
Applicando la legge di De Morgan (A . B)’ = A’ + B’
Y = (A + B)’ + C’
Applicando la legge di De Morgan (A + B)’ = A’. B'
Y = A'. B'+C'
Problema 4: semplificare l'espressione booleana: X = [(A + B)' + C]'
Soluzione:
X = [(A + B)’ + C]’
Applicando la legge di De Morgan (A + B)’ = A’. B'
X = [(A + B)’]’ . C'
X = (A+B). C'
Controlla queste fonti per ulteriori informazioni:
| Argomento per l'interconnessione | Relativo a |
|---|---|
| Algebra booleana | Dalla legge di Morgan Algebra booleana |
| Insiemistica | La legge di De Morgan nella teoria degli insiemi |
| Porte logiche | Dalla logica della legge di Morgan |
| Matematica discreta | Dalla legge di Morgan Matematica discreta |
| Esempi di programmazione Java | Dalla legge di Morgan Java |
Esempi dimostrativi della legge di De Morgan
| Contesto | Esempio |
|---|---|
| Puzzle logici | Puzzle : Se non è vero che piove e fa freddo, cosa possiamo dedurre? Applicazione della legge di De Morgan : Possiamo dedurre che non piove o non fa freddo. Questo utilizza la Legge di De Morgan per semplificare la negazione di una congiunzione in una disgiunzione. |
| Programmazione | Scenario : Verifica se un numero non è né positivo né addirittura in un linguaggio di programmazione. Frammento di codice (pseudocodice) :if !(number>0 e il numero % 2 == 0)>può essere semplificato utilizzando la legge di De Morganif (number <= 0 or number % 2 != 0)>. Ciò dimostra come la Legge di De Morgan aiuti a semplificare le dichiarazioni condizionali. |
| Dimostrazioni matematiche | Dichiarazione : Dimostrare che il complemento dell'intersezione di due insiemi A e B è uguale all'unione dei loro complementi. Applicazione della legge di De Morgan : Secondo la legge di De Morgan, (A ∩ B)’ = A’ ∪ B’. Ciò mostra come la Legge di De Morgan viene utilizzata per semplificare le espressioni nella teoria degli insiemi. |
Dalla legge di Morgan Esempi pratici
Esempio 1: condimenti per pizza
Immagina di essere a una pizza party e ti viene detto che puoi scegliere qualsiasi condimento tranne i funghi e le olive insieme.
- Utilizzando la legge di De Morgan : Ciò significa che se non vuoi sia funghi che olive (Not (Mushrooms and Olives)), puoi non avere funghi (Not Mushrooms) o non avere olive (Not Olives) sulla tua pizza. Quindi potresti mangiare una pizza con solo funghi, solo olive o nessuno dei due!
Esempio 2: libri della biblioteca
Il tuo insegnante dice che non puoi portare in classe libri su maghi o draghi.
- Utilizzando la legge di De Morgan : Ciò significa che se non ti sono ammessi libri sui maghi o sui draghi (Not (Wizards or Dragons)), non puoi portare libri sui maghi (Not Wizards) e non puoi portare libri sui draghi (Not Dragons). Quindi, i libri sullo spazio o sugli animali vanno ancora bene!
Esempio 3: giocare all'aperto
Tua madre dice che non puoi giocare fuori se piove e fa freddo allo stesso tempo.
- Utilizzando la legge di De Morgan : Ciò significa che se non esci perché piove e fa freddo (Not (Raining and Cold)), non usciresti se pioveva (Not Raining) o semplicemente faceva freddo (Not Cold). Ma se c’è il sole e fa caldo, sei a posto!
Esempio 4: scelta di un film
Il tuo amico dice che non vuole guardare un film spaventoso o noioso.
- Utilizzando la legge di De Morgan : Ciò significa che se il tuo amico non vuole un film spaventoso o noioso (Not (Scary or Boring)), non vuole un film spaventoso (Not Scary) e non vuole un film noioso (Not Boring) . Quindi, un film divertente o emozionante sarebbe perfetto!
Applicazioni logiche della legge di De Morgan
| Area di applicazione | Descrizione |
|---|---|
| Ragionamento logico | Negli enigmi o nelle argomentazioni logiche, la Legge di De Morgan aiuta a semplificare le negazioni complesse. Ad esempio, negare Tutte le mele sono rosse in Non tutte le mele sono rosse implica che Alcune mele non sono rosse. |
| Informatica | La legge di De Morgan è cruciale per ottimizzare le dichiarazioni condizionali nella programmazione. Consente ai programmatori di semplificare condizioni logiche complesse, rendendo il codice più efficiente e leggibile. |
| Progettazione di circuiti elettronici | Nell'elettronica digitale, la legge di De Morgan viene utilizzata per progettare e semplificare i circuiti. Ad esempio, aiuta a convertire porte AND in porte OR (e viceversa) utilizzando porte NOT, facilitando la creazione di layout di circuito più efficienti. |
Dalla legge di Morgan – Domande frequenti
La prima formulazione della legge di State De Morgan nella teoria degli insiemi.
La prima legge di De Morgan nella teoria degli insiemi afferma che il complemento dell’unione di due insiemi è uguale all’intersezione dei loro complementi individuali.
Seconda legge di State De Morgan in algebra booleana.
La seconda legge di De Morgan nell'algebra booleana afferma che il complemento di AND di due o più variabili è uguale all'OR del complemento di ciascuna variabile.
Scrivi la formula della legge di De Morgan nella teoria degli insiemi.
La formula della legge di De Morgan nella teoria degli insiemi:
(i) (A ∪ B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ ∪ B’
Scrivi la formula della legge di De Morgan in algebra booleana.
La formula della legge di De Morgan nell'algebra booleana:
(i) (A + B)’ = A’ . B'
(ii) (A . B)’ = A’ + B’
Scrivi alcune applicazioni della legge di De Morgan.
Alcune delle applicazioni della legge di De Morgan sono quella di minimizzare la complessa espressione booleana e di semplificarla.
Come dimostrare la legge di De Morgan?
La legge di De Morgan nella teoria degli insiemi può essere dimostrata dai diagrammi di Venn e la legge di De Morgan nell’algebra booleana può essere dimostrata dalle tabelle di verità.