Calculate the number of models of a KB

Question

Suppose we had a domain with two individuals, $x$ and $y$. Suppose we had two predicate symbols $p$ and $q$ and three constants $a$, $b$, and $c$. Suppose we had the knowledge base KB defined by:

• $p(X) \leftarrow q(X)$
• $q(a)$

How many of these interpretations are models of KB?

So we know that in total there are 128 interpretations (Models and non-models).

• Constants $a,b,c$ can have two different individuals $\{x,y\}$: $2^3 = 8$
• There are two possible values $\{true,false\}$ each for: $\pi(p(x)), \pi(p(y))$: $2^2 = 4$
• There are two possible values $\{true,false\}$ each for: $\pi(q(x)), \pi(q(y))$: $2^2 = 4$
• $8 \cdot 4 \cdot 4 = 128$

But now we have to subtract all the interpretations that are not acceptable (no models) from 128. Supposedly the solution should be 24, but I cannot wrap my head around it.

Answer 1

Here's how to count the models:

• There are two options for $a$. Denote the option not chosen by $\bar{a}$ (so if $a = x$ then $\bar{a} = y$, and if $a = y$ then $\bar{a} = x$).
• There is one option for $p(a),q(a)$: both have to hold.
• There are three options for $p(\bar{a}),q(\bar{a})$.
• There are two options each for $b,c$.

In total, we get $2 \cdot 1 \cdot 3 \cdot 2 \cdot 2 = 24$.

Answer 2

These are all the acceptable interpretations for a model of the KB.