Exercise 1 Pessimistic Sat (20 credits) A literal in a clause is negative if it is of the form $ eg x$ for a variable $x$, and positive (that is, a non-negated variable) otherwise. For example, in the clause $ eg x \vee eg y \vee z$, the literals $ eg x$ and $ eg y$ are negative, and the literal $2$ is positive. We call a clause pessimistic if it contains at most one positive literal. For example, the clauses $ eg x \vee eg y \vee z$ and $ eg x \vee eg y$ as well as the one-element) clauses $x$ and $ eg y$ are pessimistic. Consider the following variant PESSIMISTIC SAT of the CSAT problem: Input: A formula $F$ that is a conjunction of pessimistic clauses. Problem: Is $F$ satisfiable? Prove that PESSIMISTIC SAT is in P. cs.vs. 1248|