# Transformation rules in Boolean algebra

1. Mar 31, 2015

### 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) ?

2. Mar 31, 2015

### WWGD

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.

Last edited: Mar 31, 2015
3. Mar 31, 2015

### Raghav Gupta

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

4. Mar 31, 2015

### 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.

Last edited: Mar 31, 2015
5. Mar 31, 2015

### 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?

6. Mar 31, 2015

### 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].

Last edited: Mar 31, 2015
7. Mar 31, 2015

### 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.

8. Mar 31, 2015

### 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?
I am not understanding the first point that how we are concluding [PΛ-Q]== P ?

9. Apr 2, 2015

### WWGD

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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook