The questions in this assignment refer to the same problem as programming assignment 3, please refer to the description of that assignment for additional details. Also, please note that, for CSE 4308 students, written assignment 3 and programming assignment 3 together will be used as the CSE 4308 assessment, worth 8% of the grade.
1a: (5 points) Are there inference algorithms for propositional logic that are sound and complete?
Answer: Yes.
1b: (5 points) If you answered yes for 1a, what aspects of propositional logic make it possible to have such algorithms? If you answered no, what aspects of propositional logic make it impossible to have such algorithms?
Answer: Such algorithms are made possible that in propositional logic the number of possible worlds (models) is finite.
Suppose that an agent using the program described in programming assignment 3 for inference, has gone through squares (1,1), (1,2), (1,3), (1,4) sensing no stench or breeze anywhere, except for a stench at square (1,4). You can assume that an agent dies if it moves to a square containing a monster or a pit, and that this particular agent did not die at any of the four squares. Specify a set of statements that we need to add to the knowledge base to represent the information that the agent collected out of those four squares. The set of statements should be sufficient, meaning that the inference engine will always give results that are correct and consistent with the information that the agent obtained from those four squares. Your set of statements should also be MINIMAL, i.e., it should not be possible to leave out any of those statements without sacrificing the correctness of the inference algorithm. You should assume that the knowledge base already contains the wumpus rules, and in particular the version of the rules specified in programming assignment 3, not the version specified in the textbook.
Answer: First of all, we note that when we update the knowledge base we should not perform inference to figure out what is already there. So, the minimal set of statements we should add without needing to perform inference is:
(not B_1_1)
(not S_1_1)
(not M_1_1)
(not P_1_1)
(not B_1_2)
(not S_1_2)
(not M_1_2)
(not P_1_2)
(not B_1_3)
(not S_1_3)
(not M_1_3)
(not P_1_3)
(not B_1_4)
S_1_4
(not M_1_4)
(not P_1_4)
Suppose that your agent has already been through 12 of the 16 squares, and that your knowledge base has been updated accordingly. What can you say about the efficiency of inference in this knowledge base, compared to the efficiency of inference in a knowledge base where the agent has only been at square (1,1) and nothing (except for the wumpus rules) is known about the rest of the squares? What quantity determines the worst-case efficiency of the algorithm? What is the value of that quantity in each of the two cases? How can you exploit the information from the 12 squares to speed up inference?
Answer: The quantity that determines the worst-case efficiency is the number of symbols whose value has not been directly observed. There are 16 such symbols, and the time complexity is is exponential to the number of symbols whose values are unknown. If we have only been at square (1,1), then 60 symbols are unknown. If we have been to 12 squares, before the initial call to TT-CHECK-ALL, we can scan the knowledge base, and put into the "model" argument of TT-CHECK-ALL all symbols whose values are known. This way, the initial call to TT-CHECK-ALL will contain not an empty model, but a model containing values for 48 symbols.
Name two inference algorithms for propositional logic that can be used to implement the inference engine in programming assignment 3.
Answer: Inference by enumeration (TT-ENTAILS), and resolution.
Suppose that you have a function f(kb, statement) that returns true iff kb (the knowledge base) entails the statement (a logical sentence) and false otherwise. Write pseudocode that, using function f, defines a function g(kb, statement) that returns +1 iff the statement is definitely true given kb, -1 iff the statement is definitely false given kb, and 0 otherwise.
Answer:
a = f(kb, statement);
b = f(kb, not(statement));
if (a and (not b))
return +1;
else if ((not a) and b)
return -1;
else
return 0;
Write pseudocode for a function extract_symbols(statement) that extracts the list of all unique symbols appearing in statement, where statement is a logical expression. What is the base case for extract_symbols? What are the recursive cases? Your function should work with arbitrarily complex statements following the syntax specified in programming assignment 3.
Your pseudocode should assume that the statement has already been stored in an object of type logical_expression, as defined in sample code file check_true_false.h from programming assignment 3. Your pseudocode should use the member variables "connective", "symbol", and "subexpressions" of class logical_expression.
Answer:
Base case: statement is a symbol.
Recursive case: statement is not a symbol.
extract_symbol(statement)
{
if (statement.symbol != null)
return a list whose single element is statement.symbol;
result = empty list;
for each exp in statement.subexpressions
result = merge_lists(result, extract_symbol(exp));
end
result = remove_duplicates(result);
}
Suppose that you have an omniscient function f(symbol) that tells you for any symbol in your wumpus world whether that symbol is true or false in that world. Write pseudocode that, using that function, defines a recursive function g(statement) that can always tell if statement is true or false, and works for any statement (however complex it may be) defined using the propositional logic syntax of programming assignment 3. Remember that only six connectors are defined in that syntax: and, or, xor, not, if, and iff.
What is the base case for function g? Which are the recursive cases? How many recursive cases are there?
As in problem 6, your pseudocode should assume that the statement has already been stored in an object of type logical_expression, as defined in sample code file check_true_false.h from programming assignment 3. Your pseudocode should use the member variables "connective", "symbol", and "subexpressions" of class logical_expression. The pseudocode should be specific enough to show exactly how to deal with each connective.
Answer:
The base case is when the statement is a symbol.
The recursive case is when the statement contains a connective. There are six subcases of the recursive case, one for each connective.
g(statement)
{
if (statement.symbol != null)
return f(statement.symbol);
if (statement.connective == "AND")
if (statement.subexpressions == empty list)
return true;
else
result_list = list of results of applying g to each subexpression in statement.subexpressions;
if result_list contains false, return false;
else return true;
if (statement.connective == "OR")
if (statement.subexpressions == empty list)
return false;
else
result_list = list of results of applying g to each subexpression in statement.subexpressions;
if result_list contains true, return true;
else return false;
if (statement.connective == "XOR")
if (statement.subexpressions == empty list)
return false;
else
result_list = list of results of applying g to each subexpression in statement.subexpressions;
if result_list contains only one "true" value (no more, no less), return true;
else return false;
if (statement.connective == "NOT")
if (statement.subexpressions == empty list)
exit with error message;
else
negation = not(statement.subexpressions[0])
return not(g(negation))
if (statement.connective == "IF")
if (statement.subexpressions.length() != 2)
exit with error message;
else
result1 = g(not(statement.subexpressions[0]));
result2 = g(statement.subexpressions[1]);
return not(result1) OR result2;
if (statement.connective == "IFF")
if (statement.subexpressions.length() != 2)
exit with error message;
else
result1 = g(not(statement.subexpressions[0]));
result2 = g(statement.subexpressions[1]);
return result1 == result2;