A 3-conjunctive form (3CF) formula is a conjunctive form formula in which each OR-term is an OR of at most 3 variables or negations of variables. Although it may be hard to tell if a propositional formula F is satisfiable, it is always easy to construct a formula C(F) that is in 3-conjunctive form. has at most 24 times as many occurrences of variables as F, and is satisfiable iff F is satisfiable. To construct C.F /, introduce a different new variables for each operator that occurs in F For example, if F ((P XOR Q) XOR R) OR (P AND S) we might use new variables X1, X2 O and A corresponding to the operator occurrences as follows: ((P XOR X_1 Q) XOR X_2 R) OR O (P AND S) A. Next we write a formula that constrains each new variable to have the same truth value as the subformula determined by its corresponding operator. For the example above, these constraining formulas would be X_1 IFF (P XOR Q). X2 IFF (X_1 XOR R). A IFF (P AND S). O IFF (X_2 OR A) (a) Explain why the AND of the four constraining formulas above along with a fifth formula consisting of just the variable O will be satisfiable iff (3.33) is satisfi- able. (b) Explain why each constraining formula will be equivalent to a 3CF formula with at most 24 occurrences of variables. (c) Using the ideas illustrated in the previous parts, explain how to construct C.F/for an arbitrary propositional formula F