EXERCISE 13 Consider the following decision problem: Monotone 3SAT Instance: a formula in 3-CNF with the property that in each clause, Question: is there some assignment of values to the variables that For example, (a v b v d) ^ (-w v-? v-'d) is a monotone formula, a legal instance of either all literals are positive or all are negative makes the formula true? Monotone 3SAT. By contrast, (-4 V ?? v d) is a 3 SAT formula but not a monotone one. EXERCISE 13 Consider the following decision problem: Monotone 3SAT Instance: a formula in 3-CNF with the property that in each clause, Question: is there some assignment of values to the variables that For example, (a v b v d) ^ (-w v-? v-'d) is a monotone formula, a legal instance of either all literals are positive or all are negative makes the formula true? Monotone 3SAT. By contrast, (-4 V ?? v d) is a 3 SAT formula but not a monotone one