The idea of reasoning by following simple rules provides an attractively straightforward characterization of cognition. However, production systems can be very difficult to design in ways that are guaranteed to always work. In this problem, you will write some functions to help you work with production systems, and then you will use those functions to reason about several different sets of rules.

Part A (1 point)

We will represent a set of beliefs using Python sets: each element in the set corresponds to a true proposition. For example, the following belief states that 'a' and 'b' are true propositions:

example_belief = {'a', 'b'}

As a quick refresher, Python sets are unique, unordered collections of objects. You can check if an item is in a set with the in keyword:

'a' in example_belief

'c' in example_belief

You can add new things to the set using the .add() method, for example:

example_belief.add('c')
example_belief

So, our beliefs will be represented using sets, and we will represent the rules of our production system using a list of 2-tuples. Each tuple contains a condition and a result. The rule can be applied if the condition is present in the set of beliefs; if the rule is applied, then the result should be added to the set of beliefs. For example, the following belief again consists of 'a' and 'b', and the rules state that "if a, then b" and that "if c, then d":

example_belief = {'a', 'b'}
example_rules = [('a', 'b'), ('c', 'd')]

To help visualize the rules a bit better, here is a function called print_rules that will print out each rule on a separate line:

def print_rules(rules):
    for rule in rules:
        print(str(rule[0]) + " --> " + str(rule[1]))

print_rules(example_rules)

Using the representation of beliefs and rules specified above, write a function called match that searches through a given list of rules to find a rule that is triggered by the given set of beliefs.

def match(belief, rules):
    """Determine whether a rule is triggered by the given set of beliefs.

    The *first* rule in the list of rules that is triggered should be
    returned (and you should only ever return one rule, even if multiple are
    triggered). If no rule is triggered, None should be returned.

    A rule should only be triggered if it adds something new to the set of 
    beliefs: for example, if the beliefs are `{'a', 'b'}`, and there is only 
    one rule, `('a', 'b')`, then it should not be triggered because it 
    doesn't add anything new. If the beliefs were just `{'a'}`, however, then 
    the rule *should* be triggered because it would add `b` to the set of 
    beliefs.

    Hint: you should be able to do this in four lines of code (or less),
    including the return statement.
    
    Parameters
    ----------
    belief : set
        A set of true propositions.
    rules : list of tuples
        A list of tuples, such that for each tuple, the first element implies
        the second (but not vice versa).
        
    Returns
    -------
    The first rule (tuple) that was triggered, or None if no rules were triggered.
    
    """
    # YOUR CODE HERE
    raise NotImplementedError()

Check that your function behaves as expected, based on the example given above:

print(match({'a'}, [('a', 'b')])) # should print ('a', 'b')

print(match({'a', 'b'}, [('a', 'b')])) # should print None

# add your own test cases here!

from nose.tools import assert_equal

# check that a --> b is triggered
assert_equal(match({'a'}, [('a', 'b')]), ('a', 'b'))

# check that nothing is triggered, because 'b' does not trigger any rules
assert_equal(match({'b'}, [('a', 'b')]), None)

# check that nothing is triggered, because 'a' and 'b' are already in the belief
assert_equal(match({'a', 'b'}, [('a', 'b')]), None)

# check that a --> b is triggered
assert_equal(match({'a'}, [('a', 'b'), ('b', 'c')]), ('a', 'b'))

# check that b --> c is triggered
assert_equal(match({'a', 'b'}, [('a', 'b'), ('b', 'c')]), ('b', 'c'))

# check that nothing is triggered, because 'a', 'b', and 'c' are already in the belief
assert_equal(match({'a', 'b', 'c'}, [('a', 'b'), ('b', 'c')]), None)

print("Success!")

Part B (1.5 points)

Now that we have a way to trigger rules based on a set of beliefs, we want to engage in a process called forward chaining. The idea behind forward chaining is that we want execute rules that are triggered by our beliefs, and to continue triggering rules until no more can be triggered. For example, if we have:

rules = [("belief1", "belief2"), ("belief2", "belief3")]
belief = {"belief1"}

To start out, we have belief_1, but we also have a rule "if belief_1, then belief_2". So, we should update our belief with belief_2.

Then, we have another rule that says "if belief_2, then belief_3". Because our belief now consists of both belief_1 and belief_2 (due to triggering the first rule), this second rule should also be triggered, and should add belief_3 to our total set of beliefs.

Write a function, forward_chain, to automatically perform forward chaining using a given set of initial beliefs and rules.

def forward_chain(belief, rules):
    """Fully execute a set of given rules that match a given belief, until
    no more new rules are triggered. Returns a new set of beliefs (without
    changing the original set of beliefs) based on which rules were
    triggered.

    Note: this function should call the `match` function you implemented
    in the first part of this problem.

    Hint: you should be able to do this in 8 lines of code, including the
    return statement.
    
    Parameters
    ----------
    belief : set
        A set of true propositions.
    rules : list of tuples
        A list of tuples, such that for each tuple, the first element implies
        the second (but not vice versa).
        
    Returns
    -------
    tuple of (new_belief, triggered_rules):
        new_belief is an updated set of true propositions, and triggered_rules
        is the list of rules that were triggered, in order.
        
    """
    # YOUR CODE HERE
    raise NotImplementedError()

Make sure your function does in fact perform full forward chaining -- if there are two matching rules, but only one matches at the beginning, they should still both be triggered:

b, r = forward_chain({'a'}, [('a', 'b'), ('b', 'c')])
print_rules(r) # should print both 'a --> b' and 'b --> c'
b              # should be {'a', 'b', 'c'}

# add your own test cases here!

"""Check that `forward_chain` uses the `match` function."""
from nose.tools import assert_raises
orig_match = match
del match
try:
    assert_raises(NameError, forward_chain, {'a'}, [('a', 'b')])
finally:
    match = orig_match

print("Success!")

"""Ensure that the new belief is a different object from the original belief."""
b1 = {'a'}
b2 = forward_chain(b1, [('a', 'b')])
assert_equal(b1, {'a'})
assert_equal(b2, ({'a', 'b'}, [('a', 'b')]))

print("Success!")

"""Check that full forward chaining works."""
b, r = forward_chain({'a'}, [('a', 'b'), ('b', 'c'), ('c', 'd')])
assert_equal(b, {'a', 'b', 'c', 'd'})
assert_equal(r, [('a', 'b'), ('b', 'c'), ('c', 'd')])

b, r = forward_chain({'a'}, [('b', 'c'), ('c', 'd'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c', 'd'})
assert_equal(r, [('a', 'b'), ('b', 'c'), ('c', 'd')])

b, r = forward_chain({'a'}, [('a', 'c'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c'})
assert_equal(r, [('a', 'c'), ('a', 'b')])

b, r = forward_chain({'b'}, [('a', 'b'), ('b', 'c')])
assert_equal(b, {'b', 'c'})
assert_equal(r, [('b', 'c')])

b, r = forward_chain({'a', 'b', 'c'}, [('b', 'c'), ('b', 'a'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c'})
assert_equal(r, [])

b, r = forward_chain(set(), [('b', 'c'), ('b', 'a'), ('a', 'b')])
assert_equal(b, set())
assert_equal(r, [])

print("Success!")

Part C (0.5 points)

Imagine you have a small sprinkler that can water your grass, but does not reach the path you walk on, or your car. However, if it rains, then the car and the path both get wet. The sprinkler definitely comes on if the appropriate switch is flipped. We might try to capture this information in a production system as follows:

IF switch is flipped THEN sprinkler is on
IF sprinkler is on THEN grass is wet
IF it is raining THEN car is wet
IF it is raining THEN path is slippery
IF it is raining THEN grass is wet

Or, in Python:

rules_1 = [
    ('switch is flipped', 'sprinkler is on'),
    ('sprinkler is on', 'grass is wet'),
    ('it is raining', 'car is wet'),
    ('it is raining', 'path is slippery'),
    ('it is raining', 'grass is wet')
]

If you knew that the switch was flipped (but nothing else), what would you conclude about the states of the sprinkler, grass, car, and the path? Use your forward_chain function to find out:

# perform forward chaining on the belief that 'switch is flipped'
belief_1, triggered_rules_1 = forward_chain({'switch is flipped'}, rules_1)

# print which rules were triggered
print_rules(triggered_rules_1)

# show the final belief
belief_1

In words, what is your belief about the state of the grass? What is your belief about the state of the car?

YOUR ANSWER HERE

Part D (0.5 points)

These rules only seem to tell part of the story. We should be able to make other inferences too. For example, if the sprinkler came on, the switch must have been flipped. We could imagine defining another production system, with a completely different set of rules getting at this:

IF sprinkler is on THEN switch is flipped
IF car is wet THEN it is raining
IF path is slippery THEN it is raining
IF grass is wet THEN it is raining

Or, in Python:

rules_2 = [
    ('sprinkler is on', 'switch is flipped'),
    ('car is wet', 'it is raining'),
    ('path is slippery', 'it is raining'),
    ('grass is wet', 'it is raining')
]

If you knew only that the grass was wet, what would you conclude? Again, you can use your forward_chain function to find out:

# perform forward chaining on the belief that 'path is slippery'
belief_2, triggered_rules_2 = forward_chain({'grass is wet'}, rules_2)

# print which rules were triggered
print_rules(triggered_rules_2)

# show the final belief
belief_2

What conclusion(s) do you draw? Intuitively, do they seem like valid or reasonable inferences to make? Explain.

YOUR ANSWER HERE

Part E (1.5 points)

The previous set of rules is still unsatisfying, though: if we know it is raining, we should be able to draw further conclusions, but those rules do not allow us to do that. To try to get around that, let's try combining both sets of rules:

IF switch is flipped THEN sprinkler is on
IF sprinkler is on THEN grass is wet
IF it is raining THEN car is wet
IF it is raining THEN path is slippery
IF it is raining THEN grass is wet
IF sprinkler is on THEN switch is flipped
IF car is wet THEN it is raining
IF path is slippery THEN it is raining
IF grass is wet THEN it is raining

If you observed sprinkler was on, what would you conclude? You can again use forward_chain:

# perform forward chaining on the belief that 'sprinkler is on'
belief_3, triggered_rules_3 = forward_chain({'sprinkler is on'}, rules_1 + rules_2)

# print which rules were triggered
print_rules(triggered_rules_3)

# show the final belief
belief_3

Do these conclusions match your intuitions about what inferences should or should not be valid? Explain your reasoning.

YOUR ANSWER HERE

What does this tell us about the limitations of production systems?

YOUR ANSWER HERE

---

Before turning this problem in remember to do the following steps:

1. Restart the kernel (Kernel$\rightarrow$Restart)
2. Run all cells (Cell$\rightarrow$Run All)
3. Save (File$\rightarrow$Save and Checkpoint)

After you have completed these three steps, ensure that the following cell has printed "No errors". If it has not printed "No errors", then your code has a bug in it and has thrown an error! Make sure you fix this error before turning in your problem set.

print("No errors!")