Может ли конъюнктивная / дизъюнктивная нормальная форма быть представлена ​​в бинарном дереве?

Question

Я мог бы найти этот относительный вопрос Распределение И над ИЛИ в двоичном дереве (Conjunctive Normal Form)

Я не совсем уверен, каковы будут результаты представления двоичного дерева CNF для выражения this. A & B & C

AND
|- A
|- AND
   |-B
   |-C

Это правильно? Мой основной вопрос заключается в том, может ли двоичное представление CNF иметь несколько узлов AND в дереве, а не только один узел AND в качестве корневого. Насколько я понимаю, у нас могут быть некорневые узлы AND, если его родительский узел является узлом AND.

Похожий вопрос есть? Является ли это представление оптимальным? или полезно представлять их в n-nary дереве с одним корневым узлом AND? Оптимальность, которую я здесь ищу, заключается в построении и обходе дерева.

// Редактировать на основе комментария. Для простоты предположим, что not (~) Оператор является частью конечных узлов A, B или C. Это означает, что вам нужно беспокоиться о том, что оператор ~ является частью неконечных узлов, которые могут изменить структуру дерева при расширении в соответствии с законом Деморгана.

Answer 1

Минимальный BDD для вашего соединения:

BDD был создан с помощью этого онлайн-инструмента.

Для простого AND с тремя входами оптимизировать нечего. Узлы BDD создают цепочку.