5
$\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=\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?

$\endgroup$
0

2 Answers 2

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

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.

$\endgroup$
0
$\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$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .