# Computational Intelligence

## Online Slides

### October 29, 2002

These are slides from Computational Intelligence, A Logical Approach, Oxford University Press, 1998. Copyright ©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1999-2002. You may prefer the pdf interface for which these slides were designed (you can read pdf files using the free acrobat reader).

# Chapter 7, Lecture 1

## Equality

• Sometimes two terms denote the same individual.
• Example: Clark Kent & superman. 4×4 & 11+5.
The projector we used last Friday & this projector.
• Ground term t1 equals ground term t2, written t1=t2, is true in interpretation I if t1 and t2 denote the same individual in interpretation I.

## Equality doesn't mean similarity

chair1 != chair2
chair_on_right = chair2
chair_on_right is not similar to chair2, it is chair2.

## Why is equality important?

• In a doctor's office, the doctor wants to know if a patient is the same patient that she saw last week (or is his twin sister).
• In a criminal investigation, the police want to determine if someone is the same person as the person who committed some crime.
• When buying a replacement switch, an electrician may want to know if it was built in the same factory as the switches that were unreliable. (And if it is a different switch to the one that was replaced the previous time).

## Allowing Equality Assertions

• Without equality assertions, the only thing that is equal to a ground term is itself.

This can be captured as though you had the assertion X=X. Explicit equality never needs to be used.

• If you allow equality assertions, you need to derive what follows from them. Either:
• axiomatize equality like any other predicate
• build special-purpose inference machinery for equality

## Axiomatizing Equality

X=X.
X=Y <- Y=X.
X=Z <- X=Y & Y=Z.

For each n-ary function symbol f there is a rule of the form

f(X_1,...,X_n)=f(Y_1,..., Y_n) <-
X_1=Y_1 & ··· & X_n=Y_n.

For each n-ary predicate symbol p, there is a rule of the form

p(X_1,...,X_n) <-
p(Y_1,..., Y_n) & X_1=Y_1 & ··· & X_n=Y_n.

## Special-Purpose Equality Reasoning

paramodulation: if you have t1=t2, then you can replace any occurrence of t1 by t2.

Treat equality as a rewrite rule, substituting equals for equals.

You select a canonical representation for each individual and rewrite all other representations into that representation.

Example: treat the sequence of digits as the canonical representation of the number.

Example: use the student number as the canonical representation for students.

## Unique Names Assumption

The convention that different ground terms denote different individuals is the unique names assumption.

For every pair of distinct ground terms t1 and t2, assume t1 != t2, where " != " means "not equal to."

Example: For each pair of courses, you don't want to have to state, math302 != psyc303, ...

Example: Sometimes the unique names assumption is inappropriate, for example 3+7 != 2×5 is wrong.

## Axiomatizing Inequality for the UNA

• c != c' for any distinct constants c and c'.
• f(X1,...,Xn) != g(Y1,...,Ym) for any distinct function symbols f and g.
• f(X1,...,Xn) != f(Y1,...,Yn) <- Xi != Yi, for any function symbol f. There are n instances of this schema for every n-ary function symbol f (one for each i such that 1 <= i <= n).
• f(X1,...,Xn) != c for any function symbol f and constant c.
• t != X for any term t in which X appears (where t is not the term X).

## Top-down procedure and the UNA

• Inequality isn't just another predicate. There are infinitely many answers to X != f(Y).
• If you have a subgoal t1 != t2, for terms t1 and t2 there are three cases:
• t1 and t2 don't unify. In this case, t1 != t2 succeeds.
• t1 and t2 are identical including having the same variables in the same positions. Here t1 != t2 fails.
• Otherwise, there are instances of t1 != t2 that succeed and instances of t1 != t2 that fail.

## Implementing the UNA

• Recall: in SLD resolution you can select any subgoal in the body of an answer clause to solve next.
• Idea: only select inequality when it will either succeed or fail, otherwise select another subgoal. Thus you are delaying inequality goals.
• If only inequality subgoals remain, and none fail, the query succeeds.

## Inequality Example

notin(X,[]).
notin(X,[H|T]) <- X != H & notin(X,T).
good_course(C) <- course(C) & passes_analysis(C).
course(cs312).
course(cs444).
course(cs322).
passes_analysis(C) <- something_complicated(C).
? notin(C,[cs312,cs322,cs422,cs310,cs402])
& good_course(C).

# Chapter 7, Lecture 2

## Complete Knowledge Assumption (CKA)

• Sometimes you want to assume that a database of facts is complete. Any fact not listed is false.
• Example: Assuming a database of enrolled(S,C) relations is complete, you can define empty_course(C).
• The definite clause RRS is monotonic: adding clauses doesn't invalidate a previous conclusion.
• With the complete knowledge assumption, the system is nonmonotonic: a conclusion can be invalidated by adding more clauses.

## CKA: propositional case

• Suppose the rules for atom a are
 a <- b1. ... a <- bn.
or equivalently: a <- b1 or ... or bn
• Under the CKA, if a is true, one of the bi must be true:

a -> b_1 or ... or b_n.

• Under the CKA, the clauses for a mean Clark's completion:

a <-> b_1 or ... or b_n

## CKA: Ground Database

Example: Consider the relation defined by:

student(mary).
student(john).
student(ying).

The CKA specifies these three are the only students:

student(X) <-> X=mary or X=john or X=ying.

To conclude ¬student(alan), you have to be able to prove
alan != mary & alan != john & alan != ying
This needs the unique names assumption.

## Clark Normal Form

The Clark normal form of the clause:

p(t_1,...,t_k) <- B

is the clause

p(V_1,...,V_k) <-
exist W_1...exist W_m V_1=t_1 & ... & V_k =t_k & B,

where V1,...,Vk are k different variables that did not appear in the original clause.

W1,...,Wm are the original variables in the clause.

## Clark normal form: example

• The Clark normal form of:

room(C,room208) <-
cs_course(C) & enrollment(C,E) & E<120.

is

room(X,Y) <- exist C exist E X=C & Y=room208 &
cs_course(C) & enrollment(C,E) & E<120.

## Clark's Completion of a Predicate

Put all of the clauses for p into Clark normal form, with the same set of introduced variables:

p(V_1,...,V_k) <- B_1
...
p(V_1,...,V_k) <- B_n

This is the same as: ~~ p(V1,...,Vk) <- B1 or ... or Bn.

Clark's completion of p is the equivalence

p(V_1,...,V_k) <-> B_1 or ... or B_n,

That is, p(V1,...,Vk) is true if and only if one Bi is true.

## Clark's Completion Example

Given the mem function:

mem(X,[X|T]).
mem(X,[H|T]) <- mem(X,T).

the completion is

mem(X,Y) <-> (exist T Y=[X|T]) or
(exist H exist T Y=[H|T] & mem(X,T))

## Clark's Completion of a KB

• Clark's completion of a knowledge base consists of the completion of every predicate symbol, along with the axioms for equality and inequality.
• If you have a predicate p defined by no clauses in the knowledge base, the completion is p <-> false. That is, ¬p.
• You can interpret negations in the bodies of clauses. `~` p means that p is false under the Complete Knowledge Assumption. This is called negation as failure.

## Using negation as failure

Previously we couldn't define empty_course(C) from a database of enrolled(S,C).

This can be defined using negation as failure:

empty_course(C) <-
course(C) &
`~` has_Enrollment(C).
has_Enrollment(C) <-
enrolled(S,C).

## Bottom-up NAF proof procedure

 C:={}; repeat either select "h <- b1 & ... & bm" in KB such that bi in C for all i, and h not in C; C:=C union {h} or select h such that for every rule "h <- b1 & ... & bm" in KB either for some bi, `~` bi in C or some bi= `~` g and g in C C:=C union { `~` h} until no more selections are possible

## Negation as failure example

p <- q & `~` r.
p <- s.
q <- `~` s.
r <- `~` t.
t.
s <- w.

## Top-Down NAF Procedure

• If the proof for a fails, you can conclude `~` a.
• Failure and success can be defined recursively:
• Suppose you have rules for atom a:
 a <- b1 ... a <- bn
If each body bi fails, a fails.
If one body, bi succeeds, a succeeds.
• A body fails if one of the conjuncts in the body fails.
A body succeeds if all of the conjuncts succeed.
• If a fails, `~` a succeeds. If a succeeds `~` a fails.

## Free Variables in Negation as Failure

Example:

p(X) <- `~` q(X) & r(X).
q(a).
q(b).
r(a).
r(c).

There is only one answer to the query ?p(X), namely X=c.

For calls to negation as failure with free variables, you need to delay negation as failure goals that contain free variables until the variables become bound.

## Floundering Goals

If the variables never become bound, a negated goal flounders.

In this case you can't conclude anything about the goal.

Example: Consider the clauses:

p(X) <- `~` q(X)
q(X) <- `~` r(X)
r(a)

and the query

?p(X).

# Chapter 7, Lecture 3

## Integrity Constraints

• In the electrical domain, what if we predict that a light should be on, but observe that it isn't?
What can we conclude?
• We will expand the definite clause language to include integrity constraints which are rules that imply false, where false is an atom that is false in all interpretations.
• This will allow us to make conclusions from a contradiction.
• A definite clause knowledge base is always consistent. This won't be true with the rules that imply false.

## Horn clauses

• An integrity constraint is a clause of the form

false <- a_1 & ... & a_k

where the ai are atoms and false is a special atom that is false in all interpretations.
• A Horn clause is either a definite clause or an integrity constraint.

## Negative Conclusions

• Negations can follow from a Horn clause KB.
• The negation of alpha, written ¬alpha is a formula that
• is true in interpretation I if alpha is false in I, and
• is false in interpretation I if alpha is true in I.
• Example:
KB={ false <- a & b. a <- c. b <- c.
} KB ¬c.

## Disjunctive Conclusions

• Disjunctions can follow from a Horn clause KB.
• The disjunction of alpha and beta, written alpha or beta, is
• true in interpretation I if alpha is true in I or beta is true in I (or both are true in I).
• false in interpretation I if alpha and beta are both false in I.
• Example:
KB={ false <- a & b. a <- c. b <- d.
} KB ¬c or ¬d.

## Questions and Answers in Horn KBs

• An assumable is an atom whose negation you are prepared to accept as part of a (disjunctive) answer.
• A conflict of KB is a set of assumables that, given KB imply false.
• A minimal conflict is a conflict such that no strict subset is also a conflict.

## Conflict Example

Example: If {c,d,e,f,g,h} are the assumables
KB={
 false <- a & b. a <- c. b <- d. b <- e.
}
• {c,d} is a conflict
• {c,e} is a conflict
• {c,d,e,h} is a conflict

## Using Conflicts for Diagnosis

• Assume that the user is able to observe whether a light is lit or dark and whether a power outlet is dead or live.
• A light can't be both lit and dark. An outlet can't be both live and dead:

false <=dark(L) &lit(L).

• Make ok assumable: assumable(ok(X)).
• Suppose switches s1, s2, and s3 are all up:
up(s1). up(s2). up(s3).

## Electrical Environment

lit(L) <=light(L)&ok(L)&live(L).
live(W) <=connected_to(W,W_1)&live(W_1).
live(outside)<=true.
light(l_1)<=true.
light(l_2)<=true.
connected_to(l_1,w_0)<=true.
connected_to(w_0,w_1) <=up(s_2)&ok(s_2).
connected_to(w_1,w_3) <=up(s_1)&ok(s_1).
connected_to(w_3,w_5) <=ok(cb_1).
connected_to(w_5,outside)<=true.

• If the user has observed l1 and l2 are both dark:
dark(l1).~dark(l2).
• There are two minimal conflicts:

{ok(cb_1),ok(s_1),ok(s_2),ok(l_1)}  and
{ok(cb_1),ok(s_3),ok(l_2)}.

• You can derive:

¬ok(cb_1) or ¬ok(s_1) or ¬ok(s_2) or ¬ok(l_1)
¬ok(cb_1) or ¬ok(s_3) or ¬ok(l_2).

• Either cb1 is broken or there is one of six double faults.

## Diagnoses

• A consistency-based diagnosis is a set of assumables that has at least one element in each conflict.
• A minimal diagnosis is a diagnosis such that no subset is also a diagnosis.
• Intuitively, one of the minimal diagnoses must hold. A diagnosis holds if all of its elements are false.
• Example: For the proceeding example there are seven minimal diagnoses: {ok(cb1)}, {ok(s1),ok(s3)}, {ok(s1),ok(l2)}, {ok(s2),ok(s3)},...

## Meta-interpreter to find conflicts

dprove(G,D0,D1) is true if list D0 is an ending of list D1 such that assuming the elements of D1 lets you derive G.

dprove(true,D,D).
dprove((A&B),D_1,D_3) <-
dprove(A,D_1,D_2) & dprove(B,D_2,D_3).
dprove(G,D,[G|D]) <- assumable(G).
dprove(H,D_1,D_2) <-
(H<=B) & dprove(B,D_1,D_2).
conflict(C) <- dprove(false,[],C).

## Example

false <=a.
a <=b &c.
b <=d.
b <=e.
c <=f.
c <=g.
e <=h &w.
e <=g.
w <=f.
assumable  d,f,g,h.

## Bottom-up Conflict Finding

• Conclusions are pairs <a,A>, where a is an atom and A is a set of assumables that imply a.
• Initially, conclusion set C={<a,{a}>:a is assumable}.
• If there is a rule h <- b1 & ... & bm such that
for each bi there is some Ai such that <bi,Ai> in C, then <h,A1 union ... union Am> can be added to C.
• If <a,A1> and <a,A2> are in C, where A1 strict subset A2, then <a,A2> can be removed from C.
• If <false,A1> and <a,A2> are in C, where A1 subset A2, then <a,A2> can be removed from C.

## Bottom-up Conflict Finding Code

 C:={:a is assumable }; repeat select clause "h <- b1 & ... & bm" in T such that in C for all i and there is no in C or in C such that A' subset A where A=A1 union ... union Am; C:=C union {} Remove any elements of C that can now be pruned; until no more selections are possible

## Integrity Constraints in Databases

• Database designers can use integrity constraints to specify constraints that should never be violated.
• Example: A student can't have two different grades for the same course.

false <-
The text passage is a set of slides from a lecture on computational intelligence, focusing on the concepts of equality, unique names assumption, complete knowledge assumption, and integrity constraints in logic programming and knowledge bases.
no_question

the passage does not contain any explicit mathematical questions or problems that require solving. it is primarily expository, explaining various concepts and their implications in the context of computational intelligence and logic programming.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Computational Intelligence

## Online Slides

### October 29, 2002

These are slides from Computational Intelligence, A Logical Approach, Oxford University Press, 1998. Copyright ©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1999-2002. You may prefer the pdf interface for which these slides were designed (you can read pdf files using the free acrobat reader).

# Chapter 7, Lecture 1

## Equality

• Sometimes two terms denote the same individual.
• Example: Clark Kent & superman. 4×4 & 11+5.
The projector we used last Friday & this projector.
• Ground term t1 equals ground term t2, written t1=t2, is true in interpretation I if t1 and t2 denote the same individual in interpretation I.

## Equality doesn't mean similarity

chair1 != chair2
chair_on_right = chair2
chair_on_right is not similar to chair2, it is chair2.

## Why is equality important?

• In a doctor's office, the doctor wants to know if a patient is the same patient that she saw last week (or is his twin sister).
• In a criminal investigation, the police want to determine if someone is the same person as the person who committed some crime.
• When buying a replacement switch, an electrician may want to know if it was built in the same factory as the switches that were unreliable. (And if it is a different switch to the one that was replaced the previous time).

## Allowing Equality Assertions

• Without equality assertions, the only thing that is equal to a ground term is itself.

This can be captured as though you had the assertion X=X. Explicit equality never needs to be used.

• If you allow equality assertions, you need to derive what follows from them. Either:
• axiomatize equality like any other predicate
• build special-purpose inference machinery for equality

## Axiomatizing Equality

X=X.
X=Y <- Y=X.
X=Z <- X=Y & Y=Z.

For each n-ary function symbol f there is a rule of the form

f(X_1,...,X_n)=f(Y_1,..., Y_n) <-
X_1=Y_1 & ··· & X_n=Y_n.

For each n-ary predicate symbol p, there is a rule of the form

p(X_1,...,X_n) <-
p(Y_1,..., Y_n) & X_1=Y_1 & ··· & X_n=Y_n.

## Special-Purpose Equality Reasoning

paramodulation: if you have t1=t2, then you can replace any occurrence of t1 by t2.

Treat equality as a rewrite rule, substituting equals for equals.

You select a canonical representation for each individual and rewrite all other representations into that representation.

Example: treat the sequence of digits as the canonical representation of the number.

Example: use the student number as the canonical representation for students.

## Unique Names Assumption

The convention that different ground terms denote different individuals is the unique names assumption.

For every pair of distinct ground terms t1 and t2, assume t1 != t2, where " != " means "not equal to."

Example: For each pair of courses, you don't want to have to state, math302 != psyc303, ...

Example: Sometimes the unique names assumption is inappropriate, for example 3+7 != 2×5 is wrong.

## Axiomatizing Inequality for the UNA

• c != c' for any distinct constants c and c'.
• f(X1,...,Xn) != g(Y1,...,Ym) for any distinct function symbols f and g.
• f(X1,...,Xn) != f(Y1,...,Yn) <- Xi != Yi, for any function symbol f. There are n instances of this schema for every n-ary function symbol f (one for each i such that 1 <= i <= n).
• f(X1,...,Xn) != c for any function symbol f and constant c.
• t != X for any term t in which X appears (where t is not the term X).

## Top-down procedure and the UNA

• Inequality isn't just another predicate. There are infinitely many answers to X != f(Y).
• If you have a subgoal t1 != t2, for terms t1 and t2 there are three cases:
• t1 and t2 don't unify. In this case, t1 != t2 succeeds.
• t1 and t2 are identical including having the same variables in the same positions. Here t1 != t2 fails.
• Otherwise, there are instances of t1 != t2 that succeed and instances of t1 != t2 that fail.

## Implementing the UNA

• Recall: in SLD resolution you can select any subgoal in the body of an answer clause to solve next.
• Idea: only select inequality when it will either succeed or fail, otherwise select another subgoal. Thus you are delaying inequality goals.
• If only inequality subgoals remain, and none fail, the query succeeds.

## Inequality Example

notin(X,[]).
notin(X,[H|T]) <- X != H & notin(X,T).
good_course(C) <- course(C) & passes_analysis(C).
course(cs312).
course(cs444).
course(cs322).
passes_analysis(C) <- something_complicated(C).
? notin(C,[cs312,cs322,cs422,cs310,cs402])
& good_course(C).

# Chapter 7, Lecture 2

## Complete Knowledge Assumption (CKA)

• Sometimes you want to assume that a database of facts is complete. Any fact not listed is false.
• Example: Assuming a database of enrolled(S,C) relations is complete, you can define empty_course(C).
• The definite clause RRS is monotonic: adding clauses doesn't invalidate a previous conclusion.
• With the complete knowledge assumption, the system is nonmonotonic: a conclusion can be invalidated by adding more clauses.

## CKA: propositional case

• Suppose the rules for atom a are
 a <- b1. ... a <- bn.
or equivalently: a <- b1 or ... or bn
• Under the CKA, if a is true, one of the bi must be true:

a -> b_1 or ... or b_n.

• Under the CKA, the clauses for a mean Clark's completion:

a <-> b_1 or ... or b_n

## CKA: Ground Database

Example: Consider the relation defined by:

student(mary).
student(john).
student(ying).

The CKA specifies these three are the only students:

student(X) <-> X=mary or X=john or X=ying.

To conclude ¬student(alan), you have to be able to prove
alan != mary & alan != john & alan != ying
This needs the unique names assumption.

## Clark Normal Form

The Clark normal form of the clause:

p(t_1,...,t_k) <- B

is the clause

p(V_1,...,V_k) <-
exist W_1...exist W_m V_1=t_1 & ... & V_k =t_k & B,

where V1,...,Vk are k different variables that did not appear in the original clause.

W1,...,Wm are the original variables in the clause.

## Clark normal form: example

• The Clark normal form of:

room(C,room208) <-
cs_course(C) & enrollment(C,E) & E<120.

is

room(X,Y) <- exist C exist E X=C & Y=room208 &
cs_course(C) & enrollment(C,E) & E<120.

## Clark's Completion of a Predicate

Put all of the clauses for p into Clark normal form, with the same set of introduced variables:

p(V_1,...,V_k) <- B_1
...
p(V_1,...,V_k) <- B_n

This is the same as: ~~ p(V1,...,Vk) <- B1 or ... or Bn.

Clark's completion of p is the equivalence

p(V_1,...,V_k) <-> B_1 or ... or B_n,

That is, p(V1,...,Vk) is true if and only if one Bi is true.

## Clark's Completion Example

Given the mem function:

mem(X,[X|T]).
mem(X,[H|T]) <- mem(X,T).

the completion is

mem(X,Y) <-> (exist T Y=[X|T]) or
(exist H exist T Y=[H|T] & mem(X,T))

## Clark's Completion of a KB

• Clark's completion of a knowledge base consists of the completion of every predicate symbol, along with the axioms for equality and inequality.
• If you have a predicate p defined by no clauses in the knowledge base, the completion is p <-> false. That is, ¬p.
• You can interpret negations in the bodies of clauses. `~` p means that p is false under the Complete Knowledge Assumption. This is called negation as failure.

## Using negation as failure

Previously we couldn't define empty_course(C) from a database of enrolled(S,C).

This can be defined using negation as failure:

empty_course(C) <-
course(C) &
`~` has_Enrollment(C).
has_Enrollment(C) <-
enrolled(S,C).

## Bottom-up NAF proof procedure

 C:={}; repeat either select "h <- b1 & ... & bm" in KB such that bi in C for all i, and h not in C; C:=C union {h} or select h such that for every rule "h <- b1 & ... & bm" in KB either for some bi, `~` bi in C or some bi= `~` g and g in C C:=C union { `~` h} until no more selections are possible

## Negation as failure example

p <- q & `~` r.
p <- s.
q <- `~` s.
r <- `~` t.
t.
s <- w.

## Top-Down NAF Procedure

• If the proof for a fails, you can conclude `~` a.
• Failure and success can be defined recursively:
• Suppose you have rules for atom a:
 a <- b1 ... a <- bn
If each body bi fails, a fails.
If one body, bi succeeds, a succeeds.
• A body fails if one of the conjuncts in the body fails.
A body succeeds if all of the conjuncts succeed.
• If a fails, `~` a succeeds. If a succeeds `~` a fails.

## Free Variables in Negation as Failure

Example:

p(X) <- `~` q(X) & r(X).
q(a).
q(b).
r(a).
r(c).

There is only one answer to the query ?p(X), namely X=c.

For calls to negation as failure with free variables, you need to delay negation as failure goals that contain free variables until the variables become bound.

## Floundering Goals

If the variables never become bound, a negated goal flounders.

In this case you can't conclude anything about the goal.

Example: Consider the clauses:

p(X) <- `~` q(X)
q(X) <- `~` r(X)
r(a)

and the query

?p(X).

# Chapter 7, Lecture 3

## Integrity Constraints

• In the electrical domain, what if we predict that a light should be on, but observe that it isn't?
What can we conclude?
• We will expand the definite clause language to include integrity constraints which are rules that imply false, where false is an atom that is false in all interpretations.
• This will allow us to make conclusions from a contradiction.
• A definite clause knowledge base is always consistent. This won't be true with the rules that imply false.

## Horn clauses

• An integrity constraint is a clause of the form

false <- a_1 & ... & a_k

where the ai are atoms and false is a special atom that is false in all interpretations.
• A Horn clause is either a definite clause or an integrity constraint.

## Negative Conclusions

• Negations can follow from a Horn clause KB.
• The negation of alpha, written ¬alpha is a formula that
• is true in interpretation I if alpha is false in I, and
• is false in interpretation I if alpha is true in I.
• Example:
KB={ false <- a & b. a <- c. b <- c.
} KB ¬c.

## Disjunctive Conclusions

• Disjunctions can follow from a Horn clause KB.
• The disjunction of alpha and beta, written alpha or beta, is
• true in interpretation I if alpha is true in I or beta is true in I (or both are true in I).
• false in interpretation I if alpha and beta are both false in I.
• Example:
KB={ false <- a & b. a <- c. b <- d.
} KB ¬c or ¬d.

## Questions and Answers in Horn KBs

• An assumable is an atom whose negation you are prepared to accept as part of a (disjunctive) answer.
• A conflict of KB is a set of assumables that, given KB imply false.
• A minimal conflict is a conflict such that no strict subset is also a conflict.

## Conflict Example

Example: If {c,d,e,f,g,h} are the assumables
KB={
 false <- a & b. a <- c. b <- d. b <- e.
}
• {c,d} is a conflict
• {c,e} is a conflict
• {c,d,e,h} is a conflict

## Using Conflicts for Diagnosis

• Assume that the user is able to observe whether a light is lit or dark and whether a power outlet is dead or live.
• A light can't be both lit and dark. An outlet can't be both live and dead:

false <=dark(L) &lit(L).

• Make ok assumable: assumable(ok(X)).
• Suppose switches s1, s2, and s3 are all up:
up(s1). up(s2). up(s3).

## Electrical Environment

lit(L) <=light(L)&ok(L)&live(L).
live(W) <=connected_to(W,W_1)&live(W_1).
live(outside)<=true.
light(l_1)<=true.
light(l_2)<=true.
connected_to(l_1,w_0)<=true.
connected_to(w_0,w_1) <=up(s_2)&ok(s_2).
connected_to(w_1,w_3) <=up(s_1)&ok(s_1).
connected_to(w_3,w_5) <=ok(cb_1).
connected_to(w_5,outside)<=true.

• If the user has observed l1 and l2 are both dark:
dark(l1).~dark(l2).
• There are two minimal conflicts:

{ok(cb_1),ok(s_1),ok(s_2),ok(l_1)}  and
{ok(cb_1),ok(s_3),ok(l_2)}.

• You can derive:

¬ok(cb_1) or ¬ok(s_1) or ¬ok(s_2) or ¬ok(l_1)
¬ok(cb_1) or ¬ok(s_3) or ¬ok(l_2).

• Either cb1 is broken or there is one of six double faults.

## Diagnoses

• A consistency-based diagnosis is a set of assumables that has at least one element in each conflict.
• A minimal diagnosis is a diagnosis such that no subset is also a diagnosis.
• Intuitively, one of the minimal diagnoses must hold. A diagnosis holds if all of its elements are false.
• Example: For the proceeding example there are seven minimal diagnoses: {ok(cb1)}, {ok(s1),ok(s3)}, {ok(s1),ok(l2)}, {ok(s2),ok(s3)},...

## Meta-interpreter to find conflicts

dprove(G,D0,D1) is true if list D0 is an ending of list D1 such that assuming the elements of D1 lets you derive G.

dprove(true,D,D).
dprove((A&B),D_1,D_3) <-
dprove(A,D_1,D_2) & dprove(B,D_2,D_3).
dprove(G,D,[G|D]) <- assumable(G).
dprove(H,D_1,D_2) <-
(H<=B) & dprove(B,D_1,D_2).
conflict(C) <- dprove(false,[],C).

## Example

false <=a.
a <=b &c.
b <=d.
b <=e.
c <=f.
c <=g.
e <=h &w.
e <=g.
w <=f.
assumable  d,f,g,h.

## Bottom-up Conflict Finding

• Conclusions are pairs <a,A>, where a is an atom and A is a set of assumables that imply a.
• Initially, conclusion set C={<a,{a}>:a is assumable}.
• If there is a rule h <- b1 & ... & bm such that
for each bi there is some Ai such that <bi,Ai> in C, then <h,A1 union ... union Am> can be added to C.
• If <a,A1> and <a,A2> are in C, where A1 strict subset A2, then <a,A2> can be removed from C.
• If <false,A1> and <a,A2> are in C, where A1 subset A2, then <a,A2> can be removed from C.

## Bottom-up Conflict Finding Code

 C:={:a is assumable }; repeat select clause "h <- b1 & ... & bm" in T such that in C for all i and there is no in C or in C such that A' subset A where A=A1 union ... union Am; C:=C union {} Remove any elements of C that can now be pruned; until no more selections are possible

## Integrity Constraints in Databases

• Database designers can use integrity constraints to specify constraints that should never be violated.
• Example: A student can't have two different grades for the same course.

false <-
user
The text passage is a set of slides from a lecture on computational intelligence, focusing on the concepts of equality, unique names assumption, complete knowledge assumption, and integrity constraints in logic programming and knowledge bases.

TYPE: NO_QUESTION

The passage does not contain any explicit mathematical questions or problems that require solving. It is primarily expository, explaining various concepts and their implications in the context of computational intelligence and logic programming.