logo

Twierdzenie De-Morgana

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

Twierdzenie De-Morgana

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

Twierdzenie De-Morgana

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ą.

Twierdzenie De-Morgana
Twierdzenie De-Morgana

Więc,

Twierdzenie De-Morgana

2) Następnie stosujemy pierwsze twierdzenie DeMorgana. Więc,

Twierdzenie De-Morgana

3) Następnie używamy zasady numer 9, tj. (A=(A')') do anulowania podwójnych prętów.

Twierdzenie De-Morgana

4) Następnie stosujemy drugie twierdzenie DeMorgana. Więc,

Twierdzenie De-Morgana

5) Ponownie zastosuj zasadę numer 9, aby anulować podwójny pasek

Twierdzenie De-Morgana

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
Twierdzenie De-Morgana