<jupyter_start><jupyter_text>CSC421 Assignment 2 - Part I  Propositional Logic (5 points)  Author: <NAME> This notebook is based on the supporting material for topics covered in **Chapter 7 - Logical Agents** from the book *Artificial Intelligence: A Modern Approach.* You can consult and modify the code provided in logic.py and logic.ipynb for completing the assignment questions. This part does NOT rely on the provided code so you can complete it just using basic Python. ```Birds can fly, unless they are penguins and ostriches, or if they happen to be dead, or have broken wings, or are confined to cages, or have their feet stuck in cement, or have undergone experiences so dreadful as to render them psychologically incapable of flight Marvin Minsky ```  Introduction - Parsing and evaluating prefix logic expressions  In this assignment your task is to incrementally create a parser and evaluator for prefix logic expressions as well as implement simple model checking. **NOTE THAT THE GRADING IN THIS ASSIGNMENT IS DIFFERENT FOR GRADUATE STUDENTS AND THEY HAVE TO DO EXTRA WORK FOR FULL MARKS**  Question 1A (Minimum) CSC421 -  (1 point, CSC581C - 0 points) Your first task will be to write a simple evaluator of prefix logic expressions with constants. In prefix notation the operator precedes the operands and no operands are required. For example 5+3 in prefix notation is written + 5 3 or 5 * 2 + 3 would be written + * 5 2 3 or + * 5 2 * 3 4 is equivalent to (5 * 2) + (3 * 4).  As a first step we will consider very simple expressions with one operator and two constant operands. We will use 0 for false and 1 for true. The following logical connectives should be implemented (see Figure 7.8 in your book) (notice that for now there is no negation symbol ~): 1. &    (and), 3. |    (or), 4. =>   (implication) 5.   (biconditional) Example expressions: ```& 1 0  => 0 1  1 1 ```Your function should take as input a string with the prefix expression and return the result of evaluating the expression (basically a 1 for true and 0 for false). You can split a string to a list using .split[' ']. For this part of the assignment you only evaluate expressions with two constant operands i.e no nested/recursive expressions.<jupyter_code>a = '& 1 0'
print(a.split(' '))
# YOUR CODE GOES HERE 
def evaluate(expression):
    
    expression = expression.split(' ')

    function = {
        '&': (lambda a,b : a & b),
        '|': (lambda a,b : a or b),
        '=>': (lambda a,b : (a & (a & b)) or (not a) ),
        '<=>': (lambda a,b : ((a and b) or (not a and not b)))
    }[expression[0]]
    
    a = bool(int(expression[1]))
    b = bool(int(expression[2]))
    
    return function(a,b)

print(evaluate('& 1 0'))
print(evaluate('& 0 1'))<jupyter_output><empty_output><jupyter_text>Question 1B (Minimum) (CSC421 - 1 point, CSC581C - 0 point) Your next task is to implement variables and bindings for your propositional logic evaluator. In this version in addition to constants (0 and 1) you also can have variables which are strings with associated values provided in a dictionary. You still only consider two operands and one operator (no nesting). For example in the code below the three expressions are equivalent. Your function should take as arguments the expression to be evaluated as a string and the dictionary with the variable bindings. In addition you need to add the ~ (not) operator. To do so for each variable in the dictionary add a not version. For example if 'a' in the dictionary has a value of 1 the '~a' in the dictionary should have a value of 0. Notice that the not symbol is part of the string and NOT separated by a space.<jupyter_code>d = {'foo': 0, 'b': 1}
print(d)
expr1 = '& 0 1'
expr2 = '& foo 1'
expr3 = '& foo ~b'
# YOUR CODE GOES HERE 
'''
Lookup takes a string and returns its boolean value.
'''
def lookup(string, var_map):
    if string in ['0', '1']: return int(string)
    if string[0] == '~': return not int(var_map[string[1:]])
    return int(var_map[string])

def evaluate_logic(expression, var_map):
    
    expression = expression.split(' ')

    function = {
        '&': (lambda a,b : a & b),
        '|': (lambda a,b : a or b),
        '=>': (lambda a,b : (a & (a & b)) or (not a) ),
        '<=>': (lambda a,b : ((a and b) or (not a and not b)))
    }[expression[0]]
    
    a = lookup(expression[1], var_map)
    b = lookup(expression[2], var_map)

    return function(a,b)

d = {'foo': 1, 'b': 0}
expr1 = '& 0 1'
expr2 = '& foo 1'
expr3 = '& foo ~b'<jupyter_output><empty_output><jupyter_text>Question 1C (Expected) 1 point The following code is a recursive evaluator for prefix arithmetic expressions. It assumes that there are always two operands either an integer or a prefix expression starting with an operator (addition or multiplication). It is a good idea to go through this function carefully by hand to understand how the recursion works. Informed by your understanding of the arithmetic recursive_eval function your task is to write function to implement a recursive prefix logic evaluator. Your evaluator should also support variables bindings using a dictionary as in the previous question. Example expressions: ```& 1 & 1 a   => 0 & b ~alice   foo 1 ```<jupyter_code>def recursive_eval(l):
    head, tail = l[0], l[1:]
    if head in ['+', '*']: 
        val1, tail = recursive_eval(tail)
        val2, tail = recursive_eval(tail)
        if head == '+': 
            return (int(val1)+int(val2), tail)
        elif head == '*':  
            return (int(val1)*int(val2), tail)
    # operator is a number 
    else:  
        return (int(head),tail)

def prefix_eval(input_str): 
    input_list = input_str.split(' ')
    res, tail = recursive_eval(input_list)
    return res

print(prefix_eval('1'))
print(prefix_eval('+ 1 2'))
print(prefix_eval('+ 1 * 2 3'))
print(prefix_eval('+ * 5 2 * 3 + 1 5'))
# YOUR CODE GOES HERE 

def lookup(component, variables):
    if component in ['0', '1']: return int(component)
    if component[0] == '~': return int(not variables[component[1:]])
    return int(variables[component])

def evaluate(expression, variables):
    
    expression = expression.split(' ')

    function = {
        '&': (lambda a,b : a & b),
        '|': (lambda a,b : int(a or b)),
        '=>': (lambda a,b : int(a & (a & b) or (not a))),
        '<=>': (lambda a,b : int((a and b) or (not a and not b)))
    }[expression[0]]
    
    a = lookup(expression[1], variables)
    b = lookup(expression[2], variables)

    return function(a,b)


def recursive_logic_eval(l, variables):
    head, tail = l[0], l[1:]
    if head in ['=>', '&', '|', '<=>']: 
        val1, tail = recursive_logic_eval(tail, variables)
        val2, tail = recursive_logic_eval(tail, variables)
        expression = "{} {} {}".format(head, val1, val2)
        return evaluate(expression, variables), tail
    # operator is a number 
    else:  
        return (lookup(head, variables),tail)

def prefix_logic_eval(expression, variables):
    input_list = expression.split(' ')
    res, tail = recursive_logic_eval(input_list, variables)
    return res

variables = {
    'a': 0,
    'b': 1,
    'foo': 1,
    'alice': 0
}

exp1 = '& 1 & 1 ~a'
exp2 = '& 1 & 1 a'   
exp3 = '=> 1 & b ~alice'
exp4 = '<=> ~foo 0'
print(prefix_logic_eval(exp1, variables))
print(prefix_logic_eval(exp2, variables))
print(prefix_logic_eval(exp3, variables))
print(prefix_logic_eval(exp4, variables))<jupyter_output><empty_output><jupyter_text>QUESTION 1D (EXPECTED) 1 point Using the recursive prefix evaluator you defined in the previous question answer the following question (you will need to convert the exressions below to prefix). You can use multiple string assignments to assemble more complicated sentences into one big string: Let A be the formula: \begin{equation}   (( p_{1} \rightarrow (p2 \land p_{3})) \land ((\neg p_{1})  \rightarrow (p_{3} \land p_{4})))\end{equation} Let B be the formula: \begin{equation}   (( p_{3} \rightarrow (\neg p_{6})) \land ((\neg  p_{3}) \rightarrow (p_{4} \rightarrow p_{1})))  \end{equation} Let C be the formula: \begin{equation}   ((\neg(p2 \land p_{5})) \land (p2 \rightarrow p_{5})) \end{equation} Let D be the formula: \begin{equation}   (\neg (p_{3} \rightarrow p_{6}))\end{equation} Evaluate the formulate E: \begin{equation}   (( A \land (B \land C)) \rightarrow D)\end{equation} under the true assignment $I_{1}$, where $I_{1}(p_{1}) = I_{1}(p_{3}) = I_{1}(p_{5}) = false$ and $I_{1}(p2) = I_{1}(p_{4}) = I_{1}(p_{6}) = true$ as well as under the truth assignment $I_{2}$, where $I_{2}(p_{1}) = I_{2}(p_{3}) = I_{2}(p_{5}) = true$ and$I_{2}(p_{2})=I_{2}(p_{4})=I_{2}(p_{6}) = false$.<jupyter_code># YOUR CODE GOES HERE
I1 = {
    'p1': 0,
    'p2': 1,
    'p3': 0,
    'p4': 1,
    'p5': 0,
    'p6': 1
}
I2 = {
    'p1': 1,
    'p2': 0,
    'p3': 1,
    'p4': 0,
    'p5': 1,
    'p6': 0
}


A = "& => ~p1 & p3 p4 => p1 & p2 p3"
print("A of I1:", prefix_logic_eval(A, I1))
print("A of I2:", prefix_logic_eval(A, I2))


B = "& => p3 ~p6 => ~p3 => p4 p1"
print("B of I1:", prefix_logic_eval(B, I1))
print("B of I2:", prefix_logic_eval(B, I2))

C = "& | ~p2 ~p5 => p2 p5"
print("C of I1:", prefix_logic_eval(C, I1))
print("C of I2:", prefix_logic_eval(C, I2))

D = "& ~p3 p6"
print("D of I1:", prefix_logic_eval(D, I1))
print("D of I2:", prefix_logic_eval(D, I2))

E1 = "=> & & {} {} {} {}".format(
    prefix_logic_eval(A, I1),
    prefix_logic_eval(B, I1),
    prefix_logic_eval(C, I1),
    prefix_logic_eval(D, I1)
)
E2 = "=> & & {} {} {} {}".format(
    prefix_logic_eval(A, I2),
    prefix_logic_eval(B, I2),
    prefix_logic_eval(C, I2),
    prefix_logic_eval(D, I2)
)
print("E of I1:", prefix_logic_eval(E1, I1))
print("E of I2:", prefix_logic_eval(E2, I2))<jupyter_output><empty_output><jupyter_text>QUESTION 1E (ADVANCED) 1 point Implement inference using model-checking using your prefix recursive evaluator to decide whether a knowledge base KB entais some sentence a. To do so express the knowledge base in the prefix notation, enumerate all models for the variables in the dictionary, and check that the sentence a is true in every model in which the KB is true. You can check the implementation to tt_entails in logic.ipynb in the aima_python repository to inform how you implement your solution. Your solution should NOT rely directly on any code in logic.py or logic.ipynb. Check your model checking using the examples that are used in logic.ipynb to check entailment (there are a few with P and Q as variables as well as the one with A, B, C, D, E, F, G. You will need to convert these examples to prefix notation.<jupyter_code># YOUR CODE GOES HERE<jupyter_output><empty_output><jupyter_text>QUESTION 1F (ADVANCED) (CSC421 - 0 points, CSC581C - 1 point)Implement conversion of the prefix expressions to prefix conjuctive normal form (CNF) based on the recursive evaluator you have implemented.<jupyter_code># YOUR CODE GOES HERE<jupyter_output><empty_output><jupyter_text>QUESTION 1E (ADVANCED) (CSC421 - 0 POINTS, CSC581C 1 point)Based on the recursive evaluator you have implemented do a conversion of expressions in prefix notation to the infix notation of expressions supported by logic.ipynb. Provide 4 test cases that demonstrate the the conversion works by confirming that the result of your evaluator and the logic.ipynb evaluator are the same.<jupyter_code># YOUR CODE GOES HERE<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12296659086933706, 'fraction_numerical': 0.025450411054748993, 'mean_word_length': 3.8701022146507666, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 51, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '664495', 'license': 'MIT', 'n_tokens_mistral': 3841, 'n_tokens_neox': 3594, 'n_words': 1472, 'path': 'csc421_asn2_part1.ipynb', 'repo_name': 'dragonprevost/aima-python', 'size': '11445'}