# Logic proofs - Satisfiability

I need some help with some logic proofs. There are some questions that ask for the satisfiability of a formula and others that ask if the equivalence or consequence is true or false. ¿Are my answers correct?

Check Satisfiability

$$\forall X p(X) \rightarrow \exists X \neg p(X)$$ Invalid $$\forall X p(X) \vee \forall X \neg p(X)$$ Invalid

True or false questions $$\exists X \exists Y q(X,Y) \models \exists X q(X,X)$$ False $$\exists Y \forall X q(X,Y) \models \forall X \exists Y q(X,Y)$$ True $$\forall X p(X) \rightarrow \forall X q(X) \models \exists X ( p(X) \rightarrow q(X) )$$ True $$\forall X (p(X) \rightarrow q(X) \equiv \exists X p(X) \rightarrow \forall X q(X)$$ False $$\exists X(p(X) \rightarrow q(X)) \equiv \forall X p(X) \rightarrow \exists X q(X)$$ True $$\exists X( p(X,Y) \vee q(X) ) \equiv \exists X p(X,Y) \vee \exists X q(X)$$ True

Take care about satisfiability vs validity. The first two formulas are not valid, however it is asked whether they are satisfiable. In a model where $p(X)$ is false for all elements $x$ both formulas evaluate to true, thus they are satisfiable.
$\exists Y \forall X q(X,Y) \models \forall X \exists Y q(X,Y)$
• I agree with your answer for the first two ones, they are satisfiable but not valid. However I think $$\exists Y \forall X q(X,Y) \models \forall X \exists Y q(X,Y)$$ is correct, they are not equivalent because as you said the quantifiers cannot be switched arbitrarily but it is true that the second one is logic consecuence of the first one. – Emon May 14 '17 at 8:12