Prawo De Morgana jest najczęstszym prawem w teorii mnogości i algebrze Boole'a, a także w teorii mnogości. W tym artykule poznamy prawo De Morgana, prawo De Morgana w teorii mnogości i prawo De Morgana w algebrze Boole'a wraz z ich dowodami, tablicami prawdy i diagramami bramek logicznych. Artykuł zawiera także rozwiązany przykład prawa De Morgana oraz często zadawane pytania dotyczące prawa De Morgana. Poznajmy prawo De Morgana.
co to jest 10 z 60
Spis treści
- Co to jest prawo De Morgana
- Prawo De Morgana w teorii mnogości
- Pierwsze prawo De Morgana
- Drugie prawo De Morgana
- Dowód przy użyciu algebry zbiorów
- Prawo De Morgana w algebrze Boole’a
- Ze wzoru na prawo Morgana
- Rozwiązane przykłady prawa De Morgana
- Logiczne zastosowania prawa De Morgana
Co to jest prawo De Morgana
Prawo De Morgana to prawo określające relację między sumą, przecięciem i dopełnieniem w teorii mnogości. W algebrze Boole'a podaje relację pomiędzy AND, OR i uzupełnieniami zmiennej, a w logice podaje relację pomiędzy AND, OR lub negacją stwierdzenia. Za pomocą prawa De Morgana możemy zoptymalizować różne obwody logiczne zawierające bramki logiczne, które pomagają nam wykonać tę samą operację, ale z bardzo małą liczbą urządzeń.
Prawo De Morgana w teorii mnogości
Prawo De Morgana w teoria zbiorów definiuje relację między sumą, przecięciem i dopełnieniem zbiorów i jest podana zarówno dla dopełnienia sumy, jak i przecięcia dwóch zbiorów. W teorii mnogości istnieją dwa prawa De Morgana:
- Pierwsze prawo De Morgana
- Drugie prawo De Morgana
Przyjrzyjmy się szczegółowo tym przepisom, jak poniżej:
Pierwsze prawo De Morgana
Mówi o tym pierwsze prawo De Morgana Dopełnienie sumy dwóch zbiorów jest równe przecięciu dopełnień każdego zbioru.
Niech A i B będą dwoma zbiorami, wtedy matematycznie Pierwsze prawo De Morgana będzie zapisane jako:
(A ∪ B)’ = A’ ∩ B’
Gdzie
- W reprezentuje operację Unii między zbiorami,
- ∩ reprezentuje operację przecięcia między zbiorami, i
- ' reprezentuje operację dopełnienia na zbiorze.
Nazywa się to również Prawo Unii De Morgana.
Omów szczegółowo dowód prawa De Morgana
| Krok | Wyjaśnienie |
|---|---|
| Krok 1: Podaj prawo | Prawo De Morgana składa się z dwóch części: ¬(A ∪ B) = ¬A ∩ ¬B i ¬(A ∩ B) = ¬A ∪ ¬B. |
| Krok 2: Wybierz element | Udowodnijmy ¬(A ∪ B) = ¬A ∩ ¬B. Załóżmy, że element x nie występuje w A ∪ B. |
| Krok 3: Zrozum założenie | Jeśli x nie należy do A ∪ B, to x nie należy ani do A, ani do B. |
| Krok 4: Zastosuj definicję | Zgodnie z definicją dopełnienia, jeśli x nie należy do A ani do B, to x należy do ¬A i ¬B. |
| Krok 5: Zakończ dowód | Ponieważ x należy do ¬A i ¬B, x należy do ¬A ∩ ¬B. W ten sposób pokazaliśmy ¬(A ∪ B) = ¬A ∩ ¬B. |
Dowód przy użyciu algebry zbiorów
Musimy udowodnić, (A ∪ B)’ = A’ ∩ B’
Niech X = (A ∪ B)’ i Y = A’ ∩ B’
Niech p będzie dowolnym elementem X, wówczas p ∈ X ⇒ p ∈ (A ∪ B)’
⇒ p ∉ (A ∪ B)
⇒ p ∉ A lub p ∉ B
⇒ p ∈ A’ i p ∈ B’
⇒ p ∈ A’ ∩ B’
⇒ p ∈ Y
∴X ⊂ Y. . . (Siema)
Ponownie, niech q będzie dowolnym elementem Y, wtedy q ∈ Y ⇒ q ∈ A’ ∩ B’
⇒ q ∈ A’ i q ∈ B’
⇒ q ∉ A lub q ∉ B
⇒ q ∉ (A ∪ B)
⇒ q ∈ (A ∪ B)’
⇒ q ∈ X
∴Y ⊂X. . . (ii)
Z (i) i (ii) X = Y
(A ∪ B)’ = A’ ∩ B’
Przeczytaj także – Dowód praw De-Morgana w algebrze Boole'a
Dowód za pomocą diagramu Venna
Diagram Venna dla (A ∪ B)’
Diagram Venna dla A’ ∩ B’
Z obu diagramów możemy wyraźnie stwierdzić, że
(A ∪ B)’ = A’ ∩ B’
To jest pierwsze prawo de Morgana.
Drugie prawo De Morgana
Mówi o tym drugie prawo De Morgana Dopełnienie przecięcia dwóch zbiorów jest równe sumie dopełnień każdego zbioru.
Niech A i B będą dwoma zbiorami, wtedy matematycznie Pierwsze prawo De Morgana będzie zapisane jako:
(A ∩ B)’ = A’ ∪ B’
Gdzie
- W reprezentuje operację Unii między zbiorami,
- ∩ reprezentuje operację przecięcia między zbiorami, i
- ' reprezentuje operację dopełnienia na zbiorze.
Nazywa się to również Prawo de Morgana przecięcia .
Dowód przy użyciu algebry zbiorów
Drugie prawo De Morgana: (A ∩ B)’ = A’ ∪ B’
Niech X = (A ∩ B)’ i Y = A’ ∪ B’
Niech p będzie dowolnym elementem X, wówczas p ∈ X ⇒ p ∈ (A ∩ B)’
⇒ p ∉ (A ∩ B)
⇒ p ∉ A i p ∉ B
⇒ p ∈ A’ lub p ∈ B’
⇒ p ∈ A’ ∪ B’
⇒ p ∈ Y
∴ X ⊂ Y ————–(i)
Ponownie, niech q będzie dowolnym elementem Y, wtedy q ∈ Y ⇒ q ∈ A’ ∪ B’
⇒ q ∈ A’ lub q ∈ B’
⇒ q ∉ A i q ∉ B
⇒ q ∉ (A ∩ B)
⇒ q ∈ (A ∩ B)’
⇒ q ∈ X
∴ Y ⊂ X ————–(ii)
Z (i) i (ii) X = Y
(A ∩ B)’ = A’ ∪ B’
Dowód za pomocą diagramu Venna
Diagram Venna dla (A ∩ B)’
Diagram Venna dla A’ ∪ B’
Z obu diagramów możemy jasno powiedzieć
(A ∩ B)’ = A’ ∪ B’
To jest Drugie Prawo De Morgana.
Prawo De Morgana w algebrze Boole’a
Prawo De Morgana Algebra Boole'a definiuje relację pomiędzy OR, AND i uzupełnieniami zmiennych i jest podana zarówno dla uzupełnienia AND, jak i OR dwóch wartości. W algebrze Boole'a istnieją dwa prawa De Morgana, którymi są:
- Pierwsze prawo De Morgana
- Drugie prawo De Morgana
Przyjrzyjmy się szczegółowo tym przepisom, jak poniżej:
Pierwsze prawo De Morgana w algebrze Boole’a
Mówi o tym pierwsze prawo De Morgana Uzupełnienie OR dwóch lub więcej zmiennych jest równe AND uzupełnienia każdej zmiennej.
Niech A i B będą dwiema zmiennymi, wtedy matematycznie Pierwsze prawo De Morgana można zapisać jako:
(A + B)’ = A’ . B'
Gdzie
- + reprezentuje operator OR pomiędzy zmiennymi,
- . reprezentuje operator AND pomiędzy zmiennymi, oraz
- ' reprezentuje operację dopełnienia na zmiennej.
Pierwsze bramki logiczne z prawem De Morgana
W kontekście bramek logicznych i algebry Boole'a prawo De Morgana stwierdza, że oba obwody bramki logicznej, tj. bramka NOT jest dodawana do wyjścia bramki OR i bramka NOT dodawana do wejścia bramki AND, są równoważne. Te dwa obwody bramek logicznych podano w następujący sposób:
Pierwsza tabela prawdy prawa De Morgana
Tabela prawdy pierwszego prawa De Morgana jest podana w następujący sposób:
| 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 |
Drugie prawo De Morgana w algebrze Boole’a
Mówi o tym drugie prawo De Morgana Uzupełnienie AND dwóch lub więcej zmiennych jest równe OR uzupełnienia każdej zmiennej.
Niech A i B będą dwiema zmiennymi, wówczas matematycznie Drugie Prawo De Morgana można zapisać jako:
(A. B)’ = A’ + B’
Gdzie
- + reprezentuje operator OR pomiędzy zmiennymi,
- . reprezentuje operator AND pomiędzy zmiennymi, oraz
- ' reprezentuje operację dopełnienia na zmiennej.
Bramki logiczne prawa De Morgana
W kontekście bramek logicznych i algebry Boole'a prawo De Morgana stwierdza, że oba obwody bramki logicznej, tj. bramka NOT jest dodawana do wyjścia bramki AND i bramka NOT jest dodawana do wejścia bramki OR, są równoważne. Te dwa obwody bramek logicznych podano w następujący sposób:
Druga tabela prawdy prawa De Morgana
Tabela prawdy dla drugiego prawa De Morgana jest podana w następujący sposób:
| 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 |
Z logiki prawa Morgana
W prawie De Morgana dla logiki poniższe przyimki są tautologią:
∼ (a ∧ b) ≡ ∼ za ∨ ∼ b
∼ (a ∨ b) ≡ ∼ za ∧ ∼ b
Gdzie,
- ∧ reprezentuje koniunkcję stwierdzeń,
- ∨ reprezentuje alternatywę zdań,
- ~ reprezentuje zaprzeczenie stwierdzenia, i
- ≡ reprezentuje równoważność stwierdzeń.
Ze wzoru na prawo Morgana
Zestawmy wszystkie wzory prawa De Morgana na poniższej liście.
Dla teorii mnogości:
- (A ∪ B)’ = A’ ∩ B’
- (A ∩ B)’ = A’ ∪ B’
Dla algebry Boole'a:
- (A + B)’ = A’ . B'
- (A. B)’ = A’ + B’
Dla logiki:
- ∼ (a ∧ b) ≡ ∼ za ∨ ∼ b
- ∼ (a ∨ b) ≡ ∼ za ∧ ∼ b
Rozwiązane przykłady prawa De Morgana
Problem 1: Biorąc pod uwagę, że U = {2, 3, 7, 8, 9}, A = {2, 7} i B = {2, 3, 9}. Udowodnij drugie prawo De Morgana.
Rozwiązanie:
U = {2, 3, 7, 8, 9}, A = {2, 7} i B = {2, 3, 9}
Aby udowodnić: (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’
Problem 2: Biorąc pod uwagę, że U = {1, 4, 6, 8, 9}, A = {1, 9} i B = {4, 6, 9}. Udowodnij pierwsze prawo De Morgana.
Rozwiązanie:
U = {1, 4, 6, 8, 9}, A = {1, 9} i B = {4, 6, 9}
Aby udowodnić: (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’
Stąd udowodnione
Problem 3: Uprość wyrażenie logiczne: Y = [(A + B).C]’
zamień z ciągu w Javie
Rozwiązanie:
Y = [(A + B).C]’
Stosowanie prawa De Morgana (A . B)’ = A’ + B’
Y = (A + B)’ + C’
Stosowanie prawa De Morgana (A + B)’ = A’. B'
Y = A'. B' + C'
Problem 4: Uprość wyrażenie logiczne: X = [(A + B)’ + C]’
Rozwiązanie:
X = [(A + B)’ + C]’
Stosowanie prawa De Morgana (A + B)’ = A’. B'
X = [(A + B)’]’ . C'
X = (A + B). C'
Sprawdź te źródła, aby uzyskać więcej:
| Temat do łączenia | Związany z |
|---|---|
| Algebra Boole’a | Z algebry Boole’a z prawem Morgana |
| Teoria zbiorów | Prawo De Morgana w teorii mnogości |
| Bramki logiczne | Z logiki praw Morgana |
| Matematyka dyskretna | Z prawa Morgana w matematyce dyskretnej |
| Przykłady programowania w Javie | Z prawa Morgana Java |
Przedstaw przykłady prawa De Morgana
| Kontekst | Przykład |
|---|---|
| Zagadki logiczne | Puzzle : Jeśli nie jest prawdą, że pada deszcz i jest zimno, to co możemy z tego wywnioskować? Zastosowanie prawa De Morgana : Możemy wywnioskować, że nie pada deszcz i nie jest zimno. Wykorzystuje to prawo De Morgana do uproszczenia negacji koniunkcji w alternatywę. |
| Programowanie | Scenariusz : Sprawdzanie, czy liczba nie jest ani dodatnia, ani nawet w języku programowania. Fragment kodu (pseudokod) :if !(number>0 i liczba % 2 == 0)>można uprościć, korzystając z prawa De Morganaif (number <= 0 or number % 2 != 0)>. To pokazuje, jak prawo De Morgana pomaga w upraszczaniu instrukcji warunkowych. |
| Dowody matematyczne | Oświadczenie : Udowodnić, że dopełnienie przecięcia dwóch zbiorów A i B jest równe sumie ich dopełnień. Zastosowanie prawa De Morgana : Zgodnie z prawem De Morgana, (A ∩ B)’ = A’ ∪ B’. To pokazuje, jak prawo De Morgana jest wykorzystywane do upraszczania wyrażeń w teorii mnogości. |
Z praktycznych przykładów prawa Morgana
Przykład 1: Dodatki do pizzy
Wyobraź sobie, że jesteś na imprezie z pizzą i powiedziano Ci, że możesz wybrać dowolne dodatki, z wyjątkiem grzybów i oliwek razem.
- Korzystanie z prawa De Morgana : Oznacza to, że jeśli nie chcesz jednocześnie grzybów i oliwek (Nie (grzyby i oliwki)), możesz albo nie mieć grzybów (nie grzyby), albo nie mieć oliwek (nie oliwki) na swojej pizzy. Możesz więc zjeść pizzę tylko z grzybami, tylko z oliwkami, albo z żadnymi!
Przykład 2: Książki biblioteczne
Twój nauczyciel mówi, że nie możesz przynosić do klasy książek o czarodziejach i smokach.
- Korzystanie z prawa De Morgana : Oznacza to, że jeśli nie wolno Ci przynosić książek o czarodziejach lub smokach (Nie (Czarodzieje i Smoki)), nie możesz przynosić książek o czarodziejach (Nie Czarodzieje) i nie możesz przynosić książek o smokach (Nie Smoki). Zatem książki o kosmosie i zwierzętach są nadal w porządku!
Przykład 3: Zabawa na świeżym powietrzu
Twoja mama mówi, że nie możesz bawić się na zewnątrz, jeśli jednocześnie pada deszcz i jest zimno.
- Korzystanie z prawa De Morgana : Oznacza to, że jeśli nie wyjdziesz, bo pada deszcz i jest zimno (Nie (deszcz i zimno)), nie wyjdziesz, jeśli tylko pada deszcz (nie pada) lub po prostu jest zimno (nie zimno). Ale jeśli jest słonecznie i ciepło, możesz jechać!
Przykład 4: Wybór filmu
Twój przyjaciel mówi, że nie chce oglądać filmu, który jest straszny lub nudny.
- Korzystanie z prawa De Morgana : Oznacza to, że jeśli Twój znajomy nie chce filmu, który jest straszny lub nudny (Nie (Straszny lub Nudny)), nie chce strasznego filmu (Nie Straszny) i nie chce nudnego filmu (Nie Nudny) . Więc zabawny lub ekscytujący film byłby idealny!
Logiczne zastosowania prawa De Morgana
| Obszar zastosowań | Opis |
|---|---|
| Logiczne rozumowanie | W łamigłówkach logicznych lub argumentach prawo De Morgana pomaga uprościć złożone negacje. Na przykład zanegowanie Wszystkie jabłka są czerwone na Nie wszystkie jabłka są czerwone oznacza, że Niektóre jabłka nie są czerwone. |
| Informatyka | Prawo De Morgana ma kluczowe znaczenie w optymalizacji instrukcji warunkowych w programowaniu. Pozwala programistom upraszczać złożone warunki logiczne, czyniąc kod bardziej wydajnym i czytelnym. |
| Projekt obwodu elektronicznego | W elektronice cyfrowej prawo De Morgana służy do projektowania i upraszczania obwodów. Na przykład pomaga w konwersji bramek AND na bramki OR (i odwrotnie) przy użyciu bramek NOT, ułatwiając tworzenie bardziej wydajnych układów obwodów. |
Z prawa Morgana – często zadawane pytania
Pierwsze stwierdzenie prawa State De Morgana w teorii mnogości.
Pierwsze prawo De Morgana w teorii mnogości stwierdza, że dopełnienie sumy dwóch zbiorów jest równe przecięciu ich poszczególnych dopełnień.
Drugie prawo State De Morgana w algebrze Boole’a.
Drugie prawo De Morgana w algebrze Boole'a stwierdza, że uzupełnienie AND dwóch lub więcej zmiennych jest równe OR uzupełnienia każdej zmiennej.
Zapisz wzór na prawo De Morgana w teorii mnogości.
Wzór na prawo De Morgana w teorii mnogości:
(i) (A ∪ B)’ = A’ ∩ B’
(ii) (A ∩ B)’ = A’ ∪ B’
Napisz wzór na prawo De Morgana w algebrze Boole’a.
Wzór na prawo De Morgana w algebrze Boole’a:
(i) (A + B)’ = A’. B'
(ii) (A. B)’ = A’ + B’
Napisz kilka zastosowań prawa De Morgana.
Niektóre zastosowania prawa De Morgana polegają na minimalizacji złożonego wyrażenia logicznego i jego uproszczeniu.
Jak udowodnić prawo De Morgana?
Prawo De Morgana w teorii mnogości można udowodnić za pomocą diagramów Venna, a prawo De Morgana w algebrze Boole'a można udowodnić za pomocą tablic prawdy.