Відомий математик ДеМорган винайшов дві найважливіші теореми булевої алгебри. Теореми Деморгана використовуються для математичної перевірки еквівалентності вентилів АБО та негативного І, а також вентилів негативного АБО та І-НЕ. Ці теореми відіграють важливу роль у розв’язуванні різних виразів булевої алгебри. У наведеній нижче таблиці визначено логічну операцію для кожної комбінації вхідної змінної.
| Вхідні змінні | Вихідний стан | ||||
|---|---|---|---|---|---|
| А | Б | І | 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. Перша теорема Деморгана говорить, що якщо ми виконуємо операцію І для двох вхідних змінних, а потім виконуємо операцію НЕ для результату, результат буде таким же, як і операція АБО доповнення до цієї змінної. Друга теорема ДеМоргана говорить, що якщо ми виконуємо операцію АБО двох вхідних змінних, а потім виконуємо НІ результату, результат буде таким самим, як і операція AND доповнення цієї змінної.
Перша теорема Де Моргана
Згідно з першою теоремою результат доповнення до операції І дорівнює операції АБО доповнення цієї змінної. Таким чином, це еквівалент функції NAND і є функцією негативного АБО, яка доводить, що (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 |
Друга теорема Де Моргана
Згідно з другою теоремою результат доповнення операції АБО дорівнює операції І доповнення цієї змінної. Таким чином, це еквівалент функції NOR і функція негативного І, яка доводить, що (A+B)' = A'.B', і ми можемо показати це за допомогою наступної таблиці істинності.
| Вхідні дані | Вихід для кожного члена | |||||
|---|---|---|---|---|---|---|
| А | Б | A+B | (A+B)' | А' | 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')')'
Щоб застосувати теорему ДеМоргана до цього виразу, ми повинні дотримуватися таких виразів:
1) У повному виразі спочатку ми знаходимо ті терміни, до яких ми можемо застосувати теорему ДеМоргана, і розглядаємо кожен член як одну змінну.
Так,
2) Далі ми застосовуємо першу теорему ДеМоргана. Так,
3) Далі ми використовуємо правило номер 9, тобто (A=(A')') для скасування подвійних смуг.
4) Далі ми застосовуємо другу теорему ДеМоргана. Так,
5) Знову застосуйте правило номер 9, щоб скасувати подвійну смугу
Цей вираз не має терміна, до якого ми можемо застосувати будь-яке правило чи теорему. Отже, це остаточний вираз.
Приклад 3: (AB'.(A + C))'+ A'B.(A + B + C')'
програмування в масивах c
