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.


2 Answers 2


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$.


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

Acceptable interpretations


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.