Structure satisfiability and entailment

117 Views Asked by At

Let $Fv[\phi]$ be the free variables of $\phi$. Suppose there are 2 formulas $A,B$ such that $Fv[A] \subseteq \{x,y\}$ and $Fv[B] \subseteq \{x,y\}$.

Prove/Disprove: $T \nvdash A\wedge B$ iff there exists a structure $M$ such that $M\models T \cup \neg(A\wedge B)$

I'm pretty sure it is wrong. My reasoning is that if that even though there is no structure such that when $ M \models T$, then $M \models A \wedge B$, that doesn't necessarily mean that there is no variable assignment $v$ such that $M, v \models A \wedge B$. So what we need is formulas such that for each structure $M$ that models $T$ there exists an assignment $v_1$ such that $M, v_1 \models A \wedge B$, and also and assignment $v_2$ such that $M, v_2 \not\models A \wedge B$. However, I cannot find such formulas and I'd like an example.

thanks

1

There are 1 best solutions below

0
On BEST ANSWER

Found a counterexample:

$$T= \emptyset$$

$$ A = B = p(x)\vee\neg p(y)$$

works here