- We have a set of Boolean variables B = {b₁,..., bn} that are used to form a set of [5 ma disjunctions D = {d₁,..., dm}

[answerhappygod]

We Have A Set Of Boolean Variables B B Bn That Are Used To Form A Set Of 5 Ma Disjunctions D D Dm 1 (118.67 KiB) Viewed 60 times

- We have a set of Boolean variables B = {b₁,..., bn} that are used to form a set of [5 ma disjunctions D = {d₁,..., dm} (boolean formulas constructed using only the OR- operator, for example (b3 V-b5 V-bs)). We want to compute a truth assignment (i.e., assign true or false to each Boolean variable) such that the largest number of disjunctions evaluate to true. Example: Boolean variables B: b₁, b2, b3, b4 Disjunctions D: (b₁ V b₂), (b3 V-b4), (b₁ V b3 V b4), (b3 V-b4), (b₁), (-b3 V b₁) In the example, if we set b₁, b2 and b4 to true and b3 to false, we satisfy 5 of the 6 disjunctions: only (b3 V-b4) evaluates to false, since both b3 and -b4 (i.e., not b4) evaluate to false. There are multiple truth assignments where the same number of disjunctions evaluate to true. Setting all variables to false results in only 4 of the 6 disjunctions evaluating to true and thus doesn't make the largest number of them evaluate to true. Construct a counterexample to show that the following algorithm doesn't com- pute a truth assignment where the largest set of disjunctions evaluate to true: sort the variables in non-increasing order based on the number of disjunctions that contain them (ties are broken lexicographically). Let p, (and n) denote the number of disjunctions containing variable b, (resp. b) that don't yet evaluate to true based on previously set variables. If pin, set b; to true and set it to false otherwise. 1: def TRUTHASSIGNMENT(B, D) 2: Sort B by the number of disjunctions that contains each variable in non-increasing order and renumber such that |b₁|2|b₂|2|bu| for i1; i<n; i++ do Compute p, and n 3: 4: 5: 6: 7: if pin, then set b, to true else set b; to false return B.