Steven C. Shaffer

Copyright 2020, by Shaffer Media Enterprises LLC

About the author

Steven Shaffer is an Associate Teaching Professor of computer science and engineering at Penn State, University Park. He has been using and teaching artificial intelligence techniques for over 20 years.

Preface

This mini-book will take you step-by-step through coding your own simple rule-based expert system. This version uses Python, but once you have mastered the basics, it should be easy enough to translate your knowledge into most other languages.

While you’re still reading the free introduction part, let me be clear: This mini-book goes step by step through the development of a relatively simple backward chaining rule-based expert system. The purpose is to explain the concepts from a code-literate standpoint. This book uses a single example and does not contain information on unification algorithms. The purpose of this book is to explain the concept of rule-based expert systems to someone who understands coding but has no other training in the subject. I use an example with built-in rules and global variables in order to make the example clear (without confounding details). This is not production code. If you already understand how rule-based expert systems work, please do not buy this book.

People have kind of forgotten about rule-based systems as a topic, but they can be extremely useful for certain kinds of tasks and are not hard to code. If you are a coder, the explanations should make sense to you. No explanations of Python syntax are given, so this is not for the novice programmer. This book is not for the purist or the researcher, it’s an introductory book for people who want a basic understanding of how rule-based systems work.

Also, I suggest that you read up at least a little bit on the concept of rule based systems; just search for the phrase “introduction to rule-based systems” in your favorite search engine, and/or at least read the Wikipedia article entitled “rule-based system” and follow some of the links from there.

With that said, I feel confident that if you spend a few hours going through this tutorial, you will gain a solid knowledge of the mechanics of backward chaining rule based systems. If you want a copy of the source code, follow the instructions towards the end of this mini-book. However, I believe that you’re better off typing it in as you go – you will understand it better that way.

Once you’ve walked through this tutorial, you can add the code you need for your own purposes.

Please note: It’s very hard to get program code to display properly in an e-format; I’ve done the best I can. If reading this as an e-book, I suggest that you read most of this book in landscape mode to keep the code from wrapping strangely. In addition, no amount of planning will make the code appear on convenient page breaks, so I have abandoned any attempt at controlling this.

Also note: The example code here comes with no warrantee of any kind. They’re just educational examples!

The basic idea of a rule-based system is to create a series of rules that define or describe a decision-making process, and then to execute the rules in a way that a decision is made. For this mini-book, I’ve identified the following scenario:

To graduate, a student must have had a theory class, a database class, advanced programming and an English class. Theory classes include either data structures or automata theory. You must take a two-course sequence in data structures (460 and 461) to fulfill the data structures component, or take the two-course sequence in automata theory (470 and 471) to satisfy the automata component. In addition to the theory class requirement, you have to satisfy the database requirement (450 or 451), and have taken at least one of the advanced programming courses from the list 350, 351, or 352. Finally, you have to satisfy the English component by taking one English course from the list of eng101, eng102, eng103.

---

Note: There is an alternate scenario at the end, using the same base code.

---

These rules are stored in simple strings in a list as shown below:

rules = [
"graduate:- has_theory AND has_database AND has_advprog AND has_english",
"has_theory:- has_datastruct OR has_automata",
"has_database:- cs450 OR cs451",
"has_datastruct:- cs460 AND cs461",
"has_automata:- cs470 AND cs471",
"has_advprog:- cs350 OR cs351 OR cs352",
"has_english:- eng101 OR eng102 OR eng103"
]

Of course, these rules could easily be read from a file (and should be). For this example, I will just include them at the top of the program.

Next, we need some facts. Whereas the rules apply to all circumstances, the facts differ from case to case. In this case, the student has taken eng101, cs450, cs491, cs352 and cs460. These facts, which could easily be stored in a file, are stored globally as follows:

facts = [
"eng101",
"cs450",
"cs491",
"cs352",
"cs460"
]

The main goal of the program will be to work backwards from the goal, trying to “prove” that graduation is true. In order to do that, we will have to process the rules into parts and (recursively) process the parts as rules themselves.

---

Note: If you don’t already understand recursion, I suggest that you read up on the concept. Alternatively, you can learn something about recursion just by following along in this mini-book.

---

For the main process, we just do the following (from here on, new code lines will be shown in bold):

prove("graduate", 0)
print("FACTS:")
for f in facts:
    print(f)

So, we call a function called prove, along with two parameters: what we are trying to prove and the depth of the recursion (starting at zero). The depth is mostly used so that the output will be readable. Here is an example of the output (so you know where this is going); the most important lines are bolded.

PROVE graduate
   PROVE has_theory
      PROVE has_datastruct
         PROVE cs460
         cs460 is true
         PROVE cs461
         cs461 is false
      has_datastruct is false
      PROVE has_automata
         PROVE cs470
         cs470 is false
         PROVE cs471
         cs471 is false
      has_automata is false
   has_theory is false
   PROVE has_database
      PROVE cs450
      cs450 is true
      PROVE cs451
      cs451 is false
   has_database is true
   PROVE has_advprog
      PROVE cs350
      cs350 is false
      PROVE cs351
      cs351 is false
      PROVE cs352
      cs352 is true
   has_advprog is true
   PROVE has_english
      PROVE eng101
      eng101 is true
      PROVE eng102
      eng102 is false
      PROVE eng103
      eng103 is false
   has_english is true
graduate is false
FACTS:
eng101
cs450
cs491
cs352
cs460
has_database
has_advprog
has_english

So, the student cannot graduate because s/he has not fulfilled the theory requirement. Don’t worry if it’s not clear what’s happening here; I’ll go through it again at the end. In general, though, what this shows is that in order to prove graduate, we have to prove the sub-goals of has_theory, has_database, has_advprog, and has_english. For each of these sub-goals, there is either a list of courses (connected by AND or OR) or there is a sub-sub-goal (as with has_theory, which requires either has_automata or has_datastruct). First of all, if what we have to prove is already in the list of facts, there’s not much to it. For example:

PROVE cs491
cs491 is true
FACTS:
eng101
cs450
cs491
cs352
cs460

This is what is called the base case for the recursion – this is how we avoid an infinite regress. Once we get to the level of facts, something is either True (i.e., it’s in the list of facts) or False (it’s not in the list of facts). Note that something might be true in real life but not “true” as far as the rule system is concerned. For example, maybe the student took cs460 but somehow it did not get on the list of facts. We can easily check if something is in the facts list by using just checking if it’s in the facts list. Here are the first few lines of the prove function:

…
def prove(goal, depth):
    print(("\t"*depth)+"PROVE "+goal)
    depth += 1
    onceTrue = False
    if goal in facts:
        onceTrue = True
    else:
…

As we enter the prove function, we print what we are trying to prove, tabbed in based on the depth of the recursion (the first depth level is zero). We add one to the level of recursion each time we step deeper into it. I use the variable onceTrue to indicate if the goal is ever proven; it’s named this because there could be several ways to try to prove something in a rule system, and if any of the ways works then that means that the goal was proven (note: we’ll see more on this later). If the thing we are trying to prove is already in the list of facts, it’s automatically proven and so we set onceTrue to True.

If everything we were trying to prove was in the fact list, this program would be way too easy to warrant this mini-book, so of course not everything will already be in the list of facts. So, next we have to break the rule up into sub-goals:

…
def findSubgoals(goal):
    subgoals = []
    findthis = goal + ":-"
    for r in rules:
        if r.find(findthis) != -1:
            subgoals.append(r[r.find(findthis)+len(findthis):].strip())
    return subgoals

def prove(goal, depth):
    print(("\t"*depth)+"PROVE "+goal)
    depth += 1
    onceTrue = False
    if goal in facts:
        onceTrue = True
    else:
        subgoals = findSubgoals(goal)
…

The findSubgoals function looks through the list of rules, looking for the string goal+”:-“ which indicates a rule to prove the goal. If it finds such a rule, the function adds the right-hand-side of the :- symbol to the list of sub-goals. (As mentioned, there may be more than one way to achieve a goal, so this returns a list.) The function returns the list of rules to prove the goal.

Back in the prove function, we now iterate through the list of sub-goals:

…
def prove(goal, depth):
    print(("\t"*depth)+"PROVE "+goal)
    depth += 1
    onceTrue = False
    if goal in facts:
        onceTrue = True
    else:
        subgoals = findSubgoals(goal)
        connective = "AND" # I'll explain this line below
        for g in subgoals:
            truthValue = None
            subgoal = g.split()
            printIt = True
            cnt = 1
            for s in subgoal:
…

We break each subgoal into a list of tokens (just using whitespace), set cnt (count) to 1, and start iterating through the tokens. Note then that the tokens can be one of three things: a fact, another sub-goal, or a logical connective (AND or OR). The “cheap” way to handle the logical connectives is to make use of the fact that, as binary connectives, they have to appear on the “even” tokens (2, 4, 6, etc.). So, we can handle these this way:

…
def prove(goal, depth):
    print(("\t"*depth)+"PROVE "+goal)
    depth += 1
    onceTrue = False
    if goal in facts:
        onceTrue = True
    else:
        subgoals = findSubgoals(goal)
        connective = "AND"
        for g in subgoals:
            truthValue = None
            subgoal = g.split()
            printIt = True
            cnt = 1
            for s in subgoal:
                if cnt % 2 == 0:
                    if s not in ["AND", "OR"]:
                        print("#Error 31: Syntax error on " + s)
                        exit(1)
                    else:
                        connective = s
                else:
…

So, every alternate token must be an AND or an OR or else we have a syntax error. (Yes, there are more dynamic ways to handle this kind of error, but that would take us off track. This is not production code!) A few lines above we have initialized the connective to AND to give it a value which is the most restrictive and will work if there is only one piece to the rule we are processing.

Note: This program doesn’t process parentheses and so all connectives are processed left-to-right. Adding parentheses involves tokenizing the string to look for these and going down a level of recursion to process the sub-expression. Adding that here would make the example less clear. Complex OR statements can be handled by having multiple rules for proving something (as mentioned above and demonstrated below).

Next, we have to process the sub-goals, as shown below:

…
def prove(goal, depth):
    print(("\t"*depth)+"PROVE "+goal)
    depth += 1
    onceTrue = False
    if goal in facts:
        onceTrue = True
    else:
        subgoals = findSubgoals(goal)
        connective = "AND"
        for g in subgoals:
            truthValue = None
            subgoal = g.split()
            printIt = True
            cnt = 1
            for s in subgoal:
                if cnt % 2 == 0:
                    if s not in ["AND", "OR"]:
                        print("#Error 31: Syntax error on " + s)
                        exit(1)
                    else:
                        connective = s
                else:
                    truthval = prove(s, depth)
                    conditionalSave(s, truthval) # Explained below
                    if truthValue is None:
                        truthValue = truthval
                    elif connective == "AND":
                        truthValue = truthValue and truthval
                    elif connective == "OR":
                        truthValue = truthValue or truthval
                    else:
                        print("Error 42: Syntax error on " + s)
                        exit(1)      
                cnt += 1
…

So, if we get to the else part, we have a sub-goal we need to prove. To do so, we call prove (recursively) with the new (+1) depth and get back a truth value. If appropriate we save it to the facts list (more on that in a moment). Then, there are one of three legitimate states for the truth value:

1. There is nothing else to logically connect it to and so the truth value for the entire statement (so far), called truthValue, is the same as the truth value for this one sub-goal (truthval).
2. There are other sub-goals involved with an existing truth value, and the current connective is AND, so we and the new truth value (truthval) with the overall truth value (truthValue).
3. There are other sub-goals involved with an existing truth value, and the current connective is OR, so we or the new truth value (truthval) with the overall truth value (truthValue).

Note: Again, note that this is left-to-right resolution of the truth values.

Note: If you find these variable names to be confusing, you’re welcome to change them.

Also, as a bookkeeping item, note that cnt is incremented every time through the loop (for s in subgoal). This means that whether the item is a logical connective or a sub-goal, the count will keep incrementing.

Once we have looped through all of the sub-goals, we check if truthValue is True and, if so, we update onceTrue, which gets the value of True if any of the ways of proving the goal have been successful:

…
                    truthval = prove(s, depth)
                    conditionalSave(s, truthval)
                    if truthValue is None:
                        truthValue = truthval
                    elif connective == "AND":
                        truthValue = truthValue and truthval
                    elif connective == "OR":
                        truthValue = truthValue or truthval
                    else:
                        print("Error 42: Syntax error on " + s)
                        exit(1)      
                cnt += 1
            if truthValue == True:
                onceTrue = True
…

At the end of the prove function we print the results (tabbed in for readability) and return onceTrue (indicating if the goal state has been proven true via any path through the rules):

    print(("\t"*depth)+goal+" is "+ ("true" if onceTrue else "false"))
    return onceTrue

One thing that I said above that I would explain is the conditionalSave function. What this does is simply add a new fact to the facts list if it is true and if it isn’t already in the facts list, as shown below:

def conditionalSave(fact, truthval):
    if truthval == True:
        if fact not in facts:
            facts.append(fact)

This has two uses; one is easy and obvious and the other is more subtle. The easy reason for it is so that the user can see at the end what sub-goals were proven. The more subtle reason, and one that goes beyond this small mini-book, is that sometimes you have to run rule sets multiple times to ensure that everything that is provable comes out proven. So, in certain circumstances, you would run (for example) the prove(“graduate”) call in a loop until nothing in the facts list changes. This is usually only necessary if you are doing what’s called forward chaining – a topic that perhaps will be the subject of another mini-book.

To conclude, let’s look at the output and trace through what is going on:

PROVE graduate <== This is what we are trying to prove
   PROVE has_theory <== The student has to fulfill the theory requirement
      PROVE has_datastruct <== Can fulfill theory with data structures
         PROVE cs460 <== First data structures course
         cs460 is true <== Has it!
         PROVE cs461 <== Second data structures course
         cs461 is false <== Does not have it!
      has_datastruct is false <== So, did not fulfill data structures
      PROVE has_automata <== Another way to fulfill the theory requirement
         PROVE cs470 <== First automata course
         cs470 is false <== Does not have it!
         PROVE cs471 <== Second automata course
         cs471 is false <== Also does not have this one
      has_automata is false <== Does not fulfill the automata requirement
   has_theory is false <== So, does not fulfill the theory requirement
   PROVE has_database <== Student has to fulfill the database requirement
      PROVE cs450 <== One of the two choices for the database requirement
      cs450 is true <== Student has this one!
      PROVE cs451 <== Other database course they could take
      cs451 is false <== Doesn't have this one
   has_database is true <== Having one of the database courses is enough
   PROVE has_advprog <== Same situation as the database requirement
      PROVE cs350
      cs350 is false
      PROVE cs351
      cs351 is false
      PROVE cs352
      cs352 is true
   has_advprog is true
   PROVE has_english <== Same situation as the database requirement
      PROVE eng101
      eng101 is true
      PROVE eng102
      eng102 is false
      PROVE eng103
      eng103 is false
   has_english is true
graduate is false <== Has all except the theory requirement
FACTS: <== List of facts about the student
eng101
cs450
cs491
cs352
cs460
has_database
has_advprog
has_english

You could easily adjust the program to only show where things fail, as in:

has_datastruct is FALSE
has_automata is FALSE
has_theory is FALSE
graduate is FALSE
FACTS:
eng101
cs450
cs491
cs352
cs460
has_database
has_advprog
has_english

This is just a few minor adjustments around the print statements in the program.

---

Advertisement — Take a break and take a look!

APPEALING: A dark comedy about a serious subject

Christine, a young attorney on the brink of death, finds herself at the gates of heaven and hell. Having summarily received a sentence to hell, she demands an appeal. This sets her on a path of spiritual discovery, shepherded by three strangely familiar characters.

It should be noted that this film is psychological and spiritual in focus, but definitely not a mainstream Christian film. The film does contain adult themes and some strong language.

Visit www.AppealingFilm.com to watch!

---

Alternative rule set

As an example of how this exact same program can be used to solve an entirely different kind of problem, I present the totally made up and not medically based diagnosis rule set for a “virusX”:

rules = [
"virusX:- difficulty_breathing AND fever",
"virusX:- dry_cough AND tiredness AND congestion",
"virusX:- dry_cough AND fever",
"virusX:- fever AND sore_throat AND congestion"
]

facts = [
"fever",
"dry_cough",
"congestion"
]

If you run the same program as above with these rules and facts, you will get the following results:

PROVE virusX
   PROVE difficulty_breathing
      difficulty_breathing is false
   PROVE fever
      fever is true
   PROVE dry_cough
      dry_cough is true
   PROVE tiredness
      tiredness is false
   PROVE congestion
      congestion is true
   PROVE dry_cough
      dry_cough is true
   PROVE fever
      fever is true
   PROVE fever
      fever is true
   PROVE sore_throat
      sore_throat is false
   PROVE congestion
      congestion is true
   virusX is true

FACTS:
fever
dry_cough
congestion

As you can see, this new data set works as expected. This rule set is interestingly different than the first one in that it defines four different ways to prove virusX instead of using a single statement with a bunch of ORs. For example, the above rule set gives the same result as this one:

rules = [
"virusX:- method1 OR method2 OR method3 OR method4",
"method1:- difficulty_breathing AND fever",
"method2:- dry_cough AND tiredness AND congestion",
"method3:- dry_cough AND fever",
"method4:- fever AND sore_throat AND congestion"
]

In the end, this shows why, in a strict sense, the OR is not required at all. Anything you can do with an OR could be done with multiple rules. However, having the OR makes the rules more readable.

---

And that, dear readers, is how a simple rule based system works!

---

Important points

• Of course, a nice interface or at least loading the data from files would be nicer if you actually wanted to use the rule system.
• This kind of rule system is most often seen these days embedded within other software as opposed to being public-facing in itself.
• Try adding parentheses! Beware, though, that the code will get a lot harder to follow.
• One thing that is clearly missing is a NOT logical operator. Adding this pretty much requires you to add parentheses, which will definitely make your code harder to follow (but the rule system much more powerful).
• Based on Boolean logic, you can do any logic you need just with a NAND operator. So, you could have a very complete rule system by trashing AND and OR and just implementing NAND. In my experience, though, this is not a very intuitive logical operator for most people.
• You might notice that the program keeps looking through a goal even when it is full of ORs and one of the sub-goals has already come back False. You can code around this, but it will require pre-processing the goal string (not hard).
• Use your imagination and natural curiosity! Hours of fun can be had by all!

 

Full program code

This mini-book was intended to give you a boost in understanding how rule systems work by looking at the code, instead of all the theory. Yes, the theory is important, but it’s not necessary to understand the fundamental principles involved. I hope that I’ve succeeded in my mission!

Below is the full program code. I strongly urge you to read the text and follow along with the development of the code if you really want to understand it. Note that it is only about 80 lines long.

Enjoy!

Copyright, 2020, by Steven C. Shaffer and Shaffer Media Enterprises, LLC

You may use this code as a basis for your own learning or as the starting place for your own projects (academic or commercial). Do not reproduce or publish in whole or in part without the express permission of the author. The code comes with no warrantee whatsoever.

'''
# DATA SET ONE
rules = [
"graduate:- has_theory AND has_database AND has_advprog AND has_english",
"has_theory:- has_datastruct OR has_automata",
"has_database:- cs450 OR cs451",
"has_datastruct:- cs460 AND cs461",
"has_automata:- cs470 AND cs471",
"has_advprog:- cs350 OR cs351 OR cs352",
"has_english:- eng101 OR eng102 OR eng103"
]

facts = [
"eng101",
"cs450",
"cs491",
"cs352",
"cs460"
]

'''
DATA SET TWO
rules = [
"virusX:- difficulty_breathing AND fever",
"virusX:- dry_cough AND tiredness AND congestion",
"virusX:- dry_cough AND fever",
"virusX:- fever AND sore_throat AND congestion"
]

facts = [
"fever",
"dry_cough",
"congestion"
]

'''

'''

DATA SET THREE
rules = [
"virusX:- method1 OR method2 OR method3 OR method4",
"method1:- difficulty_breathing AND fever",
"method2:- dry_cough AND tiredness AND congestion",
"method3:- dry_cough AND fever",
"method4:- fever AND sore_throat AND congestion"
]

facts = [
"fever",
"dry_cough",
"congestion"
]

'''

def conditionalSave(fact, truthval):
    if truthval == True:
        if fact not in facts:
            facts.append(fact)

def findSubgoals(goal):
    subgoals = []
    findthis = goal + ":-"
    for r in rules:
        if r.find(findthis) != -1:
            subgoals.append(r[r.find(findthis)+len(findthis):].strip())
    return subgoals

def prove(goal, depth):
    print(("\t"*depth)+"PROVE "+goal)
    depth += 1
    onceTrue = False
    if goal in facts:
        onceTrue = True
    else:
        subgoals = findSubgoals(goal)
        connective = "AND"
        for g in subgoals:
            truthValue = None # nothing yet tested, open to anything
            subgoal = g.split()
            printIt = True
            cnt = 1
            for s in subgoal:
                if cnt % 2 == 0:
                    if s not in ["AND", "OR"]:
                        print("#Error 31: Syntax error on " + s)
                        exit(1)
                    else:
                        connective = s
                else:
                    truthval = prove(s, depth)
                    conditionalSave(s, truthval)
                    if truthValue is None:
                        truthValue = truthval
                    elif connective == "AND":
                        truthValue = truthValue and truthval
                    elif connective == "OR":
                        truthValue = truthValue or truthval
                    else:
                        print("Error 42: Syntax error on " + s)
                        exit(1)      
                cnt += 1
            if truthValue == True:
                onceTrue = True
    print(("\t"*depth)+goal+" is "+ ("true" if onceTrue else "false"))
    return onceTrue
prove("graduate", 0)
print("FACTS:")
for f in facts:
    print(f)