2
$\begingroup$

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=true$ and $B= 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?

$\endgroup$
3
$\begingroup$

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.

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 this "model" has nothing to do with a "model" e.g. in machine learning! 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 not assignment to the variables or propositions of $f$ which make $f$ evaluate to true.

A "knowledge base" is a set of formulae $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(KB)$ to be the set of assignments to the formulae in the "knowledge base" such that all formulae are true. If you think of the formulae in $KB$ as "facts", $M(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 $KB$, is consistent with formula $f$ if $M(KB \cup \{ f \})$ is a non-empty set, where $\cup$ means the "union" operation between sets: note that (as we defined it above) $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" $KB$ is defined with respect to another formula $f$. Recall that a "knowledge base" is a set of formulae, so we are defining consistency of a set of formulae with respect to another formula.

When is then a "knowledge base" $KB$ consistent with a formula $f$? When $M(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, $KB$ is consistent with $f$ when there is a set of assignments of values to the formulae in $KB$ and an assignment of values to the variables in $f$ such that both $KB$ and $f$ are true. In other words, $KB$ is consistent with $f$ when both all formulae in $KB$ and $f$ can be true at the same time.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your definition of KB consistency is not consistent with my definition (which is highly based on the slides that OP linked us to). Your definition is not based on the relation with another formula. You based your answer on a Wikipedia article which doesn't cite any sources. $\endgroup$ – nbro Feb 10 at 14:12
  • $\begingroup$ True; my answer was a quick and informal one, which is why I then pointed to yours, which is better. We submitted our answers at the same time, otherwise I would've just upvoted yours instead of replying myself. $\endgroup$ – Oliver Mason Feb 11 at 9:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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