Recitation 21 Problem 4. Here are seven propositions V t4 V nTA V Ts V.C7 . V.C5 V".C Note that. 1. Each proposition is the OR of three terms of the form m; or the form - i 2. The variables in the three terms in each proposition are all different Suppose that we assign true/false values to the variables J1,..., rg independently and with equal probability (a) What is the expected number of true propositions? Solution. Each proposition is true unless all three of its terms are false. Thus, each proposition is true with probability () Let Ti be an indicator for the event that the i-th proposition is true. Then the number of true propositions is T1+...+T7 and the expected number is Ex(T1+…+T)=Ex(T1)+…+Ex(T7) 7/8+…+7/8 49/8 (b) Use your answer to prove that there exists an assignment to the variables that makes all of the propositions true Solution. A random variable can not always be less than its expectation, so there must be some assignment such that: T1+..T≥6 This implies that T1 +.. T7=7 for at least one outcome. This outcome is an assignment to the variables such that all of the propositions are trueRecitation 21 6 Problem 4. Here are seven propositions: x1 ∨ x3 ∨ ¬x7 ¬x5 ∨ x6 ∨ x7 x2 ∨ ¬x4 ∨ x6 ¬x4 ∨ x5 ∨ ¬x7 x3 ∨ ¬x5 ∨ ¬x8 x9 ∨ ¬x8 ∨ x2 ¬x3 ∨ x9 ∨ x4 Note that: 1. Each proposition is the OR of three terms of the form xi or the form ¬xi. 2. The variables in the three terms in each proposition are all different. Suppose that we assign true/false values to the variables x1, . . . , x9 independently and with equal probability. (a) What is the expected number of true propositions? Solution. Each proposition is true unless all three of its terms are false. Thus, each proposition is true with probability: � �3 1 7 1 − = 2 8 Let Ti be an indicator for the event that the i­th proposition is true. Then the number of true propositions is T1 + . . . + T7 and the expected number is: Ex (T1 + . . . + T7) = Ex (T1) + . . . + Ex (T7) = 7/8 + . . . + 7/8 1 = 49/8 = 6 8 (b) Use your answer to prove that there exists an assignment to the variables that makes all of the propositions true. Solution. A random variable can not always be less than its expectation, so there must be some assignment such that: 1 T1 + . . . T7 ≥ 6 8 This implies that T1 + . . . + T7 = 7 for at least one outcome. This outcome is an assignment to the variables such that all of the propositions are true