During my course in logic I encountered this problem:
Determine whether the following set of sentences is satisfiable or not. If not, use natural deduction to prove contradiction.
S = {∃x(R(x, x) ∧ ∀yQ(x, y)), ¬∃x((∃yR(x, y)) ∧ Q(x, x))}
From theory, we know that a set of sentences is satisfiable if there exists an interpretation that is a model of all sentences in a set.
Now I'm not that experienced with predicate logic, and it takes me quite some time to come up with an interpretation to satisfy all the sentences, and I noticed that I waste too much time trying to come up with an interpretation, even though it is entirely possible that the set is not satisfiable.
For example I spent so much time trying to find an interpretation for the following set of sentences too:
S = {∀x∃y(R(x, y) ∧ P(y)), ∃zP(z), ∀x(P(x) ⇒ ∀y¬R(y, x))}
By the way, both of these sets are not satisfiable, which can be proven by finding a contradiction.
So how would you go about solving this problem? Would you first try to make an interpretation, and if that doesn't work, try to prove contradiction by natural deduction, or vice versa?
Is there any "inner feeling" when you see these problems for the first time and say to yourselves "Ah, this must be (un)satisfiable!"?
What I would probably do first is think about how an interpretation of your sentences would have to be behave. If you're lucky, that might lead you to a contradiction (after which you can look for a syntactic proof of contradiction in natural deduction if you wish). If you aren't led to contradiction then you can start thinking about what elements have to exist to make the interpretation work and try to build a small example.
As an example, let's think about your first set of sentences, $\{\exists x (R(x, x) \wedge \forall y Q(x, y)), \neg \exists x ((\exists y R(x, y)) \wedge Q(x, x))\}$.
In an interpretation of that set of sentences the first sentence must be true. It's an existential sentence, so let's give a name to the thing it says exists. To avoid clashing with variables elsewhere, I'll call this thing $a$. So we know that $R(a, a)$ and we know that $\forall y Q(a, y)$. So far the only thing we know we can plug in for $y$ there is $a$ again; maybe later we'll need to do something else, but for now let's take note of the fact that we have $Q(a, a)$.
Now let's look at the second sentence in your set. It says that a certain kind of object can't exist, specifically, there is no $x$ such that $Q(x, x)$ and for some $y$ $R(x, y)$. Oh, but look at what we already know! We already know that $R(a, a)$ and $Q(a, a)$. In particular, we know $Q(a, a)$ and $\exists y R(a, y)$. So $a$ is the kind of element that the second sentence says shouldn't exist.
So we've shown that if the first sentence is true then the second one can't be. Now that we know the set is inconsistent we can go about looking for a formal proof in natural deduction if we're so inclined.
In a case where the set is consistent the same kind of thinking might lead us to discover that we can make all the sentences true with just a few elements, in which case we can explicitly write down an interpretation.
There's no guarantee that working out consequences like this will lead us, in a reasonable amount of time, to either a contradiction or a construction of an interpretation (if there were, a lot of math would be a lot easier than it is!). Still, I think it's a good strategy (and it will very often work in introductory exercises).