548 CHAPTER 8 Discrete Probability
- A system has four components numbered 1, 2, 3, and 4 as shown:
The system performs if either component 1 or component 2 performs or if both com-
ponents 3 and 4 perform. Each component has probability 0.9 of performing, and all
the components are independent. What is the probability the system performs?- Recall the 3-satisfiability problem: We are given a set of m clauses, each of which
contains three boolean variables connected together by OR's; the clauses are then con-
nected together by AND's. For example, we might want to assign truth values to the
variables X 1 , X2 ..... X 5 so that the expression
(X 1 OR X 3 OR -X 5 ) AND (X 1 OR -X 2 OR X 4 )
is true. Here, there are only m = 2 clauses and n = 5 variables. In general, for n vari-
ables (not counting their complements separately), we might have to try as many as 2n
truth assignments to the variables to determine whether the clauses can all be simulta-
neously satisfied. We can assume that no variable appears more than once in the same
clause (whether complemented or not). If X appears with -X in the same clause, then
the clause is automatically satisfied. If X appears more than once in the same clause,
that is redundant, so the clause does not truly contain three variables. (As an example
of how probability theory can help to solve a problem that otherwise would seem to re-
quire examining an exponentially large number of cases, consider the following idea:
For each variable, toss a fair coin. If the coin comes up heads, then set the variable
to TRUE and its complement to FALSE. If it comes up tails, then make the opposite
assignment). What is the expectation of the number of clauses that will be satisfied?