Znany matematyk DeMorgana wynalazł dwa najważniejsze twierdzenia algebry Boole'a. Twierdzenia DeMorgana służą do matematycznej weryfikacji równoważności bramek NOR i ujemnych bramek AND oraz ujemnych bramek OR i NAND. Twierdzenia te odgrywają ważną rolę w rozwiązywaniu różnych wyrażeń algebry Boole'a. W poniższej tabeli zdefiniowano operację logiczną dla każdej kombinacji zmiennej wejściowej.
Zmienne wejściowe | Warunek wyjściowy | ||||
---|---|---|---|---|---|
A | B | I | NAND | LUB | ANI |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 0 |
Reguły twierdzenia De-Morgana są tworzone na podstawie wyrażeń boolowskich dla OR , AND i NOT przy użyciu dwóch zmiennych wejściowych x i y. Pierwsze twierdzenie Demorgana mówi, że jeśli wykonamy operację AND na dwóch zmiennych wejściowych, a następnie na wyniku wykonamy operację NOT, to wynik będzie taki sam, jak operacja OR na dopełnieniu tej zmiennej. Drugie twierdzenie DeMorgana mówi, że jeśli wykonamy operację OR na dwóch zmiennych wejściowych, a następnie wykonamy: NIE operacji wyniku, wynik będzie taki sam, jak operacja AND uzupełnienia tej zmiennej.
Pierwsze twierdzenie De-Morgana
Zgodnie z pierwszym twierdzeniem wynik uzupełnienia operacji AND jest równy operacji OR dopełnienia tej zmiennej. Zatem jest to odpowiednik funkcji NAND i jest funkcją ujemną-OR udowadniającą, że (A.B)' = A'+B' i możemy to pokazać za pomocą poniższej tabeli.
Wejścia | Dane wyjściowe dla każdego terminu | |||||
---|---|---|---|---|---|---|
A | B | A.B | (A.B)” | A' | B' | A'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 |
Drugie twierdzenie De-Morgana
Zgodnie z drugim twierdzeniem wynik uzupełnienia operacji OR jest równy operacji AND dopełnienia tej zmiennej. Zatem jest to odpowiednik funkcji NOR i jest funkcją ujemną ORAZ udowadniającą, że (A+B)' = A'.B' i możemy to pokazać za pomocą poniższej tabeli prawdy.
Wejścia | Dane wyjściowe dla każdego terminu | |||||
---|---|---|---|---|---|---|
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 |
Weźmy kilka przykładów, w których bierzemy pewne wyrażenia i stosujemy twierdzenia DeMorgana.
Przykład 1: (A.B.C)”
(A.B.C)'=A'+B'+C'
Przykład 2: (A+B+C)'
(A+B+C)'=A'.B'.C
Przykład 3: ((A+BC')'+D(E+F')')'
Aby zastosować twierdzenie DeMorgana do tego wyrażenia, musimy zastosować się do następujących wyrażeń:
1) W pełnym wyrażeniu najpierw znajdujemy te terminy, na których możemy zastosować twierdzenie DeMorgana i traktować każdy termin jako pojedynczą zmienną.
Więc,
2) Następnie stosujemy pierwsze twierdzenie DeMorgana. Więc,
3) Następnie używamy zasady numer 9, tj. (A=(A')') do anulowania podwójnych prętów.
4) Następnie stosujemy drugie twierdzenie DeMorgana. Więc,
5) Ponownie zastosuj zasadę numer 9, aby anulować podwójny pasek
To wyrażenie nie ma terminu, w którym moglibyśmy zastosować jakąkolwiek regułę lub twierdzenie. To jest więc ostatnie wyrażenie.
Przykład 3: (AB'.(A + C))'+ A'B.(A + B + C')'
przykłady kodu Java