Канонические формы логических выражений

• Дизъюнктивная нормальная форма (ДНФ) — логическое выражение представляется в виде дизъюнкции (логическое ИЛИ) нескольких конъюнктов, где каждый конъюнкт — это конъюнкция (логическое И) переменных или их отрицаний.

 Пример ДНФ:
 ${\displaystyle F=(A\land {\overline {B}}\land C)\lor ({\overline {A}}\land B\land C)\lor (A\land B\land {\overline {C}})}$

• Конъюнктивная нормальная форма (КНФ) — логическое выражение представляется в виде конъюнкции (логическое И) нескольких дизъюнктов, где каждый дизъюнкт — это дизъюнкция (логическое ИЛИ) переменных или их отрицаний.

 Пример КНФ:
 ${\displaystyle F=(A\lor B\lor {\overline {C}})\land ({\overline {A}}\lor {\overline {B}}\lor C)\land (A\lor {\overline {B}}\lor C)}$

• Алгебраическая нормальная форма (АНФ) или полином Жегалкина — представление логического выражения в виде суммы по модулю 2 (операция XOR, обозначается символом ${\displaystyle \oplus }$) произведений переменных.

 Пример АНФ:
 ${\displaystyle F=A\oplus (B\land C)\oplus (A\land B\land {\overline {C}})}$

Любое логическое выражение можно преобразовать в ДНФ или КНФ, используя законы логики:

• Дистрибутивность для ДНФ:

 ${\displaystyle A\land (B\lor C)=(A\land B)\lor (A\land C)}$

• Дистрибутивность для КНФ:

 ${\displaystyle A\lor (B\land C)=(A\lor B)\land (A\lor C)}$

• Законы де Моргана для отрицания выражений:

 ${\displaystyle {\overline {A\land B}}={\overline {A}}\lor {\overline {B}}}$
 
 ${\displaystyle {\overline {A\lor B}}={\overline {A}}\land {\overline {B}}}$

Для получения алгебраической нормальной формы используются следующие шаги:

1. Представление функции в СДНФ. 2. Замена логических операций на соответствующие операции в АНФ:

  * ИЛИ заменяется на XOR (${\displaystyle \oplus }$).
  * Отрицание переменной заменяется на ${\displaystyle 1\oplus A}$.

3. Применение правил упрощения:

  * ${\displaystyle A\oplus A=0}$
  * ${\displaystyle A\oplus 0=A}$
  * ${\displaystyle A\oplus 1={\overline {A}}}$

Канонические формы широко используются при проектировании и анализе цифровых схем:

• Минимизация логических функций: Канонические формы позволяют применять методы оптимизации, такие как метод карт Карно или табличный метод Квайна — Мак-Класки, для сокращения числа логических элементов в схеме.

• Синтез цифровых схем: На основе канонических форм можно переходить от логического выражения к схемотехнической реализации, используя базовые логические элементы: И, ИЛИ, НЕ.

• Анализ логических выражений: Упрощение и преобразование логических выражений для обнаружения эквивалентности или противоречивости.

Канонические формы логических выражений являются важным инструментом в математической логике и цифровой электронике. Они позволяют систематизировать и упростить работу с логическими функциями, обеспечивая эффективное проектирование и оптимизацию цифровых устройств.