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

Определить, каким из классов $\mathcal{S}_{0}, \mathcal{\mathcal{ S }_{ 1 }}, \mathcal{S}, \mathcal{L}, \mathcal{M}$ принадлежит булева функция $f\left(x_{1}, \ldots , x_{n}, y\right)$, задаваемая хорновской формулой $\left(x_{1} \wedge \cdots \wedge x_{n}\right) \rightarrow y$.

Пусть задано множество хорновских формул

Какие из следующих формул являются следствиями $F$?

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

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

Пусть $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$ эквивалентна конъюнкции хорновских формул тогда и только тогда, когда сокращённая ДНФ для $\neg \Phi$ содержит в каждой элементарной конъюнкции в точности одну переменную с отрицанием.

Доказать, что формула $\Phi$ эквивалентна конъюнкции хорновских формул тогда и только тогда, когда выполнены одновременно два условия:

Доказать, что формулы $a \oplus b$ и $a \vee b$ не эквивалентны никаким конъюнкциям хорновских формул.

Нормальной назовём формулу вида

где $\sigma_{i} \in \left\{ 0,1\right\}$ (см. раздел 6). Доказать, что каждая нормальная формула может быть получена как суперпозиция хорновских.

Доказать, что функция эквивалентна конъюнкции нормальных формул тогда и только тогда, когда она сохраняет единицу.

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

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

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

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

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

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

Используя алгоритм ОптЗам, определить, какая последовательность процессов приводит к получению $a$.