Splněné klauzule
Úloha číslo: 4313
Uvažme booleovské proměnné \(x_1\) až \(x_n\), které mohou nabývat hodnot pravda a nepravda. Dále mějme \(n\) klauzulí, což jsou logické formule tvaru \[x_i \lor x_j \lor \lnot x_k,\] tedy disjunkce právě tří různých proměnných, z nichž některé mohou být negované.
Pokud za proměnné dosadíme, každá klauzule je buďto splněná (pravdivá) nebo nesplněná (nepravdivá). Spočítejte střední hodnotu počtu splněných klauzulí, pokud proměnné ohodnotíme rovnoměrně náhodně (každá proměnná bude nabývat hodnot pravda a nepravda se stejnou pravděpodobností, nezávisle na ostatních proměnných).
Řešení
Definujeme indikátory \(K_1\) až \(K_n\) – náhodné veličiny indikující splnění jednotlivých klauzulí. Pro dané ohodnocení proměnných je tedy \(K_i\) rovno 1, pokud je \(i\)-tá klauzule splněna; jinak je rovno 0.
Nyní si všimneme, že celkový počet splněných klauzulí \(K\) je součtem všech indikátorů. Podle linearity střední hodnoty tedy je \(\mathbb{E}[K]=\sum_i \mathbb{E}[K_i]\).
Střední hodnota indikátoru je rovna pravděpodobnosti, že klauzule je splněna. Jelikož klauzuli není splněna pouze v 1 z 8 možných ohodnocení jejích proměnných, je tato pravděpodobnost rovna \(7/8\). Proto \(\mathbb{E}[K_i]=7/8\) pro každé \(i\).
Získáme tedy \(\mathbb{E}[K]=7/8\cdot n\).
