Известен математик ДеМорган изобретил двете най-важни теореми на булевата алгебра. Теоремите на DeMorgan се използват за математическа проверка на еквивалентността на елементите NOR и отрицателното И и отрицателното ИЛИ и NAND. Тези теореми играят важна роля при решаването на различни булеви алгебрични изрази. В таблицата по-долу е дефинирана логическата операция за всяка комбинация от входната променлива.
| Входни променливи | Изходно състояние | ||||
|---|---|---|---|---|---|
| А | Б | И | NAND | ИЛИ | НИТО |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 |
Правилата на теоремата на Де-Морган се произвеждат от булевите изрази за ИЛИ, И и НЕ, като се използват две входни променливи x и y. Първата теорема на Деморган гласи, че ако извършим операцията И на две входни променливи и след това извършим операцията НЕ на резултата, резултатът ще бъде същият като операцията ИЛИ на допълнението на тази променлива. Втората теорема на ДеМорган казва, че ако извършим операция ИЛИ на две входни променливи и след това изпълним НЕ операция на резултата, резултатът ще бъде същият като операцията И на допълнението на тази променлива.
Първата теорема на Де-Морган
Съгласно първата теорема резултатът от допълнението на операцията И е равен на операцията ИЛИ на допълнението на тази променлива. По този начин тя е еквивалентна на функцията NAND и е функция отрицателно ИЛИ, доказваща, че (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 |
Втората теорема на Де-Морган
Съгласно втората теорема резултатът от допълнението на операцията ИЛИ е равен на операцията И на допълнението на тази променлива. По този начин, това е еквивалентът на функцията NOR и е функция отрицателно И, доказваща, че (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 |
Нека вземем няколко примера, в които вземаме някои изрази и прилагаме теоремите на ДеМорган.
Пример 1: (A.B.C)'
(A.B.C)'=A'+B'+C'
Пример 2: (A+B+C)'
(A+B+C)'=A'.B'.C
Пример 3: ((A+BC')'+D(E+F')')'
За да приложим теоремата на DeMorgan върху този израз, трябва да следваме следните изрази:
1) В пълния израз първо намираме тези термини, върху които можем да приложим теоремата на ДеМорган и третираме всеки член като отделна променлива.
Така,
2) След това прилагаме първата теорема на DeMorgan. Така,
3) След това използваме правило номер 9, т.е. (A=(A')') за премахване на двойните черти.
4) След това прилагаме втората теорема на ДеМорган. Така,
5) Приложете отново правило номер 9, за да отмените двойната лента
Този израз няма член, в който можем да приложим някакво правило или теорема. И така, това е крайният израз.
Пример 3: (AB'.(A + C))'+ A'B.(A + B + C')'
обхождане на дърво с предварителна поръчка
