MHB Prove that the statement is always true using the rules of boolean algebra

[mathmari]

Hey!

I want to prove by using the rules of boolean algebra that the following statement is always true $$\{b\land [\neg a\Rightarrow \neg b]\} \Rightarrow a$$

Since we have to use the rules of boolean algebra, we cannot use the truth table, right?

Could you give me a hint how we could show that?

:unsure:

 

[I like Serena]

Note that $p\to q$ is the same a $\lnot p\lor q$.

Btw, can it be that there is a typo? Can it be that it should be $\{b, [\neg a\Rightarrow \neg b]\} \Rightarrow a$?

 

[mathmari]

Note that $p\to q$ is the same a $\lnot p\lor q$.

Btw, can it be that there is a typo? Can it be that it should be $\{b, [\neg a\Rightarrow \neg b]\} \Rightarrow a$?

Before the statement there is the following text:

Proofs of contradiction often have the following pattern:
You know that a statement $b$ is correct, and would like to show that a statement $a$ is also correct. We consider then that $a$ is not correct, and show that it follows that $b$ is wrong (“contradiction”), and then we conclude that $a$ is correct. So the given statement is correct, isn't it? :unsure:

We have that \begin{align*}\{b\land [\neg a\Rightarrow \neg b]\} \Rightarrow a &\equiv \{b\land [a\lor \neg b]\} \Rightarrow a \\ & \equiv \{b\land a\lor b\land \neg b]\} \Rightarrow a \\ & \equiv \{b\land a \}\Rightarrow a \\ & \equiv \neg \{b\land a \}\lor a \\ & \equiv \neg b\lor \neg a \lor a \\ & \equiv \neg b\end{align*}

Is everything correct? :unsure:

 

[I like Serena]

Ah, I assumed those curly braces were intended to indicate a set of boolean statements.
I guess it's also possible that they are intended as alternatives to parentheses.
In that case, I believe it is correct.
It also means that the statement is not always true...

EDIT: the last step is not correct as SquareOne pointed out.

 

[SquareOne1]

\[ \{ b \land [\neg a \to \neg b] \} \to a \\ \{ b \land [a \lor \neg b] \} \to a \\ \{ [b \land a] \lor [b \land \neg b] \} \to a \\ \{ [b \land a] \lor \text{False} \} \to a \\ [b \land a] \to a \\ \neg [b \land a] \lor a \\ \neg b \lor \neg a \lor a \\ \neg b \lor \text{True} \\ \text{True} \]

 

[mathmari]

Ohh I see! Thanks a lot! (Sun)

 

[solakis1]

\[ \{ b \land [\neg a \to \neg b] \} \to a \\ \{ b \land [a \lor \neg b] \} \to a \\ \{ [b \land a] \lor [b \land \neg b] \} \to a \\ \{ [b \land a] \lor \text{False} \} \to a \\ [b \land a] \to a \\ \neg [b \land a] \lor a \\ \neg b \lor \neg a \lor a \\ \neg b \lor \text{True} \\ \text{True} \]

This is not a proof by contradiction using boolean algebra
In boolean algebra the symbol $\rightarrow$ does not exist
However it exists in propositional calculus
The operational symbols in Boolean algebra are: $\wedge...\vee$...,(') for complement of a boolean variable x i.e x'
and the constants T or F or better 0 or 1
And of course the pridicate of equality
The axioms you can find in any book or inthe internet

 

[solakis1]

Before the statement there is the following text:

Proofs of contradiction often have the following pattern:
You know that a statement $b$ is correct, and would like to show that a statement $a$ is also correct. We consider then that $a$ is not correct, and show that it follows that $b$ is wrong (“contradiction”), and then we conclude that $a$ is correct. So the given statement is correct, isn't it? :unsure:

We have that \begin{align*}\{b\land [\neg a\Rightarrow \neg b]\} \Rightarrow a &\equiv \{b\land [a\lor \neg b]\} \Rightarrow a \\ & \equiv \{b\land a\lor b\land \neg b]\} \Rightarrow a \\ & \equiv \{b\land a \}\Rightarrow a \\ & \equiv \neg \{b\land a \}\lor a \\ & \equiv \neg b\lor \neg a \lor a \\ & \equiv \neg b\end{align*}

Is everything correct? :unsure:

Proof by contradion for the statement $b\Rightarrow a$ and following the pattern that you mentioned above is the following formula $[b\wedge(\neg a\Rightarrow\neg b)]\Rightarrow (b\Rightarrow a)$ and not the statement
\begin{align*}\{b\land [\neg a\Rightarrow \neg b]\} \Rightarrow a\end{align*}
And that statement (your stetement ) can be proved only by using propositional calculus and not boolean algebra
Boolean algebra does not include $\Rightarrow$ as an operational symbol

 

[solakis1]

Note that $p\to q$ is the same a $\lnot p\lor q$.

Btw, can it be that there is a typo? Can it be that it should be $\{b, [\neg a\Rightarrow \neg b]\} \Rightarrow a$?

does boolean algebra include $\rightarrow$ as one of its operational symbols
You can use logic (propositinal and predicate calculus) to prove all the formulas in boolean algebra but not the opposite

 

[solakis1]

Hey!

I want to prove by using the rules of boolean algebra that the following statement is always true $$\{b\land [\neg a\Rightarrow \neg b]\} \Rightarrow a$$

Since we have to use the rules of boolean algebra, we cannot use the truth table, right?

Could you give me a hint how we could show that?

:unsure:

This is not a formula of contradiction:
All formulas of contradiction are the following:

1)$(\neg b\rightarrow(a\wedge \neg a))\rightarrow b$

2)$(\neg b\rightarrow b)\rightarrow b$

3)$(b\rightarrow\neg b)\rightarrow\neg b$

4)$[(b\wedge\neg a)\rightarrow (r\wedge\neg r)]\rightarrow(b\rightarrow a)$

5) $[(b\wedge\neg a)\rightarrow \neg b)]\rightarrow(b\rightarrow a)$

6) )$[(b\wedge\neg a)\rightarrow a]\rightarrow(b\rightarrow a)$

You can check all the above formulas by using propositional calculus