Cómo demostrar que si $\neg b = a \land d$ entonces $a \land \neg b = \neg b$ y $b \land \neg a = \neg a$

Question

Soy nuevo en el álgebra booleana y estoy teniendo problemas para demostrar el siguiente teorema simple. Muchas gracias por cualquier ayuda.

Si $\neg b = a \land d$ entonces $a \land \neg b = \neg b$ y $b \land \neg a = \neg a$ .

Así es como lo he resuelto:

$\neg b = a \land d$

$a \land \neg b = a \land (a \wedge d)$

$a \land \neg b = a \land d$

$a \land \neg b = \neg b$

Esto demuestra la primera expresión (¿creo?).

Entonces, para la segunda expresión, partimos de la primera.

$a \land \neg b = \neg b$

$\neg (a \land \neg b) = b$

$\neg a \lor b = b$

... y aquí me quedo atascado?

¿Cómo puedo pasar de $\neg a \lor b = b$ a $b \land \neg a = \neg a$ ?

Ahora, si pensamos en esto en términos de conjuntos, puedes ver cómo $A^{c} \cup B = B$ sólo puede ser cierto si $A^{c} \subseteq B$ y por lo tanto se puede ver cómo $b \land \neg a = \neg a$ puede tener. Pero no estoy seguro de cómo probar esto.

Answer 1

La primera parte funciona bien.

Para la segunda, lo siguiente funcionará, pero no sé lo que dice su conjunto de axiomas y reglas de inferencia.

assumption           1 ¬b=(a∧d) 
introduce "V" in 1   2 (a V ¬b)=(aV(a∧d)).
2 (xV(x^y))=x        3 (a V ¬b)=a
3 ¬¬a=a              4 ¬¬(a V ¬b)=¬¬a
4 ¬(aVb)=(¬a^¬b)     5 ¬(¬a∧¬¬b)=¬¬a
canceling ¬'s in 5   6 (¬a∧¬¬b)=¬a
6 ¬¬a=a              7 (¬a∧b)=¬a
7 (x^y)=(y^x)        8 (b∧¬a)=¬a

Answer 2

Lo que ocurre con el álgebra booleana es que no siempre hay un atajo (a menos que se manifiesten algunos resultados matemáticos muy monumentales que nos sorprendan a todos).

En tu primera pregunta, has encontrado un buen atajo aplicando $a \land \dots$ a ambos lados. Pero a veces hay que escribir las tablas de verdad y nada es más rápido. Es más importante saber cómo hacer esto de forma lenta y sistemática que memorizar los atajos.

Así que para hacer la segunda pregunta de la manera más directa, basta con comprobar los 8 casos de $a$ , $b$ y $d$ :

$$\DeclareMathOperator{T}{\color{blue}{\text{T}}} \DeclareMathOperator{F}{\color{red}{\text{F}}} \begin{array} {ccc|c|c|c} a & b & d & \lnot b = a \land d & b \land \lnot a = \lnot a & (\lnot b = a \land d) \rightarrow (b \land \lnot a = \lnot a) \\ \T & \T & \T & \F & \T & \T\\ \T & \T & \F & \F & \T & \T\\ \T & \F & \T & \T & \T & \T\\ \T & \F & \F & \F & \T & \T\\ \F & \T & \T & \T & \T & \T\\ \F & \T & \F & \T & \T & \T\\ \F & \F & \T & \F & \F & \T\\ \F & \F & \F & \F & \F & \T\\ \end{array}$$

Así que puedes ver que la implicación siempre se mantiene.

Answer 3

Así es como yo lo haría: por cálculo.

$\newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}}$ Se nos da que $$\tag 0 \lnot b \;\equiv\; a \land d$$ Para la primera parte, empezamos por el lado más complejo, y tratamos de simplificar $\;a \land \lnot b\;$ : $$\calc a \land \lnot b \calcop\equiv{using $\ref 0 $ -- the only thing we know} a \land a \land d \calcop\equiv{logic: simplify} a \land d \calcop\equiv{using $\ref 0 $ -- to get us to our goal} \lnot b \endcalc$$ Esto demuestra la primera parte.

Ahora la segunda parte se puede hacer de manera similar, pero también tendrá que utilizar DeMorgan y la absorción.