Пропозициональный ориентированный ациклический граф

Пропозициональный ориентированный ациклический граф (PDAG) — это структура данных , которая используется для представления булевой функции . Булева функция может быть представлена ​​в виде корневого ориентированного ациклического графа следующего вида:

Листья, помеченные ( ), представляют постоянную логическую функцию, которая всегда возвращает 1 (0). Лист, помеченный булевой переменной , интерпретируется как присваивание , т.е. он представляет собой булеву функцию, которая оценивается как 1 тогда и только тогда, когда . Булева функция, представленная -узлом, имеет значение 1 тогда и только тогда, когда логическая функция всех ее дочерних элементов оценивается как 1. Точно так же -узел представляет логическую функцию, которая дает значение 1 тогда и только тогда, когда Булева функция по крайней мере одного дочернего элемента оценивается как 1. Наконец, -узел представляет дополнительную логическую функцию своего дочернего элемента, т. е. ту, которая оценивается как 1, тогда и только тогда, когда логическая функция его дочернего элемента оценивается как 0.${\ Displaystyle \ сверху}$${\ Displaystyle \ бот}$${\ Displaystyle х}$${\ Displaystyle х = 1}$${\ Displaystyle х = 1}$${\ Displaystyle \ большой треугольник}$${\ Displaystyle \ большой треугольник вниз}$${\ Displaystyle \ алмаз}$

Каждая двоичная диаграмма решений (BDD) и каждая нормальная форма отрицания (NNF) также являются PDAG с некоторыми специфическими свойствами. Следующие изображения представляют булеву функцию :${\ Displaystyle е (х1, х2, х3) = - х1 * - х2 * - х3 + х1 * х2 + х2 * х3}$

BDD для функции f

PDAG для функции f, полученной из BDD

PDAG для функции f