3. (15 points) Satisfactory DNF We closed out our lectures on propositional logic by discussing the computational Satisfiability problem. For this problem, we are given as input a formula in CNF and asked to find out if it can be satisfied, i.e., there is a setting of the variables that makes the formula true. This is a very hard problem to solve efficiently and a "good" algorithm would win one million dollars. However it turns out that if the input is given in DNF the problem becomes very easy to solve. First we will build up a little intuition. (a) Write down two different formulas in DNF that can be satisfied. (b) Write down two different formulas in DNF that can not be satisfied (c) Now, describe a fast algorithm that decides if a DNF formula can be satisfied. (Your algorithm should be fast, even for formulas with thousands of variables. So you should not build a truth table.) 3. (15 points) Satisfactory DNF We closed out our lectures on propositional logic by discussing the computational Satisfiability problem. For this problem, we are given as input a formula in CNF and asked to find out if it can be satisfied, i.e., there is a setting of the variables that makes the formula true. This is a very hard problem to solve efficiently and a "good" algorithm would win one million dollars. However it turns out that if the input is given in DNF the problem becomes very easy to solve. First we will build up a little intuition. (a) Write down two different formulas in DNF that can be satisfied. (b) Write down two different formulas in DNF that can not be satisfied (c) Now, describe a fast algorithm that decides if a DNF formula can be satisfied. (Your algorithm should be fast, even for formulas with thousands of variables. So you should not build a truth table.)