2
$\begingroup$

I know I must be getting stuck on notation. However, I'm having trouble following the logic in Example 1.2 in https://arxiv.org/pdf/cs/0611018.pdf. They define what preserving a propositional formula means.

So, I'm trying to understand a basic example. Take X = A or (Not B) or (Not C) as an example Horn Clause. Define the assignments f1 and f2 by f1(A) = f1(B) = f1(C) = true and f2(A) = f2(B) = f2(C) = false. Both f1 and f2 satisfy X.

What does it mean to say AND preserves X with respect f1 and f2?

$\endgroup$
2
$\begingroup$

In your example the assignment $f_1\wedge f_2$ is $(f_1\wedge f_2)(A)=f_1(A)\wedge f_2(A)=\text{True} \land \text{False} = \text{False}$. similarly: $(f_1\wedge f_2)(B)=(f_1\wedge f_2)(C)=\text{False}$ so actually $f_1\wedge f_2 \equiv f_2$.

As they define, AND is preserving $X$ if for every two assignments $f_1, f_2$ that satisfy $X$, the assignment $f_1 \wedge f_2$ (defined by $(f_1\wedge f_2)(v)=f_1(v)\wedge f_2(v)$) also satisfies $X$.

$\endgroup$
  • $\begingroup$ Thank you. I see now that $f_1\land f_2$ is defined componentwise. $\endgroup$ – Alex Williams Aug 14 '18 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.