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

In summary: Rightarrow a$" is always true. However, I cannot do so using boolean algebra. I believe that I need to use propositional calculus in order to do so.
  • #1
mathmari
Gold Member
MHB
5,049
7
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:
 
Physics news on Phys.org
  • #2
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$? 🤔
 
  • #3
Klaas van Aarsen said:
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:
 
  • #4
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. 🤨
 
Last edited:
  • #5
\[ \{ 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} \]
 
Last edited:
  • #6
Ohh I see! Thanks a lot! (Sun)
 
  • #7
SquareOne said:
\[ \{ 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
 
  • #8
mathmari said:
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
 
  • #9
Klaas van Aarsen said:
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
 
  • #10
mathmari said:
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
 

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

1. What is boolean algebra?

Boolean algebra is a branch of mathematics that deals with logic and logical operations. It is based on the concept of binary values, where variables can only have two possible values: true or false.

2. How is boolean algebra used in science?

Boolean algebra is used in science, particularly in computer science and engineering, to represent and manipulate logical statements. It is also used in the design and analysis of digital circuits and computer programs.

3. What are the basic rules of boolean algebra?

The basic rules of boolean algebra include the commutative, associative, and distributive laws, as well as the identities and complement laws. These rules govern how logical operations are performed on boolean variables.

4. How do you prove that a statement is always true using boolean algebra?

To prove that a statement is always true using boolean algebra, you can use logical equivalences and the basic rules of boolean algebra to simplify the statement and show that it is logically equivalent to the tautology (always true) statement, "true = true".

5. What are some examples of using boolean algebra to prove statements?

Some examples of using boolean algebra to prove statements include proving De Morgan's laws, showing that a logical statement is a tautology, and simplifying complex logical expressions to their simplest form.

Similar threads

Replies
11
Views
1K
Replies
1
Views
2K
Replies
16
Views
1K
Replies
6
Views
3K
Replies
6
Views
1K
Replies
4
Views
1K
Replies
1
Views
3K
Replies
20
Views
4K
Replies
6
Views
965
Back
Top