Хорновские формулы и задача получения продукции

Доказать, что каждое множество хорновских формул имеет модель, то есть интерпретацию, в которой все они истинны.

Доказать, что если КНФ в каждой элементарной конъюнкции содержит в точности одну переменную без отрицания, то она эквивалентна конъюнкции хорновских формул.

Пусть $J_{i}, i=1, \ldots , n$ — интерпретации. Назовём их пересечением интерпретацию $K=J_{1} \ldots J_{n}$ такую, что для любой переменной $x$ выполнено $K(x)=1$ тогда и только тогда, когда $J_{i}(x)=1$ для всех $i=1, \ldots , n$. Доказать, что если хорновская формула имеет модели $J_{i}, i=1, \ldots , n$, то их пересечение $K=J_{1} \ldots J_{n}$ тоже будет её моделью.

Доказать, что формула $Φ$ эквивалентна конъюнкции хорновских формул тогда и только тогда, когда её сокращённая КНФ содержит в каждой элементарной дизъюнкции в точности одну переменную без отрицания.

Доказать, что последовательность процессов $\tau_{i}$ в доказательстве теоремы 37 на стр. 121 определена корректно, то есть все исходные продукты каждого процесса в этой последовательности имеются перед его запуском.

Доказать теорему 38 на стр. 124.

Указание. Пусть $N_{k}$ — это значение $N$ после $k$ итераций основного цикла алгоритма Замыкание в строках $7-14$. Показать, что для каждого продукта $z \in \operatorname {cl}(X, F)$, который может быть получен из $X$ цепочкой процессов длины $k$ и менее, $z$ входит в $N_{k}$.

Алгоритм ПрямаяВолна $(X, y, F)$ позволяет ответить на вопрос о возможности производства $y$ из исходных продуктов $X$ с помощью процессов $F$, но не строит цепочку процессов, приводящую к $y$. Изменить алгоритм Замыкание $(X, F)$ так, чтобы по его результату для любого продукта $a \in \operatorname {cl}(X, F)$ можно было построить цепочку процессов, приводящую к $a$.

Назовём сложным технологическим процессом такой процесс $t$, который по набору исходных продуктов $L_{t}$ одновременно производит некоторое множество продуктов $B_{t}$ (а не один продукт $b_{t}$). Доказать, что сложному технологическому процессу соответствует конъюнкция хорновских формул.

Обобщить алгоритм Замыкание $(X, F)$ так, чтобы он строил замыкание $X$ относительно системы сложных технологических процессов $F$.

Определить, какая цепочка процессов в примере 25 на предшествующей странице приводит к получению $a$.

Используя алгоритм Замыкание, вычислить замыкание для набора исходных продуктов $X=\left\{ c, d\right\}$ и системы технологических процессов $F$ :

Определить, какая цепочка процессов приводит к получению $e$.

Доказать теорему 39 на стр. 127.

Указание. Пусть $N_{k}$ — это значение $N, A_{k}$ — значение $A$, а $C_{k}$ — значение $C$ после $k$ итераций основного цикла алгоритма ОптЗам в строках $17-29$. Показать, что

Изменить алгоритм ОптЗам таким образом, чтобы по его результату для любого продукта $a \in \operatorname {cl}(X, F)$ можно было построить цепочку процессов, приводящую к $a$.

Используя алгоритм ОптЗам, вычислить замыкание для набора исходных атрибутов $X=\left\{ a, f\right\}$ и следующей системы зависимостей $F$ :

Определить, какая цепочка процессов приводит к получению $h$.