aima.core.logic.propositional.inference

Class PLFCEntails

java.lang.Object

aima.core.logic.propositional.inference.PLFCEntails

public class PLFCEntails
extends java.lang.Object

Artificial Intelligence A Modern Approach (3rd Edition): page 258.

 
 function PL-FC-ENTAILS?(KB, q) returns true or false
   inputs: KB, the knowledge base, a set of propositional definite clauses
           q, the query, a proposition symbol
   count ← a table, where count[c] is the number of symbols in c's premise
   inferred ← a table, where inferred[s] is initially false for all symbols
   agenda ← a queue of symbols, initially symbols known to be true in KB
   
   while agenda is not empty do
     p ← Pop(agenda)
     if p = q then return true
     if inferred[p] = false then
        inferred[p] ← true
        for each clause c in KB where p is in c.PREMISE do
            decrement count[c]
            if count[c] = 0 then add c.CONCLUSION to agenda
   return false
 
 

Figure 7.15 the forward-chaining algorithm for propositional logic. The agenda keeps track of symbols known to be true but not yet "processed". The count table keeps track of how many premises of each implication are as yet unknown. Whenever a new symbol p from the agenda is processed, the count is reduced by one for each implication in whose premise p appears (easily identified in constant time with appropriate indexing.) If a count reaches zero, all the premises of the implication are known, so its conclusion can be added to the agenda. Finally, we need to keep track of which symbols have been processed; a symbol that is already in the set of inferred symbols need not be added to the agenda again. This avoids redundant work and prevents loops caused by implications such as P ⇒ Q and Q ⇒ P.

Author:

Ciaran O'Reilly, Ravi Mohan, Mike Stampone

Constructor Summary

Constructors

Constructor and Description
PLFCEntails()

Method Summary

Modifier and Type	Method and Description
protected PropositionSymbol	conclusion(Clause c)
protected void	decrement(java.util.Map<Clause,java.lang.Integer> count, Clause c)
protected java.util.Queue<PropositionSymbol>	initializeAgenda(java.util.Map<Clause,java.lang.Integer> count)
protected java.util.Map<Clause,java.lang.Integer>	initializeCount(KnowledgeBase kb)
protected java.util.Map<PropositionSymbol,java.util.Set<Clause>>	initializeIndex(java.util.Map<Clause,java.lang.Integer> count, java.util.Map<PropositionSymbol,java.lang.Boolean> inferred)
protected java.util.Map<PropositionSymbol,java.lang.Boolean>	initializeInferred(KnowledgeBase kb)
boolean	plfcEntails(KnowledgeBase kb, PropositionSymbol q) PL-FC-ENTAILS?(KB, q) The forward-chaining algorithm for propositional logic.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PLFCEntails

public PLFCEntails()

Method Detail

plfcEntails

public boolean plfcEntails(KnowledgeBase kb,
                           PropositionSymbol q)

PL-FC-ENTAILS?(KB, q)
The forward-chaining algorithm for propositional logic.

Parameters:

kb - the knowledge base, a set of propositional definite clauses.

q - q, the query, a proposition symbol

Returns:

true if KB |= q, false otherwise.

Throws:

java.lang.IllegalArgumentException - if KB contains any non-definite clauses.

initializeCount

protected java.util.Map<Clause,java.lang.Integer> initializeCount(KnowledgeBase kb)

initializeInferred

protected java.util.Map<PropositionSymbol,java.lang.Boolean> initializeInferred(KnowledgeBase kb)

initializeAgenda

protected java.util.Queue<PropositionSymbol> initializeAgenda(java.util.Map<Clause,java.lang.Integer> count)

initializeIndex

protected java.util.Map<PropositionSymbol,java.util.Set<Clause>> initializeIndex(java.util.Map<Clause,java.lang.Integer> count,
                                                                                 java.util.Map<PropositionSymbol,java.lang.Boolean> inferred)

decrement

protected void decrement(java.util.Map<Clause,java.lang.Integer> count,
                         Clause c)

conclusion

protected PropositionSymbol conclusion(Clause c)