Description
Problem 1
25 Points (+5 points EC)
The following outline map needs to be colored. Your job is to color the various sections such that no two sections
sharing a border have the same color. You are allowed to use the colors (Red, Green, Blue).
Figure 5: Map to be colored.
Part a: Draw the Constraint Graph for this problem. Can you use this information to simplify the problem?
Part b: Assuming you are using Backtracking search to solve this problem and that you are using both MRV and
Degree heuristic to select the variable, Which variable will be selected at each level of the search tree [You do
not need to draw the tree. Just let me know which variable will be selected and why (MRV and degree values)].
Note: Multiple possible answers. You only have to give one.
Part c: If we assign the color Red to the Variable at the first level of the search tree, show all the steps involved
in checking arc consistency to find out the remaining legal values for the other variable
Part d: EC (5 points): Give one valid solution to this problem.
Problem 2
10 points.
Two logical statements A and B are logically equivalent if (A <=> B) is valid. We have two knowledge bases,
KB1 and KB2.. Write a function CHECK_EQUIVALENCE(KB1, KB2) that:
returns true if KB1 and KB2 are logically equivalent.
returns false otherwise.
Your pseudocode needs to use or modify TT-ENTAILS from the textbook or slides, and can call any of the
functions given in the textbook or slides, as long as such code and functions are used correctly, with correct
names for the functions, and with well-specified values for all variables and arguments.
Problem 3
10 points.
A B C KB S1
True True True True True
True True False False True
True False True True True
True False False False True
False True True False False
False True False False False
False False True True True
False False False False False
KB and S1 are two propositional logic statements, that are constructed using symbols A, B, C, and using various
connectives. The above truth table shows, for each combination of values of A, B, C, whether KB and S1 are
true or false.
Part a: Given the above information, does KB entail S1? Justify your answer.
Part b: Given the above information, does statement NOT(KB) entail statement NOT(S1)? Justify your answer.
Problem 4
10 points.
Suppose that some knowledge base contains various propositional-logic sentences that utilize symbols A, B, C,
D (connected with various connectives). There are only two cases when the knowledge base is false:
– First case: when A is true, B is true, C is false, D is true.
– Second case: when A is true, B is false, C is true, D is false.
In all other cases, the knowledge base is true. Write a conjunctive normal form (CNF) for the knowledge base.
Problem 5
15 points.
Consider the KB
A <=> B
B => C
D => A
C AND E => F
E
D
Show that this entails F by
i. Forward Chaining
ii. Backward Chaining
iii. Resolution
Problem 6
25 points.
On April 20, 2017, John and Mary sign the following contract:
– If it rains on May 1, 2017, then John must give Mary a check for $10,000 on May 2, 2017
– If John gives Mary a check for $10,000 on May 2, 2017, Mary must mow the lawn on May 3, 2017.
What truly happened those days is the following:
– it did not rain on May 1, 2017
– John gave Mary a check for $10,000 on May 2, 2017
– Mary mowed the lawn on May 3, 2017.
Part a: Write a first order logic statement to express the contract. Make sure that you clearly define what
constants and predicates that you use are. (NOTE: DO NOT use functions)
Part b: Write a logical statement to express what truly happened. When possible, use the same predicates and
constants as in question 6a. If you need to define any new predicates or constants, clearly define what they stand
for.
Part c: Define the symbols required to convert any KB involved in the above domanin from FOL to
Propositional logic. Use this to convert the answers to part a and b to Propositional Logic.
Part d: Was the contract violated or not, Justify your answer Problem 7
5 points
Try and unifiy the following predicates(if possible)
taller(John, y), taller(x, Son(x))
taller(y, Barry), taller(Barry, x)
taller(x, Jane), taller(Bob, Jane)
taller(Son(x), Jane), taller(Bob, Jane)
taller(Barry, John), taller(x, y)
