PUERTA | PUERTA-CS-2007 | Pregunta 48

¿Cuál de las siguientes es VERDADERA acerca de las fórmulas en forma normal conjuntiva?
(A) Para cualquier fórmula, hay una asignación de verdad para la cual al menos la mitad de las cláusulas se evalúan como verdaderas.
(B) Para cualquier fórmula, hay una asignación de verdad para la cual todas las cláusulas se evalúan como verdaderas
(C) Hay una fórmula tal que para cada asignación de verdad, como máximo una cuarta parte de las cláusulas se evalúan como verdaderas.
(D) Ninguna de las anteriores

Respuesta: (A)
Explicación: Podemos probar fácilmente que para cualquier fórmula, hay una asignación de verdad para la cual al menos la mitad de las cláusulas se evalúan como verdaderas.

Prueba:
Considere una asignación de verdad arbitraria. Para cada una de sus cláusulas ‘j’, introduzca una variable aleatoria.
X _j = 1 si se cumple la cláusula ‘j’
X _j = 0 en caso contrario

Entonces, X = sumatoria de (j * X _j ) es el número de cláusulas satisfechas.
Dada cualquier cláusula ‘c’, no se cumple solo si todos sus literales constituyentes ‘k’ se evalúan como falsos ya que están unidos por el operador OR.
Ahora, debido a que cada literal dentro de una cláusula tiene una probabilidad de 1/2 de evaluarse como verdadero independientemente del valor de verdad de cualquiera de los otros literales, la probabilidad de que todos sean falsos es (1/2) ^k .
Por lo tanto, la probabilidad de que ‘c’ se cumpla = 1 − (1/2) ^k
Entonces, E(X _j ) = 1 * (1/2) ^k = (1/2) ^k

Por lo tanto, E(X _j ) >= 1/2

Suma en ambos lados para obtener E(X).

Por lo tanto, tenemos E(X) = sumatoria de (j * X _j ) >= m/2 donde ‘m’ es el número de cláusulas.
E(X) representa el número esperado de cláusulas satisfechas.

Así, debe existir una cesión que satisfaga al menos la mitad de las cláusulas.

Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Cuestionario de esta pregunta