17.5. Linearity of Expectation 613
(a)What is the expected number of true propositions?Hint:LetTibe an indicator for the event that thei-th proposition is true.
(b)Use your answer to prove that foranyset of 7 propositions satisfying the
conditions 1. and 2., there is an assignment to the variables that makes all 7 of the
propositions true.
Problem 17.13.
Aliteralis a propositional variable or its negation. Ak-clauseis anORofkliterals,
with no variable occurring more than once in the clause. For example,
PORQORRORV;is a 4-clause, but
VORQORXORV;
is not, sinceVappears twice.
LetSbe a set ofndistinctk-clauses involvingvvariables. The variables in
differentk-clauses may overlap or be completely different, sokvnk.
A random assignment of true/false values will be made independently to each of
thevvariables, with true and false assignments equally likely. Write formulas inn,
k, andvin answer to the first two parts below.
(a)What is the probability that the lastk-clause inSis true under the random
assignment?
(b)What is the expected number of truek-clauses inS?(c)A set of propositions issatisfiableiff there is an assignment to the variables
that makes all of the propositions true. Use your answer to part (b) to prove that if
n < 2k, thenSis satisfiable.
Problem 17.14. (a)Suppose we flip a fair coin and letNTTbe the number of flips
until the first time two Tails in a row appear. What is ExŒNTTç?
Hint:LetDbe the tree diagram for this process. Explain whyDcan be described
by the tree in Figure 17.8
Use theLaw of Total Expectation17.4.6.