# When is a knowledge base consistent?

I am studying a knowledge base (KB) from the book "Artificial Intelligence: A Modern Approach" (by Stuart Russell and Peter Norvig) and from this series of slides.

A formula is satisfiable if there is some assignment to the variables that makes the formula evaluate to true. For example, if we have the boolean formula $$A \land B$$, then the assignments $$A=\text{true}$$ and $$B=\text{true}$$ make it satisfiable. Right?

But what does it mean for a KB to be consistent? The definition (given at slide 14 of this series of slides) is:

a KB is consistent with formula $$f$$ if $$M(KB \cup \{ f \})$$ is non-empty (there is a world in which KB is true and $$f$$ is also true).

Can anyone explain this part to me with an example?

I will first recapitulate the key concepts which you need to know in order to understand the answer to your question (which will be very simple, because I will just try to clarify what is given as a "definition").

In logic, a formula is e.g. $$f$$, $$\lnot f$$, $$f \land g$$, where $$f$$ can be e.g. the proposition (or variable) "today it will rain". So, in a (propositional) formula, you have propositions, i.e. sentences like "today it will rain", and logical connectives, i.e. symbols like $$\land$$ (i.e. logical AND), which logically connect these sentences. The propositions like "today it will rain" can often be denoted by a single (capital) letter like $$P$$. $$f \land g$$ is the combination of two formulae (where formulae is the plural of formula). So, for example, suppose that $$f$$ is composed of the propositions "today it will rain" (denoted by $$P$$) or "my friend will visit me" (denoted by $$Q$$) and $$f$$ is defined as "I will play with my friend" (denoted by $$S$$). Then the formula $$f \land g = (P \lor Q) \land S$$. In general, you can combine formulae in any logically appropriate way.

In this context, a model is an assignment to each variable in a formula. For example, suppose $$f = P \lor Q$$, then $$w = \{ P=0, Q = 1\}$$ is a model for $$f$$, that is, each variable (e.g. $$P$$) is assigned either "true" ($$1$$) or "false" ($$0$$) but not both. (Note that the word model may be used to refer to different concepts depending on the context; again, in this context, you can simply think of a model as an assignment of values to the variables in a formula.)

Suppose now we define $$I(f, w)$$ to be a function that receives the formula $$f$$ and the model $$w$$ as input, and $$I$$ returns either "true" ($$1$$) or "false" ($$0$$). In other words, $$I$$ is a function that automatically tells us if $$f$$ is evaluated to true or false given the assignment $$w$$.

You can now define $$M(f)$$ to be a set of assignments (or models) to the formula $$f$$ such that $$f$$ is true. So, $$M$$ is a set and not just an assignment (or model). This set can be empty, it can contain one assignment or it can contain any number of assignments: it depends on the formula $$f$$: in some cases, $$M$$ is empty and, in other cases, it may contain say $$n$$ valid assignments to $$f$$, where by "valid" I mean that these assignments make $$f$$ evaluate to "true". For example, suppose we have formula $$f = A \land \lnot A$$. Then you can try to assign any value to $$A$$, but $$f$$ will never evaluate to true. In that case, $$M(f)$$ is an empty set, because there is no assignment to the variables (or propositions) of $$f$$ which make $$f$$ evaluate to true.

A knowledge base is a set of formulae $$\text{KB} = \{ f_1, f_2, \dots, f_n \}$$. So, for example, $$f_2 =$$ "today it will rain" and $$f_3 =$$ "I will go to school AND I will have lunch".

We can now define $$M(\text{KB})$$ to be the set of assignments to the formulae in the knowledge base $$\text{KB}$$ such that all formulae are true. If you think of the formulae in $$KB$$ as "facts", $$M(\text{KB})$$ is an assignment to these formulae in $$KB$$ such that these facts hold or are true.

In this context, we then say that a particular knowledge base (i.e., a set of formulae as defined above), denoted by $$\text{KB}$$, is consistent with formula $$f$$ if $$M(\text{KB} \cup \{ f \})$$ is a non-empty set, where $$\cup$$ means the union operation between sets: note that (as we defined it above) $$\text{KB}$$ is a set, and $$\{ f \}$$ means that we are making a set out of the formula $$f$$, so we are indeed performing an union operation on sets.

So, what does it mean for a knowledge base to be consistent? First of all, the consistency of a knowledge base $$\text{KB}$$ is defined with respect to another formula $$f$$. Recall that a knowledge base is a set of formulae, so we are defining the consistency of a set of formulae with respect to another formula.

When is then a knowledge base $$\text{KB}$$ consistent with a formula $$f$$? When $$M(\text{KB} \cup \{ f \})$$ is a non-empty set. Recall that $$M$$ is an assignment to the variables in its input such that its inputs evaluate to true. So, $$\text{KB}$$ is consistent with $$f$$ when there is a set of assignments of values to the formulae in $$\text{KB}$$ and an assignment of values to the variables in $$f$$ such that both $$\text{KB}$$ and $$f$$ are true. In other words, $$\text{KB}$$ is consistent with $$f$$ when both all formulae in $$\text{KB}$$ and $$f$$ can be true at the same time.

Here is a (very) brief wikipedia article on consistency in KB's, which should answer your question.

A KB is consistent, if it does not contain any contradictions, ie $$\lnot a$$ and $$a$$ are not both derivable from it. Which is pretty much common sense if you think about it.

If I have a formula $$f$$, for example "A is a trout $$\land$$ A lays eggs", and my KB contains "fish lay eggs" and "a trout is a fish", then, if $$f$$ is true, ie trout do lay eggs, that formula is consistent with my KB, which states that trout are fish and that fish lay eggs.

Edit: for a more formalised version, see nbro's answer.