Question 1 - 15 pointsResolutiona. (7 points) Which sentences, if any, do you obtain by applying the resolution inference rule to the following pair of sentences? Do not do any simplifications to either the input or the output sentences, just blindly apply the resolution rule. The sentences use first-order logic, x,y, and z are variables, John is a constant, pred1, pred2 and pred3 are predicates. If resolution cannot be applied, clearly explain why.not(pred1(x, y)) or pred2(x) or pred3(y)pred1(z, John)pred2(z) or pred3(John)b. (8 points) Which sentences, if any, do you obtain by applying the resolution inference rule to the following pair of sentences? Do not do any simplifications to either the input or the output sentences, just blindly apply the resolution rule. The sentences use first-order logic, x and y are variables, John and Mary are constants, pred1, pred2 and pred3 are predicates. If resolution cannot be applied, clearly explain why.not(pred1(x, y)) or pred2(x) or pred3(x)pred1(Mary, John) or pred3(John)pred2(Mary) or pred3(Mary) or pred3(John)1Question 2 - 15 pointsPattern MatchingWrite the most general unifier for each of the following pairs of first-order logic sentences. The following conventions hold:F and G are predicates.x, y, z are variables.John and Mary are constants.a. (5 points) F(x, y) and F(y, z)F(John, Mary) and F(Mary, John){x/John, y/Mary, z/John}b. (5 points) F(x, y) and F(G(Mary), G(x))F(John, Mary) and F(z, G(John)){x/John, y/Mary, z/G(Mary)}c. (5 points)F(x, y, G(z))F(G(y), Mary, G(John)){x/G(Mary), y/Mary, z/John}2Question 3 – 15 pointsConjunctive Normal Formsa. (7 points) Put the following propositional-logic knowledge base in conjunctive normalform:((NOT A) AND B) => (C OR A)A AND B AND (C OR D)A OR (NOT B) OR C OR AABC OR Db. (8 points) Suppose that some knowledge base contains various propositional-logic sentences that utilize symbols A, B, C, D, E (connected with various connectives). Thereare only two cases when the knowledge base is false:- First case: when A is true, B is true, C is false, D is false, E is false. - Second case: when A is true, B is false, C is false, D is false, E is true.In all other cases, the knowledge base is true. Write a conjunctive normal form for the knowledge base. (Hint: there is a much simpler and quicker way to get the right answer, compared to considering all 32 entries in the truth table).(NOT A) OR (NOT B) OR C OR D OR E(NOT A) OR B OR C OR D OR (NOT E)3Question 4 - 15 pointsLogical EquivalenceDetermine if the following pairs of sentences are logically equivalent, meaning that one istrue if and only iff the other is true. You do not have to justify your answer.a. (5 points) Propositional logic.A or B or not(B) or CA or B or (C <=> C)Logically equivalent, they are both always trueb. (5 points) First-order logic, x and y are variables, f is a predicate.for-every x, for-every y: f(x, y)for-every x, for-every y: f(y, x)Logically equivalent, “for-every x, for-every y” is the same as for-every y, for-every x, so:for-every x, for-every y: f(x, y) is the same asfor-every y, for-every x: f(x, y)By consistently replacing x with y and y with x in “for-every y, for-every x: f(x, y)”, we obtain “for-every x, for-every y: f(y, x)”c. (5 points) Propositional logic.(A and B) => (E and G)not(A) or not(B) or (E and G)logically equivalent, the second statement is obtained from the first one by applying the rule that “X => Y” is the same as “(not X) or Y”4Question 4 40 points.Your job is to color the various sections such that no twoCsections sharing a border have the same color. You can use the colors (Red, Green, Blue).4a. Draw the Constraint Graph for this problem. Use it to separate the problem into subproblemsThe 2 connected subgraphs shown here correspond to 2 separate sub-problems. Each of these can be solved separately and the solutions concatenated to solve the entire problem.4b. 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 of each subproblems.5Subproblem 1:1. Unassigned variables are {A,B,C,D,E}a. A: RV: 3 Deg: 2, B: RV: 3 Deg: 3, C: RV: 3 Deg: 2,D: RV: 3 Deg: 4, E: RV: 3 Deg: 1b. Chosen Variable: D.2. Unassigned variables are {A,B,C,E}a. A: RV: 2 Deg: 2, B: RV: 2 Deg: 3, C: RV: 2 Deg: 2,E: RV: 2 Deg: 1b. Chosen Variable: B.3. Unassigned variables are {A,C,E}a. A: RV: 1 Deg: 2, C: RV: 1 Deg: 2, E: RV: 2 Deg: 1b. Chosen Variable: A or C (Chose A).4. Unassigned variables are {C,E}a. C: RV: 1 Deg: 2, E: RV: 2 Deg: 1b. Chosen Variable: C.5. Unassigned variables are {E}a. E: RV: 2 Deg: 1b. Chosen Variable: E.Subproblem 2:1. Unassigned variables are {F,G,H,I,J}a. F: RV: 3 Deg: 3, G: RV: 3 Deg: 3, H: RV: 3 Deg: 3,I: RV: 3 Deg: 3, J: RV: 3 Deg: 4b. Chosen Variable: J.2. Unassigned variables are {F,G,H,I}a. F: RV: 2 Deg: 3, G: RV: 2 Deg: 3, H: RV: 2 Deg: 3,I: RV: 2 Deg: 3b. Chosen Variable: F or G or H or I (Chose F).3. Unassigned variables are {G,H,I}a. G: RV: 1 Deg: 3, H: RV: 2 Deg: 3, I: RV: 1 Deg: 3b. Chosen Variable: G or I (Chose G).4. Unassigned variables are {H,I}a. H: RV: 1 Deg: 3, I: RV: 1 Deg: 3b. Chosen Variable: H or I (Chose H).5. Unassigned variables are {I}a. I: RV: 1 Deg: 1b. Chosen Variable: I.4c. For each of the subproblems, show how forward chaining is used to select values.Subproblem 1:1. A: RGB, B: RGB, C: RGB, D: RGB, E: RGB2. A: GB, B: GB, C: GB, D: R, E: GB3. A: B, B: G, C: B, D: R, E: GB64. A: B, B: G, C: B, D: R, E: GSubproblem 2:1. F: RGB, G: RGB, H: RGB, I: RGB, J: RGB2. F: GB, G: GB, H: GB, I: GB, J: R3. F: G, G: B, H: GB, I: B, J: R 4. F: G, G: B, H: G, I: B, J: R4d. Assuming you have already assigned A = Red, D = Blue check the arc consistency.A: R, B: RGB, C: RGB, D: B, E: RGBA-BA: R, B: RGB, C: RGB, D: B, E: RGBA-DA: R, B: RGB, C: RGB, D: B, E: RGBB-DA: R, B: RGB, C: RGB, D: B, E: RGBB-CA: R, B: RGB, C: RGB, D: B, E: RGBC-DA: R, B: RGB, C: RGB, D: B, E: RGBD-EA: R, B: RGB, C: RGB, D: B, E: RGBRemaining Legal valuesA: R, B: RGB, C: RGB, D: B, E: