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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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