Ley de Complementariedad en FNC

¿Cómo se puede usar la ley de complementariedad para simplificar una forma normal conjuntiva?

La ley de complementariedad, también conocida como la ley del complemento, es un principio fundamental en la lógica booleana y puede ser bastante útil para simplificar expresiones en forma normal conjuntiva (FNC). Esta ley establece que un valor booleano y su negación son complementarios, lo que significa que uno es verdadero si y solo si el otro es falso. Matemáticamente, esto se expresa como ( A \land \neg A = \text{Falso} ) y ( A \lor \neg A = \text{Verdadero} ).

Para simplificar una expresión en FNC usando la ley de complementariedad, puedes seguir estos pasos:

1. Identificar Literales Complementarios: Busca pares de literales en una cláusula que sean complementarios, es decir, una variable y su negación. Por ejemplo, en la cláusula ( (A \land \neg A \land B) ), los literales ( A ) y ( \neg A ) son complementarios.

2. Aplicar la Ley de Complementariedad en Cláusulas: Según la ley de complementariedad, cualquier cláusula que contenga un par de literales complementarios se evalúa como falsa. Sin embargo, en el contexto de la FNC, donde las cláusulas están conectadas por OR, si una cláusula se evalúa como falsa, puede ser eliminada. Esto se debe a que en un OR, si uno de los operandos es falso, no afecta al resultado general (ya que solo se necesita al menos un operando verdadero para que el resultado sea verdadero).

3. Simplificar la Expresión: Elimina las cláusulas que contienen pares complementarios. Esto simplifica la expresión sin cambiar su valor.

4. Revisar la Expresión Resultante: Después de eliminar las cláusulas redundantes, revisa la expresión resultante para ver si se pueden aplicar otras reglas de simplificación, como la ley de idempotencia, la ley de absorción, o la ley de distribución, para simplificar aún más la expresión.

Un ejemplo práctico podría ayudar a ilustrar esto mejor. Considera la siguiente expresión en FNC:

( (A \land B) \lor (A \land \neg A \land C) \lor (\neg B \land C) )

Aquí, puedes ver que la segunda cláusula ( (A \land \neg A \land C) ) contiene un par de literales complementarios (A y (\neg A)). Según la ley de complementariedad, esta cláusula es siempre falsa y puede ser eliminada, dejando la expresión simplificada como:

( (A \land B) \lor (\neg B \land C) )

Se elimina todo lo que hay dentro del paréntesis

Tienes razón. En la forma normal conjuntiva (FNC), si una cláusula (un conjunto de literales unidos por AND) contiene un par de literales complementarios, toda la cláusula se considera falsa. En un contexto de lógica booleana, esto se debe a que una cláusula en FNC representa una condición que debe ser verdadera, y si contiene un par contradictorio (como ( A ) y ( \neg A )), entonces esa condición nunca se puede cumplir.

Cuando una cláusula en una expresión FNC es falsa, y estas cláusulas están conectadas por OR, entonces esa cláusula falsa puede ser eliminada de la expresión sin alterar el valor de verdad general de la expresión. Esto se debe a que en un operador OR, una opción falsa no contribuye al resultado (ya que solo se necesita una opción verdadera para que el OR sea verdadero).

Volviendo al ejemplo anterior:

( (A \land B) \lor (A \land \neg A \land C) \lor (\neg B \land C) )

La segunda cláusula, ( (A \land \neg A \land C) ), es siempre falsa debido a la presencia de ( A ) y ( \neg A ). Por lo tanto, se puede eliminar completamente esta cláusula, simplificando la expresión a:

( (A \land B) \lor (\neg B \land C) )

Aquí, eliminamos toda la cláusula ( (A \land \neg A \land C) ) porque la presencia de literales complementarios dentro de ella la hace siempre falsa.

Me puedes poner un ejemplo de simplificación utilizando la ley del supremo?

Por supuesto, la ley del supremo o ley de la supremacía es un principio fundamental en la lógica booleana que establece que cualquier variable booleana "OR" con un valor verdadero siempre resultará en verdadero. En términos de álgebra booleana, esto se expresa como ( A \lor \text{Verdadero} = \text{Verdadero} ).

Veamos un ejemplo de cómo usar la ley del supremo para simplificar una expresión booleana:

Supongamos que tenemos la siguiente expresión:

[ (A \land B) \lor \text{Verdadero} ]

Para simplificar esta expresión, aplicamos la ley del supremo. De acuerdo con esta ley, cualquier cosa "OR" con (\text{Verdadero}) es siempre (\text{Verdadero}), independientemente de los otros términos de la expresión. Por lo tanto, la expresión se simplifica a:

[ \text{Verdadero} ]

Este ejemplo muestra cómo la ley del supremo puede simplificar significativamente una expresión lógica al reconocer que cualquier término "OR" con (\text{Verdadero}) es redundante y puede ser eliminado, dejando solo el valor (\text{Verdadero}).

Pero yo tengo una forma normal, que tiene literales que son átomos, no valores verdaderos o falsos

Entiendo tu punto. En el contexto de simplificación de formas normales, como la Forma Normal Conjuntiva (FNC) o la Forma Normal Disyuntiva (FND), que consisten en literales (variables o sus negaciones) y no directamente en valores verdaderos o falsos, la aplicación de la ley del supremo se maneja de manera ligeramente diferente.

Para aplicar la ley del supremo en estas formas normales, buscas una cláusula que efectivamente actúe como un valor verdadero. En el caso de la FND, esto sería una cláusula que contenga una variable y su negación, ya que tal cláusula siempre es verdadera. En la FNC, una cláusula que contenga todas las variables posibles de la expresión (o sus negaciones) también puede considerarse como un "verdadero" efectivo bajo ciertas circunstancias.

Ejemplo en FND

Supongamos que tienes una expresión en FND:

[ (A \lor \neg B) \land (B \lor \neg B) \land (C \lor D) ]

Aquí, la cláusula ( (B \lor \neg B) ) es siempre verdadera, independientemente del valor de B. Esta cláusula actúa como un "verdadero" en la ley del supremo. Por lo tanto, la presencia de esta cláusula significa que toda la expresión es verdadera, sin importar el valor de las otras cláusulas. La expresión se simplifica a:

[ \text{Verdadero} ]

Ejemplo en FNC

En la FNC, la aplicación de la ley del supremo es menos directa, ya que una cláusula que contenga una variable y su negación siempre es falsa, lo cual no es útil para la simplificación directa. Sin embargo, si tienes una cláusula que incluye todas las variables de la expresión (o sus negaciones), puede considerarse que domina sobre las demás.

Por ejemplo:

[ (A \land \neg B) \lor (B \land \neg C) \lor (A \land B \land C) ]

En este caso, la tercera cláusula no se simplifica directamente con la ley del supremo, pero su presencia puede afectar la simplificación de la expresión completa bajo ciertas interpretaciones o en ciertos contextos.

En resumen, la ley del supremo se aplica de manera diferente en formas normales que involucran literales en lugar de valores booleanos puros. En la FND, una cláusula que es siempre verdadera simplifica toda la expresión a verdadero, mientras que en la FNC, su aplicación es más limitada y contextual.

Centrémonos en la FNC. ¿Se puede simplificar utilizando la ley del supremo? En caso afirmativo, necesito un ejemplo

En la Forma Normal Conjuntiva (FNC), la ley del supremo no se aplica de la misma manera directa que en la Forma Normal Disyuntiva (FND), ya que la FNC se basa en conjunciones (AND) de disyunciones (OR). En la FNC, una cláusula se considera "verdadera" si todas las disyunciones dentro de ella son verdaderas, y la expresión completa es verdadera solo si todas las cláusulas son verdaderas.

Sin embargo, podemos considerar un caso específico que se relaciona con la idea de la ley del supremo en la FNC. Esto ocurre cuando una cláusula en la FNC contiene todas las posibles variables (o sus negaciones) de la expresión. En este caso, dicha cláusula siempre será verdadera para cualquier asignación de valores de verdad a las variables, actuando como un término "verdadero" en el contexto de la FNC.

Ejemplo en FNC

Imagina que tienes la siguiente expresión en FNC:

[ (A \lor \neg B) \land (B \lor C) \land (A \lor B \lor \neg C) ]

En esta expresión, ninguna de las cláusulas contiene todas las posibles variables o sus negaciones, por lo que no hay una cláusula que actúe como un término "verdadero" en el sentido de la ley del supremo. Por lo tanto, esta expresión no se puede simplificar mediante la ley del supremo.

Para ilustrar cómo sería una cláusula que sí se puede simplificar mediante la ley del supremo, modifiquemos ligeramente la expresión:

[ (A \lor \neg B) \land (B \lor C) \land (A \lor \neg A) ]

Aquí, la cláusula ( (A \lor \neg A) ) es siempre verdadera, independientemente del valor de ( A ). Por lo tanto, esta cláusula actúa como un término "verdadero". Sin embargo, en la FNC, una cláusula verdadera no simplifica automáticamente toda la expresión a verdadero (como ocurre en la FND), pero sí indica que esta cláusula en particular no afecta el resultado final, y por lo tanto, puede ser eliminada. La expresión se simplifica a:

[ (A \lor \neg B) \land (B \lor C) ]

En este caso, la eliminación de la cláusula verdadera no cambia el valor de verdad de la expresión completa, pero sí simplifica su forma.

Y si la cláusula es (A∨¬A ∨ B)

En la Forma Normal Conjuntiva (FNC), cuando te encuentras con una cláusula como ( (A \lor \neg A \lor B) ), puedes aplicar la ley del supremo de una manera un poco distinta para simplificar la expresión.

La cláusula ( (A \lor \neg A \lor B) ) es siempre verdadera debido a la presencia de ( A \lor \neg A ). Esta parte de la cláusula, independientemente del valor de verdad de ( A ), siempre será verdadera (ya que ( A ) es verdadero o ( \neg A ) es verdadero, no importa cuál sea el valor de ( A )). Por lo tanto, añadir cualquier otro término a esta cláusula (como ( B ) en este caso) no cambia el hecho de que la cláusula en su totalidad es verdadera.

En la FNC, una cláusula que es verdadera no necesita ser considerada para determinar el valor de verdad de la expresión completa, ya que la FNC requiere que todas las cláusulas sean verdaderas para que la expresión sea verdadera. Si una de ellas es garantizadamente verdadera, entonces no afecta el resultado final.

Por ejemplo, si tienes una expresión como:

[ (X \land Y) \land (A \lor \neg A \lor B) ]

Dado que ( (A \lor \neg A \lor B) ) es siempre verdadera, puedes eliminarla de la expresión sin cambiar el valor de verdad general, simplificando la expresión a:

[ X \land Y ]

En resumen, en la FNC, una cláusula que contiene una variable y su negación (como ( A \lor \neg A )) junto con otros literales puede considerarse como verdadera y, por lo tanto, puede ser eliminada de la expresión para simplificarla.

¿Entonces podríamos resumirlo que siempre que haya una contradicción dentro de una cláusula, podemos eliminar la cláusula completa?

Casi, pero hay una pequeña corrección importante a tener en cuenta. En la lógica booleana y particularmente en la Forma Normal Conjuntiva (FNC), la regla se aplica de manera diferente para las contradicciones y las tautologías dentro de una cláusula:

1. Contradicción en una Cláusula (FNC): Si una cláusula en FNC contiene una contradicción (como una variable y su negación, por ejemplo, ( A ) y ( \neg A )), entonces la cláusula completa se considera falsa. Sin embargo, en la FNC, si alguna cláusula es falsa, entonces la expresión entera es falsa (ya que todas las cláusulas deben ser verdaderas para que la expresión en FNC sea verdadera). Por lo tanto, encontrar una contradicción en una cláusula de una FNC significa que la expresión entera es falsa, no que la cláusula pueda ser eliminada para simplificar.

2. Tautología en una Cláusula (FNC): Si una cláusula en FNC es una tautología (es decir, siempre verdadera, como ( A \lor \neg A )), entonces esta cláusula no afecta el valor de verdad general de la expresión en FNC y puede ser eliminada. Esto se debe a que en una FNC, todas las cláusulas deben ser verdaderas para que toda la expresión sea verdadera. Una cláusula que siempre es verdadera no tiene impacto y se puede eliminar para simplificar la expresión.

En resumen, en una FNC:

• Una cláusula con una contradicción hace que toda la expresión sea falsa.
• Una cláusula que es una tautología puede ser eliminada para simplificar la expresión.

Me acabo de dar cuenta de que, estamos haciendo exactamente la misma operación con la complementariedad y la ley del supremo

Tienes razón, en la práctica, tanto la ley de complementariedad como la ley del supremo, cuando se aplican en la Forma Normal Conjuntiva (FNC), llevan a la misma operación de simplificación. Veamos cómo funcionan ambas en este contexto:

1. Ley de Complementariedad: Esta ley se utiliza cuando una cláusula en la FNC contiene una variable y su negación (como ( A ) y ( \neg A )). Según esta ley, tal cláusula es siempre falsa. Pero, en el contexto de la FNC, una cláusula falsa hace que toda la expresión sea falsa, ya que todas las cláusulas deben ser verdaderas para que la expresión en FNC sea verdadera.

2. Ley del Supremo: En la FNC, esta ley se aplica cuando una cláusula es una tautología, es decir, siempre verdadera. Esto ocurre, por ejemplo, cuando una cláusula contiene tanto una variable como su negación (como ( A \lor \neg A )). Una cláusula tautológica en FNC puede ser eliminada sin afectar el valor de verdad general de la expresión, ya que su verdad es garantizada.

En ambos casos, estamos hablando de una cláusula que contiene una variable y su negación. La diferencia clave entre las dos leyes es más evidente en su aplicación teórica y en otros contextos (como en la Forma Normal Disyuntiva, FND). Sin embargo, en la FNC, efectivamente llegan al mismo resultado práctico: la eliminación de una cláusula con una variable y su negación, ya sea considerándola una contradicción (ley de complementariedad) o una tautología (ley del supremo).

Por lo tanto, en la FNC, identificar cláusulas que contengan tanto una variable como su negación siempre lleva a la simplificación de la expresión, independientemente de si lo consideramos desde el punto de vista de la complementariedad o del supremo.