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

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

• Листья обозначены значком $\top$ (истинный), $\bot$ (ложь) или логическую переменную.
• Нелистья $\bigtriangleup$ (логическое и), $\bigtriangledown$ (логическое или) и $\Diamond$ (логично нет).
• $\bigtriangleup$- и $\bigtriangledown$-узлы имеют хотя бы одного дочернего узла.
• $\Diamond$-узлы имеют ровно одного дочернего элемента.

Листья с надписью $\top$ ( $\bot$) представляют постоянную булеву функцию, значение которой всегда равно 1 (0). Лист, помеченный логической переменной $x$ интерпретируется как задание $x=1$, т. е. представляет собой логическую функцию, которая принимает значение 1 тогда и только тогда, когда $x=1$. Булева функция, представленная $\bigtriangleup$-узел — это узел, который оценивается как 1, если и только если булева функция всех его дочерних элементов оценивается как 1. Аналогично, $\bigtriangledown$-node представляет логическую функцию, которая оценивается как 1, тогда и только тогда, когда логическая функция хотя бы одного дочернего элемента оценивается как 1. Наконец, $\Diamond$-node представляет дополнительную логическую функцию своего дочернего элемента, т. е. ту, которая оценивается как 1, тогда и только тогда, когда булева функция его дочернего элемента оценивается как 0.

PDAG, BDD и NNF

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

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

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

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

См. также

• Структура данных
• Проблема логической выполнимости
• Предложение

Ссылки

• М. Вахтер и Р. Хенни, «Пропозициональные DAG: новый язык на основе графов для представления логических функций», KR'06, 10-я Международная конференция по принципам представления знаний и рассуждения, Лейк-Дистрикт, Великобритания, 2006 г.
• М. Вахтер и Р. Хэнни, «Проверка вероятностной эквивалентности с помощью пропозициональных DAG», Технический отчет iam-2006-001, Институт компьютерных наук и прикладной математики, Бернский университет, Швейцария, 2006 г.
• М. Вахтер, Р. Хенни и Дж. Джончи, «Надежность и диагностика модульных систем: новый вероятностный подход», DX'06, 18-й международный семинар по принципам диагностики, Пеньяранда-де-Дуэро, Бургос, Испания, 2006 г.