Toggle navigation
Home
Ask A Question
Answer Questions
Users
Support/FAQ
Register
Login
862homework.pdf
Details
Question Title:
i have the code but there is some parts, i have
View the Question
Preview - Click download on the question page for the full document.
") return False def check_term(T): if is_constant(T): return (get_value(T) is not None) or pFail("The value of the constant is None", T) if is_variable(T): return (get_name(T) is not None) or pFail("The name of the variable is None", T) if is_function_call(T): return not [t for t in get_args(T) if not check_term(t)] and \ (get_head(T) is not None or pFail("Function is not callable", T)) return pFail("Term is not one of constant, variable or function call", T) def check_atom(A): if is_atom(A): return not [t for t in get_args(A) if not check_term(t)] and \ (get_head(A) is not None or pFail("Predicate name is None", A)) return pFail("Is not an atom", A) def check_sentence(S): if is_atom(S): return check_atom(S) if is_sentence(S): if get_head(S) in [and_name, or_name]: return (len(get_args(S)) >= 2 or pFail("Sentence has too few operands", S)) \ and not [s for s in get_args(S) if not check_sentence(s)] if get_head(S) == neg_name: return (len(get_args(S)) == 1 or pFail("Negative sentence has not just 1 operand", S)) \ and check_sentence(get_args(S)[0]) return pFail("Not sentence or unknown type", S) def add_statement(kb, conclusion, *hypotheses): s = conclusion if not hypotheses else make_or(*([make_neg(s) for s in hypotheses] + [conclusion])) if check_sentence(s): kb.append(s) print("OK: Added statement " + print_formula(s, True)) return True print("-- FAILED CHECK: Sentence does not check out <"+print_formula(s, True)+"><" + str(s) + ">") return False var_no = 0; def assign_next_var_name(): global var_no var_no += 1 return "v" + str(var_no) def gather_vars(S): return [get_name(S)] if is_variable(S) else \ [] if not has_args(S) else reduce(lambda res, a: res + gather_vars(a), get_args(S), []) def make_unique_var_names(KB): global var_no var_no = 0 return [substitute(S, {var: make_var(assign_next_var_name()) for var in gather_vars(S)}) for S in KB] def print_KB(KB): print("KB now:") for s in KB: print("\t\t\t" + print_formula(s, True)) # KB 1 # based on an example in Artificial Intelligence - A Modern Approach KB_America = [] #0 Mr West is a US general add_statement(KB_America, make_atom("USGeneral", make_const("West"))) #1 General Awesome is also a US general add_statement(KB_America, make_atom("USGeneral", make_const("General_Awesome"))) #2 General Awesome is Awesome add_statement(KB_America, make_atom("Awesome", make_const("General_Awesome"))) #3 Nono is an enemy of America add_statement(KB_America, make_atom("Enemy", make_const("Nono"), make_const("America"))) #4 M1 is a type of missile add_statement(KB_America, make_atom("Missile", make_const("M1"))) #5 Nono has the M1 missile add_statement(KB_America, make_atom("Owns", make_const("Nono"), make_const("M1"))) #6 any US general is an American add_statement(KB_America, make_atom("American", make_var("x")), make_atom("USGeneral", make_var("x"))) #7 any missle is a weapon add_statement(KB_America, make_atom("Weapon", make_var("x")), make_atom("Missile", make_var("x"))) #8 if anyone owns a missile, it is General West that sold them that missile add_statement(KB_America, make_atom("Sells", make_const("West"), make_var("y"), make_var("x")), make_atom("Owns", make_var("x"), make_var("y")), make_atom("Missile", make_var("y"))) #9 any American who sells weapons to a hostile is a criminal add_statement(KB_America, make_atom("Criminal", make_var("x")), make_atom("Weapon", make_var("y")), make_atom("Sells", make_var("x"), make_var("y"), make_var("z")), make_atom("Hostile", make_var("z")), make_atom("American", make_var("x"))) #10 any enemy of America is called a hostile add_statement(KB_America, make_atom("Hostile", make_var("x")), make_atom("Enemy", make_var("x"), make_const("America"))) #11 America is awesome if at least an American is awesome add_statement(KB_America, make_atom("Awesome", make_const("America")), make_atom("American", make_var("x")), make_atom("Awesome", make_var("x"))) KB_America = make_unique_var_names(KB_America) print_KB(KB_America) OK: Added statement USGeneral(West) OK: Added statement USGeneral(General_Awesome) OK: Added statement Awesome(General_Awesome) OK: Added statement Enemy(Nono, America) OK: Added statement Missile(M1) OK: Added statement Owns(Nono, M1) OK: Added statement (V ~USGeneral(?x) American(?x)) OK: Added statement (V ~Missile(?x) Weapon(?x)) OK: Added statement (V ~Owns(?x, ?y) ~Missile(?y) Sells(West, ?y, ?x)) OK: Added statement (V ~Weapon(?y) ~Sells(?x, ?y, ?z) ~Hostile(?z) ~American(?x) Criminal(?x)) OK: Added statement (V ~Enemy(?x, America) Hostile(?x)) OK: Added statement (V ~American(?x) ~Awesome(?x) Awesome(America)) KB now: USGeneral(West) USGeneral(General_Awesome) Awesome(General_Awesome) Enemy(Nono, America) Missile(M1) Owns(Nono, M1) (V ~USGeneral(?v2) American(?v2)) (V ~Missile(?v4) Weapon(?v4)) (V ~Owns(?v9, ?v8) ~Missile(?v8) Sells(West, ?v8, ? v9)) (V ~Weapon(?v12) ~Sells(?v16, ?v12, ?v14) ~Hostile(? v14) ~American(?v16) Criminal(?v16)) (V ~Enemy(?v18, America) Hostile(?v18)) (V ~American(?v20) ~Awesome(?v20) Awesome(America)) # KB 2 KB_Faster = [] def the_greyhound(): return make_const("Greg") #0 horses are faster than dogs add_statement(KB_Faster, make_atom("Faster", make_var("x"), make_var("y")), make_atom("Horse", make_var("x")), make_atom("Dog", make_var("y"))) #1 there is a greyhound that is faster than any rabbit add_statement(KB_Faster, make_atom("Faster", make_function_call(the_greyhound), make_var("z")), make_atom("Rabbit", make_var("z"))) #2 Harry is a horse add_statement(KB_Faster, make_atom("Horse", make_const("Harry"))) #3 Ralph is a rabbit add_statement(KB_Faster, make_atom("Rabbit", make_const("Ralph"))) #4 Greg is a greyhound add_statement(KB_Faster, make_atom("Greyhound", make_function_call(the_greyhound))) #5 A greyhound is a dog add_statement(KB_Faster, make_atom("Dog", make_var("y")), make_atom("Greyhound", make_var("y"))) #6 transitivity add_statement(KB_Faster, make_atom("Faster", make_var("x"), make_var("z")), make_atom("Faster", make_var("x"), make_var("y")), make_atom("Faster", make_var("y"), make_var("z"))) KB_Faster = make_unique_var_names(KB_Faster) print_KB(KB_Faster) OK: Added statement (V ~Horse(?x) ~Dog(?y) Faster(?x, ?y)) OK: Added statement (V ~Rabbit(?z) Faster(<function the_greyhound at 0x000002863B839E58>[], ?z)) OK: Added statement Horse(Harry) OK: Added statement Rabbit(Ralph) OK: Added statement Greyhound(<function the_greyhound at 0x000002863B839E58>[]) OK: Added statement (V ~Greyhound(?y) Dog(?y)) OK: Added statement (V ~Faster(?x, ?y) ~Faster(?y, ?z) Faster(?x, ?z)) KB now: (V ~Horse(?v3) ~Dog(?v4) Faster(?v3, ?v4)) (V ~Rabbit(?v6) Faster(<function the_greyhound at 0x000002863B839E58>[], ?v6)) Horse(Harry) Rabbit(Ralph) Greyhound(<function the_greyhound at 0x000002863B839E58>[]) (V ~Greyhound(?v8) Dog(?v8)) (V ~Faster(?v13, ?v11) ~Faster(?v11, ?v14) Faster(? v13, ?v14)) KB_test = [] add_statement(KB_test, make_atom("Q", make_var("x")), make_atom("P", make_var("x"))) add_statement(KB_test, make_atom("P", make_const("A"))) KB_test = make_unique_var_names(KB_test) print_KB(KB_test) OK: Added statement (V ~P(?x) Q(?x)) OK: Added statement P(A) KB now: (V ~P(?v2) Q(?v2)) P(A) Task 1 - 3p • Implement the resolves function, which receives two clauses (literal or disjunction of literals) and returnsFalse if the two clauses do not resolve, otherwise returns a tuple containing the resolution literals, of the two clauses, and the substitution under which they resolve. • Two clauses resolve if there is a positive literal in one clause and a negative literal in the other, and the atoms of the two literals unify. def is_positive_literal(L): return is_atom(L) def is_negative_literal(L): global neg_name return get_head(L) == neg_name and is_positive_literal(get_args(L) [0]) def is_literal(L): return is_positive_literal(L) or is_negative_literal(L) def resolves(C1, C2): #print("testing " + print_formula(C1, True) + " and " + print_formula(C2, True)) # Returns a tuple (literal-from-C1, literal-from-C2, substitution) # where literal-from-C1 and literal-from-C2 unify under substitution. return False # Test! test_batch(4, globals()) Expected results: >>> Test batch [4] Test 0: OK, got < (USGeneral(General_Awesome), ~USGeneral(?v2), {?v2 - > General_Awesome} > Test 1: OK, got < (Owns(Nono, M1), ~Owns(?v9, ?v8), {?v8 -> M1, ?v9 -> Nono} > Test 2: OK, got < (~American(?v16), American(?v2), {?v2 -> ?v16} > Test 3: OK, got < (Enemy(Nono, America), ~Enemy(?v18, America), {?v18 -> Nono} > Test 4: OK, got < False > Test 5: OK, got < False > Test 6: OK, got < False > Test 7: OK, got < False > Test 8: OK, got < (Q(5), ~Q(5), {} > Test 9: OK, got < False > >>> 10 / 10 tests successful. Obs: To display the result of the resolution function between two clauses, we can use the print_r function. # Prints a 5-tuple resolvent representation (see below) def print_r(R): if R is None: print("no resolvent") else: print("resolvent: " + print_formula(R[2], True) + "/" + print_formula(R[3], True) \ + " {" + ", ".join([(k + ": " + str(R[4][k])) for k in R[4]]) + "}" \ + "\n\t\t in " + print_formula(R[0], True) + "\n\t\t and " + print_formula(R[1], True)) Task 2 - 2p • Implement the new_clause function, which returns a new solver-based clause, represented as a tuple of 5 elements: – the 2 clauses which are resolved; – the 2 literals, one from the first clause, and one from the second clause, which resolves (given as they are in the 2 clauses); – the substitution under which the two literals resolve. • If the result of the resolution step is the empty clause, the function must return VOID_CLAUSE. • Otherwise, the result must be a clause that: – contains all the literals of clauses that have been resolved, but – does not contain literals that have been resolved, and – has the substitution applied (the substitution function has already been implemented in laboratory 8), and – does not contain the same literal more than once. VOID_CLAUSE = "The void clause" def new_clause(resolvent): C1, C2, L1, L2, s = resolvent # TODO return None # Test! test_batch(5, globals()) Expected results: >>> Test batch [5] Test 0: OK, got < The void clause > Test 1: OK, got < Q(?y) > Test 2: OK, got < ~Q(5) > Test 3: OK >>> 4 / 4 tests successful. Task 3 - 5p Implement the missing part of the solve_problem function, using a solving strategy of your choice to determine two clauses that resolve, and adding the result of the solve step to the knowledge base. def solve_problem(hypotheses, conclusion): KB = hypotheses[:] KB = [make_neg(conclusion)] + KB # You can also add at the end (depending on strategy) Effort = 50 # You can increase the effort if necessary while Effort > 0: Effort -= 1 # Select two clauses Clause1 and Clause2 which have not been previously chosen. # Compute a resolvent, as tuple (Clause1, Clause2, Literal- from-clause1, Literal-from-clause2, substitution). resolvent = None # TODO print_r(resolvent) if resolvent is None: print("Failed. No resolving clauses. Effort left " + str(Effort)) return False # Calculate the new clause to be added and add it to the knowledge base. C = new_clause(resolvent) if C == VOID_CLAUSE: print("Done (effort left " + str(Effort) + ")") return True # update KB print("Added: " + print_formula(C, True)) KB = [C] + KB print_KB(KB) print("Failed. Effort exhausted.") #print_KB(KB_test) solve_problem(deepcopy(KB_test), make_atom("Q", make_const("A"))) print("==========================================") #print_KB(KB_America) #solve_problem(deepcopy(KB_America), make_atom("Criminal", make_const("West"))) print("==========================================") #print_KB(KB_Faster) #solve_problem(deepcopy(KB_Faster), make_atom("Faster", make_const("Harry"), make_const("Ralph"))) print("==========================================") Note: The expected output is longer than this printout, but its start should be similar to: KB now: ~Q(A) (V ~P(?v2) Q(?v2)) P(A) refreshing CList resolvent: ~Q(A)/Q(?v2){v2: (0, 'A')} in ~Q(A) and (V ~P(?v2) Q(?v2)) Added: ~P(A) KB now: ~P(A) (V ~P(?v2) Q(?v2)) P(A) refreshing CList resolvent: ~P(A)/P(A){} in ~P(A) and P(A) Done (effort left 497) ">
