Forward Chaining: Deriving Conclusions from Rules, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.8 Free with a free account

Forward Chaining: Deriving Conclusions from Rules

Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.8 · lesson 46 of 6913 min · free with a free account

← Structuring Domain Knowledge for AI SystemsNext lesson: Backward Chaining: Reasoning from Goals to Evidence →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How rule engines fire Horn clauses from known facts to new conclusions.

  • Identify definite rules, facts and constraints as forms of Horn clauses
  • Trace the match, select and fire cycle of forward chaining
  • Compare conflict resolution strategies and explain why they leave the final facts unchanged
  • Explain why forward chaining is sound, terminating and complete on Horn knowledge bases

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,730 words). Read along, or search it.

Opening Question

A Greenhouse That Reasons from Data

In a smart greenhouse, the sensors report that the temperature is high, the sun is shining, and the soil is dry. Nobody has asked a question. Yet the controller should work out what follows. High heat in strong sun means heat stress, so the vents should open. Dry soil with no rain forecast means the plants need water, so the irrigation should start. And each conclusion can unlock the next. Starting from what's known, and applying rules to derive new facts, is called forward chaining. It's data-driven: new information triggers it, with no question posed first.

Rules and Facts

Definite Clauses and Horn Clauses

Forward chaining works on a knowledge base of facts and rules. Each rule has a conclusion, and a list of conditions that must all hold. We write them as, conclusion IF condition AND condition. HeatStress IF TempHigh AND Sunny. A fact is a rule with no conditions, like TempHigh. A Horn clause is a statement with at most one positive conclusion, and a definite clause has exactly one. Every rule in this form is a definite clause. Written as an OR statement, the heat rule says: HeatStress, or not TempHigh, or not Sunny.

Horn Clause Forms

Rules, Facts and Constraints

Horn clauses come in three forms. A definite rule has exactly one conclusion. A fact has a conclusion and no conditions. A constraint has no conclusion: its conditions just can't all be true together. For example, it must not be that Irrigate and Raining both hold. What's not Horn is a choice between conclusions: either A or B, or, if Fever then Flu or Cold. So Horn clauses can't say, one of these is true but I don't know which. In exchange, they cover eligibility rules, configuration rules, and diagnostic checklists, and they allow reasoning that's simple, fast, and complete.

Quick Check

A Choice of Conclusions Is Not Horn

Quick check. Which of these is not a Horn clause? Refund IF Damaged AND InWarranty? Fine OR Warning IF Late? Or, never both Open and Locked? Pause, and decide. Fine OR Warning IF Late. It offers a choice of two conclusions, so it has two positive literals. That's not Horn. The refund rule has exactly one conclusion, so it's a definite clause. And never both Open and Locked has no conclusion at all: it's a constraint, which is still Horn.

System Parts

The Match, Select and Fire Cycle

A rule-based system has three parts. The knowledge base holds the rules, which change rarely. The working memory holds the facts known right now, which grow as reasoning goes on, and as new data arrives. And the inference engine repeatedly applies the rules to the working memory, in a three-step cycle. Match every rule whose conditions are all in working memory. Select one. Fire it, by adding its conclusion to working memory. The new fact may let other rules match, so the cycle continues until nothing new can be added. Because facts trigger it, it's easy to feed with live data. When a sensor adds a fact, the engine carries on from where it was.

Worked Example

Deriving Scholarship Eligibility

Here's a small knowledge base about scholarships. R1: Eligible IF GoodGrades AND InNeed. R2: GoodGrades IF AwardWinner. R3: GoodGrades IF HighGPA. R4: InNeed IF LowIncome. R5: InNeed IF SupportsFamily. And the known facts are HighGPA and LowIncome. Cycle one: R3 fires, adding GoodGrades. Cycle two: R4 fires, adding InNeed. Cycle three: R1 fires, adding Eligible. Then no rule can add anything new, so it stops. R2 and R5 never fired, because AwardWinner and SupportsFamily never entered working memory. Forward chaining uses only the rules the facts support.

Algorithm

Conflict Sets and Refraction

The simplest algorithm is a loop. Put the known facts in working memory. Then repeat. Collect every rule whose conditions are all known and whose conclusion isn't yet. If there are none, stop, and report whether the query is known. Otherwise, choose one rule, add its conclusion, and stop early if that's the query. The rules that can fire at the same moment form the conflict set, and choosing among them is conflict resolution. And the condition, conclusion not yet known, means a rule never fires twice for the same result. That idea is called refraction.

Efficiency

Counters Make Forward Chaining Linear

Rescanning every rule on every pass is wasteful. A faster version gives each rule a counter: the number of its conditions not yet known. Each time a fact comes off the agenda, the counters of rules that mention it go down by one. A rule whose counter reaches zero adds its conclusion to the agenda. On the scholarship rules, with the query Eligible, the counters start at two for R1, and one for the rest. HighGPA drops R3 to zero, so GoodGrades joins the agenda. LowIncome drops R4, so InNeed joins. GoodGrades drops R1 to one, and InNeed drops it to zero: Eligible. Each counter changes at most once per condition, so the total work is proportional to the size of the knowledge base. That's one reason Horn knowledge bases are popular.

Quick Check

Missing F Blocks Fact E

Quick check. The facts are A and B. The rules are: C IF A AND B, D IF C, and E IF D AND F. Which facts are in working memory when forward chaining stops? A, B, C, and D? A, B, C, D, and E? Or only A, B, and C? Pause, and decide. A, B, C, and D. A and B fire the first rule, giving C, and C fires the second, giving D. The third rule needs F, which is never known, so E is never derived. And stopping at C would forget that D IF C can fire once C is known.

Conflict Resolution

Rule Order, Specificity, Recency and Priority

How should the engine choose from the conflict set? Rule order takes the first applicable rule in the list. It's simple and predictable. Specificity takes the rule with the most conditions, so a detailed rule overrides a general one. Recency takes the rule that uses the most recently added fact, following the latest developments. And priority takes the rule with the highest explicit priority number, so safety-critical rules act first. Does the choice change the answer? For a Horn knowledge base run until nothing new can be added, no. Every rule that can fire eventually fires, and facts are never removed. The strategy changes only the order of derivation. That matters when the engine stops early, when firing a rule triggers a real action, like opening a vent, or when time is limited.

Worked Example

Six Greenhouse Rules in Action

Back to the greenhouse, with six rules. R1: HeatStress IF TempHigh AND Sunny. R2: NeedsWater IF SoilDry AND NoRainForecast. R3: OpenVents IF HeatStress. R4: Irrigate IF NeedsWater AND WaterAvailable. R5: ShadeOn IF HeatStress AND NotWindy AND Sunny. And R6: CoverPlants IF FrostForecast. The sensors report six facts: TempHigh, Sunny, SoilDry, NoRainForecast, WaterAvailable, and NotWindy. Using rule order: in cycle one, R1 and R2 can fire, and R1 adds HeatStress. That makes R3 and R5 applicable too, so cycle two's conflict set holds three rules, and R2 adds NeedsWater. Then R3 adds OpenVents, R4 adds Irrigate, and R5 adds ShadeOn. Nothing else can fire. R6 never does, because FrostForecast isn't a known fact.

Comparison

Different Orders, Same Five Facts

Now compare strategies at cycle two, when R2, R3, and R5 can all fire. Rule order picks R2, since it comes first. Specificity picks R5, with three conditions. Recency picks R3: R3 and R5 both use the newest fact, HeatStress, and the tie goes to the earlier rule. And priority picks R3 if venting has the highest priority, because it's a safety action. Run each to the end, and the orders differ. Specificity derives ShadeOn second, and recency derives OpenVents second. But every strategy ends with the same five facts.

Variables

One Rule Covers Many Cases

Rules can also contain variables, so one rule covers many cases. Grandparent x, z IF Parent x, y AND Parent y, z. The engine matches the conditions against the facts, and each consistent match gives a conclusion. With Parent Ann Bob, Parent Bob Cara, and Parent Bob Dan, matching x as Ann, y as Bob, and z as Cara gives Grandparent Ann Cara. And z as Dan gives Grandparent Ann Dan. That matching is unification, from lesson six point six. The rest of forward chaining works just as before.

Quick Check

Counting the Grandparent Facts

Quick check. The facts are: Parent Eve Fay, Parent Fay Gus, Parent Fay Hal, and Parent Gus Ivy. How many Grandparent facts does the rule add? Two, three, or four? Pause, and decide. Three. Eve, Fay, Gus gives Grandparent Eve Gus. Eve, Fay, Hal gives Grandparent Eve Hal. And Fay, Gus, Ivy gives Grandparent Fay Ivy. Two misses that Fay is also a grandparent, through Gus. And no fourth chain exists: Hal and Ivy have no children here.

Guarantees

Sound, Terminating and Complete

Can we trust it? A procedure is sound if everything it derives really follows, complete if it derives everything that follows, and it terminates if it always stops. Forward chaining on Horn knowledge bases has all three. Sound: each firing applies a rule to facts already established. It terminates: there are finitely many symbols, each added at most once. Complete: when it stops, make every fact in working memory true, and every other symbol false. Take any rule. If all its conditions are true, it would have fired, so its conclusion is true too. So this assignment is a model of the knowledge base. Anything false in it doesn't follow. In the scholarship model, AwardWinner and SupportsFamily are false, and every rule still holds.

Limitations

Non-Horn Rules and Unasked Facts

Where does the guarantee end? First, if the knowledge base isn't Horn. Take A or B, C IF A, and C IF B. Checking all eight combinations, C is true in every one that fits. So C follows, yet forward chaining starts with no facts and fires nothing. Second, variables with function symbols can make the derivable facts infinite. Number of Zero, and, Number of Next x IF Number of x, never stops. Third, it derives everything that follows, including facts nobody asked about. With millions of student records, it works out all their consequences, just to answer one question about one student. When only a single question matters, that's wasteful. Backward chaining, the opposite strategy, starts from the question and works back to the evidence.

Key Takeaways

Data-Driven Rule Firing

To sum up. Forward chaining starts from known facts, and fires rules whose conditions hold, adding conclusions to working memory. Horn clauses, with at most one conclusion, keep that simple and efficient. The engine cycles through match, select, and fire, and counters make it linear. Conflict resolution changes the order, but never the final facts. And on Horn knowledge bases it's sound, terminating, and complete, though it may derive facts nobody asked for.

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Forward Chaining: Deriving Conclusions from Rules

What is forward chaining in AI?
Forward chaining is a data-driven inference method that starts from known facts and repeatedly fires rules whose conditions all hold, adding each conclusion to working memory until nothing new can be added. With HighGPA and LowIncome known, rules derive GoodGrades, then InNeed, then Eligible. New data, such as a sensor reading, can trigger it without anyone posing a question.
What is a Horn clause?
A Horn clause is a clause with at most one positive literal, meaning at most one conclusion. It comes in three forms: a definite rule with one conclusion and some conditions, a fact with a conclusion and no conditions, and a constraint with no conclusion. Fine OR Warning IF Late is not a Horn clause, because it offers a choice between two conclusions.
What is conflict resolution in a rule-based system?
Conflict resolution is how an inference engine chooses which rule to fire when several can fire at once, a group called the conflict set. Common strategies are rule order, specificity, recency and priority. On a Horn knowledge base run to completion, the strategy changes only the order of derivation, not the final facts, but it matters if the engine stops early or rules trigger real actions.
Is forward chaining complete?
Yes, on propositional Horn knowledge bases forward chaining is sound, terminating and complete. Outside that setting the guarantee can fail. Given A OR B, C IF A, and C IF B, the conclusion C follows, yet forward chaining fires nothing because A OR B is not Horn. Function symbols can also make the derivable facts infinite, as with Number(Zero) and Number(Next(x)) IF Number(x).

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →