A formula is satisfiable if there exists some variable assignment that makes it true: that is, there is some row of its truth table that comes out to true out to true instead of false. Determining whether an arbitrary boolean formula is satisfiable is called the satisfiability problem. This is a famously hard problem in computer science - nobody knows a good way of doing this that is much better than trying assignments until one succeeds, and fabulous prizes await anybody who comes up with a better method. i. Make a truth table for the formula (a b) Lambda (b c) Lambda (a c). The formula is satisfiable if at least one row evaluates to true. Is it satisfiable? (Complete the truth table even if you find a satisfying assignment.) ii. Suppose a truth table must be created to know for sure whether a formula is satisfiable. If the formula has n variables, how many rows will the truth table have, as a function of n? iii. The satisfiability problem is not hard for all formulas: some formulas are easy, even if they have a lot of variables, because they have a structure that makes it easy to infer what the the values of the variables must be. Consider, for example, the 100-clause formula: x_1 Lambda (x_1 x_2) Lambda (x_2 x_3) Lambda ... Lambda (x_99 x_100) How many satisfying assignments does this formula have? How do you know