Give an interpretation where $$∃x(\neg P(x) ∨ Q(x)) \to (∃xP(x) ∧ ∀x\neg Q(x))$$ is false.
How does someone even begin with questions like this? I have interpreted it in my head and I kind of get it in a sense. But seems like the only thing I know is that since it is an implication, the only way it will be false is if True -> False. Can someone please help me continue?
This question is part of old exams I am solving.
The main strategy for finding a counter-model for a sentence in FOL is similar to the strategy you use to factor equations in algebra. You’re looking for a way to show a formula is falsifiable similarly to how you look for numbers and roots of polynomials that produce a polynomial expression.
It takes practice to learn the basics, and using straight-up model theory oftentimes confuses new learners since it has a lot of moving parts that are needed for a full semantics, but aren’t really needed to understand why a formula is or isn’t satisfiable. To that end, I prefer to use the method of semantic tableaux. There is always a way to make a counter-model based off of a semantic tableaux, but it is not always going to be the simplest. You can read about it here: https://en.m.wikipedia.org/wiki/Method_of_analytic_tableaux.
I’ll provide an example with the formula in question using a system similar to what is presented on Wikipedia. The ‘X’ to the left of a formula indicates that all available rules have been used for that formula, and so it is no longer usable. In practice, you wait to check it off until you’ve already applied the rule.
You start by negating the formula to find a counter-model.
X$\neg (∃x(¬P(x)∨Q(x))→(∃xP(x)∧∀x¬Q(x)))$
Then, applying the rule for a negated conditional, we have
X$∃x(¬P(x)∨Q(x))$
X$\neg (∃xP(x)∧∀x¬Q(x))$
The rule for a negated conjunction gives us
$\neg ∃xP(x) \lor \neg ∀x¬Q(x)$.
In general, rules for un-negated conjunctions and existentials, negated disjunctions, conditionals, and universals should be carried out first to make the tree neater and simpler. So, by the rule for the existential, we infer for a name $a$ not yet used
X$(\neg Pa \lor Qa)$.
Usually, disjunctions are done with branching, but I’ll just explain the last couple of steps in English due to formatting. One branch will have $\neg Pa$ on it and the other will have $Qa$. Then, we do the same with the other disjunction, making sure to have a branch with $\neg ∃xP(x)$ and the other with $\neg ∀x¬Q(x)$ on both sides of the existing branch. The existentials will need to instantiate to new names, and the negated universal will be transformed into $\exists x \neg \neg Qx$. Un-negated universals do not get an ‘X’. Once all of the rules are applied, you’ll have a counter-model for the formula in question.
In this case, a simpler counter-model can be created in a domain with just one element that has property $Q$ but does not have property $P$. Still, learning how to do semantic tableaux can help to demystify model theory and help you to be more efficient at coming up with counter-models.