convertir las restricciones bicondicionales en pseudobooleanas (desigualdades / ecuaciones)

Question

Estoy trabajando con pseudo-Boolean y quiero convertir el bi-condicional $(a \land b) \iff c$ a la desigualdad o a la ecuación.

mi intento fue.

En primer lugar, convertir el bi-condicional en dos implica $$((a \land b) \to c) \land (c \to (a \land b))$$ Entonces $$(\lnot(a \land b) \lor c ) \land (\lnot c \lor (a \land b))$$ Entonces, la parte izquierda se convierte en $$(\lnot a \lor\lnot b\lor c)$$ y la parte de la derecha se convierte en $$((\lnot c \lor a) \land (\lnot c \lor b))$$ pero convertir la parte de la derecha en restricciones afectó negativamente a los resultados pseudobooleanos.

Entonces, mi pregunta es, ¿estoy en lo cierto en estos pasos previos o no?

Answer 1

Una restricción pseudobooleana es una restricción de la forma, donde $w_i$ son los pesos, $x_i$ las variables booleanas, $k$ algún valor de comparación y $\#$ algún operador de comparación:

$$\sum_{i=1}^n w_i x_i\,\#\,k$$

Dado que la disyunción $x_1 \lor .. \lor x_n$ corresponde a la restricción pseudobooleana $1 x_1 + ... + 1 x_n \geq 1$ y tomando la negación de una variable booleana $x$ equivale a computar $1-x$ podemos traducir su fórmula booleana en múltiples pseudo-restricciones booleanas.

Ya que en forma normal conjuntiva su fórmula booleana $(a \land b) \iff c$ equivale a la fórmula booleana $(\lnot a\lor\lnot b\lor c)\land(\lnot c\lor a)\land(\lnot c\lor b)$ podemos traducir cada cláusula y obtener

$$(1-a)+(1-b)+c\geq 1$$

$$(1-c)+a\geq 1$$

$$(1-c)+b\geq 1$$

O bien, se ha de utilizar la forma de la suma ponderada:

$$-1 a + -1 b + 1 c\geq -1$$

$$1 a + -1 c\geq 0$$

$$1 b + -1 c\geq 0$$

No sé si la forma alternativa, la forma normal disyuntiva, sería útil en absoluto.

Answer 2

Entonces, mi pregunta es, ¿estoy en lo cierto en estos pasos previos o no?

Tienes razón. Por definición $X\leftrightarrow Y\equiv (\lnot X\lor Y)\land(\lnot Y\lor X)$ ...así que... $$(a\land b)\leftrightarrow c ~\equiv~ (\lnot a\lor\lnot b\lor c)\land(\lnot c\lor a)\land(\lnot c\lor b)$$

---

Utilizando la definición alternativa que $X\leftrightarrow Y \equiv (X\land Y)\lor(\lnot X\land\lnot Y)$ , dará... $$(a\land b)\leftrightarrow c ~\equiv~ ( a\land b\land c)\lor(\lnot a\land\lnot c)\lor(\lnot b\land\lnot c)$$