Prоblem 1: DNF-SAT (4 pоints) Recаll thаt а prоpositional formula is in Disjunctive Normal Form (DNF) if it is a disjunction of one or more clauses, where each clause is a conjunction of one or more literals. For example, the formula (phi = (x_1 land neg x_2) lor (neg x_1 land x_3) lor (x_3 land neg x_3 land x_4)) is in DNF. The formula (phi) is satisfiable: the first clause ((x_1 land neg x_2)) can be satisfied by setting (x_1 = text{True}) and (x_2 = text{False}). Let DNF-SAT be the problem of determining the satisfiability of boolean formulas in DNF. Show that DNF-SAT (in mathbf{P}) by outlining a polynomial-time algorithm directly. Hint: For the formula (phi) above, which clause is unsatisfiable and why? In general, for a DNF formula (varphi = C_1 lor C_2 lor dots lor C_m) to be satisfiable, what can you say about the satisfiability of its individual clauses (C_i)? Under what condition is a single clause, say (C_i = l_1 land l_2 land dots land l_k), unsatisfiable? Problem 2: Robot Logic (6 points) A simple robot operates based on the following rules: If the battery is low ((B)), then the robot seeks a charging station ((S)). If the battery is not low ((neg B)), then the robot continues its current task ((C)). If the robot seeks a charging station ((S)), a warning light is on ((L)). Given these rules, determine if it is possible for the robot to be continuing its current task and for the warning light to be on at the same time. Convert the question to the satisfiability problem of a propositional logic formula. Write the formula in CNF. (3 points) Apply the Resolution algorithm to check for satisfiability. (3 points) Congratulations, you are almost done with Quiz 7. DO NOT end the Honorlock session until you have submitted your work to Gradescope. When you have answered all questions: Use your smartphone to scan your answer sheet and save the scan as a PDF. Make sure your scan is clear and legible. Submit your PDF to Gradescope as follows: Email your PDF to yourself or save it to the cloud (Google Drive, etc.). Click this link to go to Gradescope to submit your work: Quiz 7 Return to this window and click the button below to agree to the honor statement. Click Submit Quiz to end the exam. End the Honorlock session.