13.3.3 Queries with Variables

Queries are used to ask whether some statement is a logical consequence of a knowledge base. With propositional queries, a user can ask yes-or-no queries. Queries with variables allow the users to ask for the individuals that make the query true.

An instance of a query is obtained by substituting terms for the variables in the query. Each occurrence of a variable in a query must be replaced by the same term. Given a query with free variables, an answer is either an instance of the query that is a logical consequence of the knowledge base, or “ $n o$ ”, meaning that no instances of the query logically follow from the knowledge base. Instances of the query are specified by providing values for the variables in the query. Determining which instances of a query follow from a knowledge base is known as answer extraction.

An answer of “no” does not mean that the query is false in the intended interpretation; it simply means that there is no instance of the query that is a logical consequence.

% $imm\_west(W,E)$ is true if room $W$ is immediately west of room $E$ .

	$\displaystyle{imm\_west(r101,r103).}$
	$\displaystyle{imm\_west(r103,r105).}$
	$\displaystyle{imm\_west(r105,r107).}$
	$\displaystyle{imm\_west(r107,r109).}$
	$\displaystyle{imm\_west(r109,r111).}$
	$\displaystyle{imm\_west(r131,r129).}$
	$\displaystyle{imm\_west(r129,r127).}$
	$\displaystyle{imm\_west(r127,r125).}$

% $imm\_east(E,W)$ is true if room $E$ is immediately east of room $W$ .

	$\displaystyle{imm\_east(E,W)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_west(W,E).}$

% $next\_door(R1,R2)$ is true if room $R1$ is next door to room $R2$ .

	$\displaystyle{next\_door(E,W)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_east(E,W).}$
	$\displaystyle{next\_door(W,E)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_west(W,E).}$

% $two\_doors\_east(E,W)$ is true if room $E$ is two doors east of room $W$ .

	$\displaystyle{two\_doors\_east(E,W)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_east(E,M)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_east(M,W).}$

% $west(W,E)$ is true if room $W$ is west of room $E$ .

	$\displaystyle{west(W,E)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_west(W,E).}$
	$\displaystyle{west(W,E)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {imm\_west(W,M)\wedge\mbox{}}$
	$\displaystyle\ \ \ \ {west(M,E).}$

Figure 13.2: A knowledge base about rooms

Example 13.13.

Consider the clauses of Figure 13.2. The person who wrote these clauses presumably has some meaning associated with the symbols, and has written the clauses because they are true in some, perhaps imaginary, world. The computer knows nothing about rooms or directions. All it knows are the clauses it is given; and it can compute their logical consequences.

The user can ask the following query:

\mbox{{ask}~{}}~{}imm\_west(r105,r107).

and the answer is yes. The user can ask the query

\mbox{{ask}~{}}~{}imm\_east(r107,r105).

and the answer is, again, yes. The user can ask the query

\mbox{{ask}~{}}~{}imm\_west(r205,r207).

and the answer is no. This means it is not a logical consequence, not that it is false. There is not enough information in the database to determine whether or not $r205$ is immediately west of $r207$ .

The query

\mbox{{ask}~{}}~{}next\_door(R,r105).

has two answers. One answer, with $R=r107$ , means $next\_door(r107,r105)$ is a logical consequence of the clauses. The other answer is for $R=r103$ . The query

\mbox{{ask}~{}}~{}west(R,r105).

has two answers: one for $R=r103$ and one for $R=r101$ . The query

\mbox{{ask}~{}}~{}west(r105,R).

has three answers: one for $R=r107$ , one for $R=r109$ , and one for $R=r111$ . The query

\mbox{{ask}~{}}~{}next\_door(X,Y).

has 16 answers, including

	$\displaystyle{X=r103,Y=r101}$
	$\displaystyle{X=r105,Y=r103}$
	$\displaystyle{X=r101,Y=r103}$
	$\displaystyle{\cdots.}$

Artificial Intelligence 2E

13.3.3 Queries with Variables

Example 13.13.

Artificial
Intelligence 2E