Написание условий в нормальной конъюнктивной форме

Question

Конъюнктивная нормальная форма (CNF) является стандартизированным обозначением для формул высказываний, которые диктуют, что каждая формула должна быть написана как соединение дизъюнкций. Каждая логическая формула может быть преобразована в CNF. Так, например:

A | (B & C)

Имеет представление в CNF, как это:

(A | B) & (A | C)

Это лучшая практика в программировании для написания условных выражений в CNF?

Answer 1

Нет, это не очень хорошая идея. Конъюнктивная нормальная форма в основном используется в теоретической информатике. Существуют алгоритмы для решения формул в CNF, а также доказательства сложности времени и NP-твердости.

С прагматической точки зрения вы должны писать код с использованием логических операторов, которые наиболее "естественно" описывают логику. Это означает полное использование вложенных выражений, таких операторов, как XOR, отрицание и т. Д. Как вы проиллюстрировали, CNF часто противоречит этой цели "естественности", потому что выражение длиннее и часто повторяет подвыражения.

В качестве теоретического примечания, в худшем случае неограниченная булева формула, содержащая n операторов, может преобразоваться в формулу CNF, длина которой экспоненциально по n. Так что CNF потенциально может взорвать формулу на очень большое количество. Последовательность примеров, иллюстрирующих это поведение:

• (A & B) | (C & D) ==
  (A | C) & (A | D) & (B | C) & (B | D).
• (A & B) | (C & D) | (E & F) ==
  (A | C | E) & (A | C | F) & (A | D | E) & (A | D | F) & (B | C | E) & (B | C | F) & (B | D | E) & (B | D | F).
• (A & B) | (C & D) | (E & F) | (G & H) ==
  (A | C | E | G) & (A | C | E | H) & (A | C | F | G) & (A | C | F | H) & (A | D | E | G) & (A | D | E | H) & (A | D | F | G) & (A | D | F | H) & (B | C | E | G) & (B | C | E | H) & (B | C | F | G) & (B | C | F | H) & (B | D | E | G) & (B | D | E | H) & (B | D | F | G) & (B | D | F | H).