Transformation rules in Boolean algebra

[Raghav Gupta]

I know De-Morgan's law that $$ -(p∧q) = -p∨-q $$
Also $$ -(p∨q) = -p∧-q $$
But for material implication and bi conditional operations there are also some transformation.
What is the law or proof for it? Like
$$ p⇒q = -p∨q $$
$$ p ↔q = (p∧q) ∨ (-p∧-q) $$
There may be other properties also that I don't know.
How one can derive or say that?

SideNote: Why PF don't have a negation ( tilda symbol) ?

 

[WWGD]

I know De-Morgan's law that $$ -(p∧q) = -p∨-q $$
Also $$ -(p∨q) = -p∧-q $$
But for material implication and bi conditional operations there are also some transformation.
What is the law or proof for it? Like
$$ p⇒q = -p∨q $$
$$ p ↔q = (p∧q) ∨ (-p∧-q) $$
There may be other properties also that I don't know.
How one can derive or say that?

SideNote: Why PF don't have a negation ( tilda symbol) ?

This should strictly be logical equivalence and not equality.
You can show $$ p⇒q = -p∨q $$ , e.g., with truth tables, showing that the two associated tables are identical, or by using a derivation, assuming $$ p⇒q $$ and deriving $$-p∨q $$ from it. Example: rewrite$$ -p ∨ q = -(p ∧-q)$$ , and assume p , then assume $$ (p ∧-q)$$, and arrive at a contradiction . From previous, p follows, then q follows and then you conclude$$ q ∧-q $$ , a contradiction, from which $$ -(p ∧-q) $$ follows.

 

[Raghav Gupta]

assuming $$ p⇒q $$ and deriving $$-p∨q $$ from it. Example: rewrite$$ -p ∨ q = -(p ∧-q)$$ , and assume p , then assume (within the assumption of p)$$ (p ∧-q)$$ . From p, q follows and then you conclude$$ q ∧-q $$ , a contradiction, from which $$ -(p ∧-q) $$ follows.

rewrite$$ -p ∨ q = -(p ∧-q)$$
That you have written by De-Morgan's Law. Then I am not able to understand afterwards.

 

[WWGD]

I just rewrote. Please point out the steps you don't understand. I want to show A->B, and I do that by trying to show A-> -B, i.e., I assume A, and I assume it implies -B, and arriving at a contradiction from this last. Here B is (p∧-q) and A is $$ p⇒q $$ . It is a proof by contradiction.

 

[Raghav Gupta]

I am not understanding that,
If A is $$ p ⇒q $$ and B is $$ p ∧-q $$ then how A implying -B is a contradiction?

 

[WWGD]

If you assume A ->B and you arrive at a contradiction, then you can conclude A--> -B. In our case, if you assume (P-->Q)-> -[ P/\-Q] and you derive a contradiction from that, then, by contradiction, you conclude (P-->Q)->[P/\-Q].

So what we do is: we assume that (P-->Q) implies the negation of what we want to prove, i.e., we assume that (P-->Q) -->-[P/\-Q] and from this we arrive at a contradiction, then we conclude (P-->Q)-->-(-[P/\-Q])==[P/\-Q].

 

[WWGD]

More Formally/ in more detail:

We assume P-->Q and we assume -[-P \/ Q]=[P/\-Q] , i.e., we assume (P-->Q)-->[P/\-Q] , and from this we arrive at a contradiction, from which we conclude

(P-->Q)-->[P/\-Q] ==[-P\/Q]:

Assume
(P-->Q)--> [P/\-Q] , and assume (P-->Q)
i) Then we conclude [P/\-Q] == P
ii) From [P/\-Q] ,we conclude P
iii) From [P/\-Q] , we conclude- Q
iv) From ii and the premise, we conclude Q
v)From iv) and iii) , we conclude Q/\-Q , a contradiction
vi)By contradiction, we conclude -[P/\-Q]
___________________________________ We discharge our assumption, to get:

(P-->Q) --> -[[P/\-Q]]==-P \/ Q

Which is what we wanted to show.

 

[Raghav Gupta]

I think it is better to go by truth table.
I am able to show they are both equivalent by truth table. I am not able to understand these statements much.
Why we are in the first place going for a proof by contradiction?

Assume
(P-->Q)--> [P/\-Q] , and assume (P-->Q)
i) Then we conclude [P/\-Q] == P
ii) From [P/\-Q] ,we conclude P
iii) From [P/\-Q] , we conclude- Q
iv) From ii and the premise, we conclude Q
v)From iv) and iii) , we conclude Q/\-Q , a contradiction
vi)By contradiction, we conclude -[P/\-Q]
___________________________________ We discharge our assumption, to get:

(P-->Q) --> -[[P/\-Q]]==-P \/ Q

Which is what we wanted to show.

I am not understanding the first point that how we are concluding [PΛ-Q]== P ?

 

[WWGD]

My mistake, should be just [P/\-Q]