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

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

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

Пусть $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}$ тоже будет её моделью.

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

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

Напомним построение из этого доказательства. Пусть $F \Rightarrow \left(\varphi_{X} \rightarrow y\right)$. Последовательность $\tau$ вместе с множествами продуктов $X_{i}$, получаемых из $X$ с помощью $\tau_{i}$, строится по шагам:

• Шаг $0$: $\tau_{0}=\varnothing$, $X_{0}=X$.

• Шаг $1$: $\tau_{1}=\left\{ t \in F : L_{t} \subseteq X_{0}\right\}$, $X_{1}=X_{0} \cup \left\{ b_{t} : t \in \tau_{1}\right\}$.

• Шаг $i+1$: пусть уже определены $\tau_{i}$ и $X_{i}$. Положим $\tau_{i+1}^{\prime }=\left\{ t \in \left(F \backslash \tau_{i}\right) : L_{t} \subseteq X_{i}\right\}$, $X_{i+1}=X_{i} \cup \left\{ b_{t} : t \in \tau_{i+1}^{\prime }\right\}$ и $\tau_{i+1}=\left(\tau_{i}, \tau_{i+1}^{\prime }\right)$ (процессы внутри $\tau_{i+1}^{\prime }$ упорядочиваются произвольным образом). Если $y \in X_{i+1}$ или $X_{i}=X_{i+1}$, то полагаем $\tau =\tau_{i+1}$ и заканчиваем процедуру.

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

Теорема 38: Алгоритм Замыкание$(X, F)$ возвращает множество $\operatorname {cl}(X, F)$, а алгоритм ПрямаяВолна$(X, y, F)$ выдаёт ответ «да» тогда и только тогда, когда $F \Rightarrow \left(\varphi_{X} \rightarrow y\right)$.

Указание. Пусть $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$.

Пример 25: $A=\left\{ a, b, c, d, e, f, g, h\right\}$, $X=\left\{ b, f\right\}$, а множество процессов $F$ состоит из следующих шести процессов:

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

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

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

Теорема 39: Алгоритм ОптЗам$(X, F)$ строит замыкание $\operatorname {cl}(X, F)$.

Указание. Пусть $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$.