Understanding Forward Chaining in Propositional Logic

 
Forward Chaining (propositional)
 
Recursive stack-based version of Back-chaining
using Propositional Logic
 
could be modified to
handle...
variables (using unification)
negation
context (fail if sub-goal is
repeated)
Backchain(KB,query)
 
stack 
{query} // initialize
 
return BC(KB,stack)
BC(KB,stack)
 
if stack empty, return True
 
goal 
 stack.pop()
 
if goal
KB, return BC(KB,stack) // a known fact
 
for each rule a
1
..a
n
goal in KB:
  
stack.push(a
1
..a
n
)
  
result 
 BC(KB,stack)
  
if result=True, return True
      remove 
a
1
..a
n
 from stack
 
return False
 
KB = {CanBikeToWork 
 CanGetToWork
CanDriveToWork 
 CanGetToWork
CanWalkToWork 
 CanGetToWork
HaveBike 
 
Sunny 
 CanBikeToWork
OwnCar 
 CanDriveToWork
HaveMoney 
 
RentCar 
 CanDriveToWork
HaveMoney 
 
TaxiAvailable 
 CanDriveToWork
Sunny 
 
CanWalkToWork
HaveUmbrella 
 
CanWalkToWork
Rainy, // facts
HaveBike,
HaveMoney,
RentCar 
}
 
query = CanGetToWork ?
 
 
1.
{CanGetToWork} // initialize goal stack with query
2.
{CanBikeToWork} // replace subgoal with rule 1
3.
{HaveBike,Sunny} // push antecedents for rule 4
4.
{Sunny} // HaveBike is fact, so pop it
5.
backtrack
 since Sunny in not a fact and can’t be proved
6.
{CanDriveToWork} // rule 2, another way CanGetToWork
7.
{OwnCar} // try rule 5
8.
backtrack
, not provable
9.
{HaveMoney,RentCar} // another way to prove
CanDriveToWork
10.
{RentCar} // pop HaveMoney since known fact
11.
{} // 
success
! empty goal stack, return True
 
 
Slide Note
Embed
Share

Forward chaining in propositional logic is a recursive, stack-based version of back-chaining that can be modified to handle variables using unification and negation context. By applying a set of rules and facts, the process aims to prove a given query by iteratively inferring new information. Illustrated steps demonstrate the application of forward chaining with a knowledge base and a specific query, showcasing how the algorithm deduces the possibility of reaching a desired goal through logical reasoning.


Uploaded on Aug 30, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Forward Chaining (propositional)

  2. Recursive stack-based version of Back-chaining using Propositional Logic could be modified to handle... variables (using unification) negation context (fail if sub-goal is repeated) Backchain(KB,query) stack {query} // initialize return BC(KB,stack) BC(KB,stack) if stack empty, return True goal stack.pop() if goal KB, return BC(KB,stack) // a known fact for each rule a1..an goal in KB: stack.push(a1..an) result BC(KB,stack) if result=True, return True remove a1..an from stack return False

  3. KB = {CanBikeToWork CanDriveToWork CanWalkToWork HaveBike Sunny OwnCar HaveMoney RentCar HaveMoney TaxiAvailable Sunny CanWalkToWork HaveUmbrella Rainy, // facts HaveBike, HaveMoney, RentCar } CanGetToWork CanGetToWork CanGetToWork CanBikeToWork CanDriveToWork CanDriveToWork CanDriveToWork CanWalkToWork query = CanGetToWork ?

  4. 1. {CanGetToWork} // initialize goal stack with query 2. {CanBikeToWork} // replace subgoal with rule 1 3. {HaveBike,Sunny} // push antecedents for rule 4 4. {Sunny} // HaveBike is fact, so pop it 5. backtracksince Sunny in not a fact and can t be proved 6. {CanDriveToWork} // rule 2, another way CanGetToWork 7. {OwnCar} // try rule 5 8. backtrack, not provable 9. {HaveMoney,RentCar} // another way to prove CanDriveToWork 10.{RentCar} // pop HaveMoney since known fact 11.{} // success! empty goal stack, return True

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#