#!/usr/bin/env python # coding: utf-8 # ## Artificial Intelligence, Programming Lab 3 # # ### Logical reasoning, Propositional logic, First Order Logic (part I) # In this session, we will study how to encode and then generate logical expression from those propositions by means of logical connectives. # # We will represent the propositions through strings, e.g. 'A', 'B', the logical connectives are represented by strings of the corresponding boolean symbols '|', '&', '==>', '<=>' # ### Exercise 1. Warm up: Encoding and Decoding logical expressions # # The code below can be used to generate logical expressions. Logical expressions are represented by strings of the form 'A & B' or 'A | B',... Try encoding and decoding a couple of expressions. # In[51]: # For operators that are not defined in Python, we allow new InfixOps: class Expr: """A mathematical expression with an operator and 0 or more arguments. op is a str like '+' or 'sin'; args are Expressions. Expr('x') or Symbol('x') creates a symbol (a nullary Expr). Expr('-', x) creates a unary; Expr('+', x, 1) creates a binary.""" def __init__(self, op, *args): self.op = str(op) self.args = args # Operator overloads def __neg__(self): return Expr('-', self) def __pos__(self): return Expr('+', self) def __invert__(self): return Expr('~', self) def __add__(self, rhs): return Expr('+', self, rhs) def __sub__(self, rhs): return Expr('-', self, rhs) def __mul__(self, rhs): return Expr('*', self, rhs) def __pow__(self, rhs): return Expr('**', self, rhs) def __mod__(self, rhs): return Expr('%', self, rhs) def __and__(self, rhs): return Expr('&', self, rhs) def __xor__(self, rhs): return Expr('^', self, rhs) def __rshift__(self, rhs): return Expr('>>', self, rhs) def __lshift__(self, rhs): return Expr('<<', self, rhs) def __truediv__(self, rhs): return Expr('/', self, rhs) def __floordiv__(self, rhs): return Expr('//', self, rhs) def __matmul__(self, rhs): return Expr('@', self, rhs) def __or__(self, rhs): """Allow both P | Q, and P |'==>'| Q.""" if isinstance(rhs, Expression): return Expr('|', self, rhs) else: return PartialExpr(rhs, self) # Reverse operator overloads def __radd__(self, lhs): return Expr('+', lhs, self) def __rsub__(self, lhs): return Expr('-', lhs, self) def __rmul__(self, lhs): return Expr('*', lhs, self) def __rdiv__(self, lhs): return Expr('/', lhs, self) def __rpow__(self, lhs): return Expr('**', lhs, self) def __rmod__(self, lhs): return Expr('%', lhs, self) def __rand__(self, lhs): return Expr('&', lhs, self) def __rxor__(self, lhs): return Expr('^', lhs, self) def __ror__(self, lhs): return Expr('|', lhs, self) def __rrshift__(self, lhs): return Expr('>>', lhs, self) def __rlshift__(self, lhs): return Expr('<<', lhs, self) def __rtruediv__(self, lhs): return Expr('/', lhs, self) def __rfloordiv__(self, lhs): return Expr('//', lhs, self) def __rmatmul__(self, lhs): return Expr('@', lhs, self) def __call__(self, *args): """Call: if 'f' is a Symbol, then f(0) == Expr('f', 0).""" if self.args: raise ValueError('Can only do a call for a Symbol, not an Expr') else: return Expr(self.op, *args) # Equality and repr def __eq__(self, other): """x == y' evaluates to True or False; does not build an Expr.""" return isinstance(other, Expr) and self.op == other.op and self.args == other.args def __lt__(self, other): return isinstance(other, Expr) and str(self) < str(other) def __hash__(self): return hash(self.op) ^ hash(self.args) def __repr__(self): op = self.op args = [str(arg) for arg in self.args] if isidentifier(op): # f(x) or f(x, y) return '{}({})'.format(op, ', '.join(args)) if args else op elif len(args) == 1: # -x or -(x + 1) return op + args[0] else: # (x - y) opp = (' ' + op + ' ') return '(' + opp.join(args) + ')' class PartialExpr: """Given 'P |'==>'| Q, first form PartialExpr('==>', P), then combine with Q.""" def __init__(self, op, lhs): self.op, self.lhs = op, lhs def __or__(self, rhs): return Expr(self.op, self.lhs, rhs) def __repr__(self): return "PartialExpr('{}', {})".format(self.op, self.lhs) def expr(x): """Shortcut to create an Expression. x is a str in which: - identifiers are automatically defined as Symbols. - ==> is treated as an infix |'==>'|, as are <== and <=>. If x is already an Expression, it is returned unchanged. Example: >>> expr('P & Q ==> Q') ((P & Q) ==> Q) """ return eval(expr_handle_infix_ops(x), defaultkeydict(Symbol)) if isinstance(x, str) else x infix_ops = '==> <== <=>'.split() def expr_handle_infix_ops(x): """Given a str, return a new str with ==> replaced by |'==>'|, etc. >>> expr_handle_infix_ops('P ==> Q') "P |'==>'| Q" """ for op in infix_ops: x = x.replace(op, '|' + repr(op) + '|') return x class defaultkeydict(collections.defaultdict): """Like defaultdict, but the default_factory is a function of the key. >>> d = defaultkeydict(len); d['four'] 4 """ def __missing__(self, key): self[key] = result = self.default_factory(key) return result class hashabledict(dict): """Allows hashing by representing a dictionary as tuple of key:value pairs. May cause problems as the hash value may change during runtime.""" def __hash__(self): return 1 import keyword import re def isidentifier(candidate): "Is the candidate string an identifier in Python 2.x" is_not_keyword = candidate not in keyword.kwlist pattern = re.compile(r'^[a-z_][a-z0-9_]*$', re.I) matches_pattern = bool(pattern.match(candidate)) return is_not_keyword and matches_pattern Number = (int, float, complex) Expression = (Expr, Number) # ### Exercise 2. Evaluating logical expressions (Part I) # # Complete the function 'evaluate_PL_Expression' below. This function should return the logical value (True or False of the Propositional expression exp following from the model 'model'). # # 1- You should use a recursive formulation, splitting the proposition into subexpressions until those are empty # 2-You should encode the model as a dictionnary and use the corresponding get function to access the boolean value of a proposition. # # You will need the function below which checks if a variable is a symbol (string starting with an alphabetic char) and if a variable is a logical variable symbol (a symbol whose first letter is a capital letter). # # Start by filling out the two functions below then complete the recursive function evaluate_PL_Expression. # In[ ]: def is_symbol(s): """A string s is a symbol if it starts with an alphabetic char. >>> is_symbol('R2D2') True """ return # complete def is_var_symbol(s): """A logic variable symbol is an initial-lowercase string. >>> is_var_symbol('EXE') False """ return # complete # In[ ]: def evaluate_PL_Expression(exp, model={}): '''The function should return the evaluation from within the model It should retun True if the Propositional sentence is true, False if this sentence is False and None if the model does not specify the value for some of the propositions''' # complete with a recursion and calls to model.get return value_of_expression # ### Exercise 3. Evaluating logical expressions (Part II) # # Once you have coded your function, try with a couple of dictionnaries. # In[ ]: # put your code here # ### Exercise 4. The knowledge Base # # Now that we have a way to store and evaluate logical sentences, we want to build a Knowledge base. The propositional Knowledge base should contain an initialization function which sets the list of clauses to 0, a tell function which adds a new sentence to the KB, and a function 'ask' that checks whether the sentence is entailed by the KB. The function 'ask' should return True if the sentence is entailed and False otherwise. # # To do this, proceed as follows. Using Expr, Start by returning a conjunction involving all the sentences from the knowledge base. Then define a function KB_entails that takes as inputs, your query and the conjunction. # # #### Exercise 4.1. Checking entailment # # # Recall that a complex inference (i.e. implication) sentence is valid if it is true in every row of the truth table corresponding to a possible state of the world. # # # Start by completing the two functions below. # # - The 'KB_entails(kb, sentence)' should generate all the symbols appearing in the knowledge base KB (which we will represent as an expression) and the consequent of the sentence we want to test. # # - The 'KBcheck_all' should return True if the query sentence is True for every row in the Truth table for which the KB is true. # # You can use the function 'merge_two_dicts' below to store the symbols from the KB and the query. # In[ ]: def merge_two_dicts(x, y): z = x.copy() # start with x's keys and values z.update(y) # modifies z with y's keys and values & returns None return z def extend(d, var, val): return merge_two_dicts(d,{var: val}) # In[ ]: def KBentails(kb, query_sentence): '''tt_entails(expr('P & Q'), expr('Q')) should return True''' symbols = # return all symbols return KBcheck_all(kb, query_sentence, symbols, {}) def KBcheck_all(kb, query_sentence, symbols, model): '''check whether the sentence 'query_sentence' of the implication KB ==> query_sentence is True for every row in the Truth table for which all the propositions in the KB are true.''' # complete the function. Generate all the rows in the truth table. # Then look at each row # #### Exercise 4.2. Defining the Knowledge Base # # Once you have the implementation for the entailment function, complete the class PropositionKnowledgeBase below by implementing the functions 'tell' and 'ask' # In[ ]: class PropositionKnowledgeBase(KB): """A KB for propositional logic. Inefficient, with no indexing.""" def __init__(self, sentence=None): self.clauses = [] def tell(self, sentence): """Add the sentence's clauses to the KB.""" # complete def ask(self, query): """Return True if the KB entails query, else return False.""" # #### Exercise 4.3. Testing the knowledge base. # # Test your knowlege base with a couple of simple benchmarks such as for # example such as for 'Socrates is a man' = True, # 'Every man is Mortal' = True, {'Socrates is a man' and 'Every man is Mortal' => 'Socrates is mortal' is true (all encoded in KB) and check that KB entails 'Socrates is mortal' # # Then check with 'I think' is true, 'I think => I am' is true (both of them included in KB) entails 'I am' is true. # # Try to find other examples. # # In[ ]: # put your code here # ### Exercise 5. Completeness, Resolution and Conjunctive normal forms # # When deriving advanced proofs, we will be interested in a single inference rule known as __resolution__, that always yields a complete inference algorithm when coupled to any complete search algorithm. The resolution rule only applied to finite conjunction or disjunction of litterals. When we want to apply the resolution rule to do inference on general problems, we will thus need to convert every logical sentence into a conjunctive form. This can be done through the following steps: # # # 1. Eliminite the Equivalence $\Leftrightarrow$ replacing $\alpha \Leftrightarrow\beta$ with $(\alpha \Rightarrow \beta)\wedge (\beta \Rightarrow \alpha)$ # 2. Eliminate the Implication $\Rightarrow$ with $\lnot \alpha \vee \beta$ # 3. Conjunctive Normal forms require the $\lnot$ to appear only inside each litteral so we move the $\lnot$ inside by applying the following rules recursively # # - $\lnot(\lnot \alpha) \equiv \alpha$ (double negation elimination) # - $\lnot(\alpha\wedge \beta) \equiv (\lnot \alpha \vee \lnot \beta)$ (De Morgan) # - $\lnot(\alpha\vee \beta) \equiv (\lnot \alpha \wedge \lnot \beta)$ (De Morgan) # # 4. From the rules above, we end up with a sentence combining $\vee$ and $\wedge$ connectives. To get a conjunctive form, we apply the distributive law as much as possible # # $$(\alpha\vee (\beta\wedge \gamma)) = ((\alpha\vee \beta)\wedge (\alpha\vee \gamma))$$ # # # For the particular example of the sentence $B_{1,1} \Leftrightarrow (P_{1,2}\vee P_{2,1})$ would give the following steps # # 1. $(B_{1,1}\Rightarrow (P_{1,2}\vee P_{2,1})) \wedge ((P_{1,2}\vee P_{2,1})\Rightarrow B_{1,1})$ # # 2. $(\lnot B_{1,1}\vee P_{1,2}\vee P_{2,1})\wedge (\lnot(P_{1,2}\vee P_{2,1})\vee B_{1,1})$ # # 3. $(\lnot B_{1,1} \vee P_{1,2}\vee P_{2,1}) \wedge ((\lnot P_{1,2}\wedge \lnot P_{2,1})\vee B_{1,1})$ # # 4. Finally we have $(\lnot B_{1,1}\vee P_{1,2}\vee P_{2,1})\wedge (\lnot P_{1,2}\vee B_{1,1}) \wedge (\lnot P_{2,1}\vee B_{1,1})$ # In[ ]: def string2ConjunctiveNormalFrom(s): '''the function should take as input a complex propositional sentence and return a conjunctive normal form''' # put your code here return s2