0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

Moreover, take a look at

$\exists Y \forall X q(X,Y) \models \forall X \exists Y q(X,Y)$

You cannot arbitrarily switch the quantifiers since the premise talks only about one element Y, while in the conclusion Y depends on X.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Emon May 14 '17 at 8:12

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.