Два закона
Законы Де Моргана описывают, как отрицание распределяется по AND и OR:
- ¬(A·B) = ¬A + ¬B — отрицание AND равно OR от отрицаний.
- ¬(A+B) = ¬A · ¬B — отрицание OR равно AND от отрицаний.
Почему это важно в аппаратуре
В технологии CMOS вентили NAND и NOR дешевле в производстве, чем AND/OR, а любую булеву функцию можно построить только из вентилей NAND (или только из NOR). Законы Де Моргана — это инструмент, позволяющий переписать выражение AND/OR/NOT в эквивалентную схему только на NAND или только на NOR.
Например, A·B равно ¬(¬A+¬B) — полезное тождество, когда доступны только вентили NOR, или когда технология производства делает NOR значительно быстрее AND.
Разобранный пример
Возьмём выражение ¬(A·B + C). Сначала применим закон Де Моргана к внешнему отрицанию:
- ¬(A·B + C) = ¬(A·B) · ¬C
- Применим закон ещё раз к ¬(A·B): = (¬A + ¬B) · ¬C
Проверьте сами
Постройте обе версии выражения — исходную и преобразованную по Де Моргану — в редакторе схем, затем используйте инструмент «Проверка», чтобы убедиться в отсутствии незаполненных выходов или неподключённых входов, и «Таблицу истинности», чтобы убедиться, что обе версии дают одинаковый результат.