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

• Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если она является дизъюнкцией неповторяющихся конъюнкций k переменных х₁, х₂, …, х_k, причём на i-м месте каждой конъюнкции стоит либо переменная х_i, либо её отрицание.
• Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (СКНФ), если она является конъюнкцией неповторяющихся дизъюнкций k переменных х₁, х₂, …, х_k, причём на i-м месте каждой дизъюнкции стоит либо переменная х_i, либо её отрицание.
• Примеры.

СДНФ: $({𝑥}_1\wedge {𝑥}_2\wedge \stackrel{-}{{𝑥}_3})\vee (\stackrel{-}{{𝑥}_1}\wedge \stackrel{-}{{𝑥}_2}\wedge {𝑥}_3)$

СКНФ: $({𝑥}_1\vee \stackrel{-}{{𝑥}_2}\vee \stackrel{-}{{𝑥}_3})\wedge ({𝑥}_1\vee \stackrel{-}{{𝑥}_2}\vee {𝑥}_3)\wedge (\stackrel{-}{{𝑥}_1}\vee \stackrel{-}{{𝑥}_2}\vee {𝑥}_3)$

• Алгоритм построения СДНФ по таблице истинности.

  1. Выбрать строки таблицы, в которых значение функции равно 1.
  2. Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — её отрицание.
  3. Все полученные конъюнкции связать операциями дизъюнкции.
• Алгоритм построения СКНФ по таблице истинности аналогичен алгоритму построения СДНФ.