# Logical identities problem

Printable View

• Oct 12th 2010, 04:05 PM
Laban
Logical identities problem
I've just started a course in logics and set theory with no background whatsoever in this field, and for some reason I'm having problems with proving stuff with identities.

I'll try and give the first problem I'm stuck in, which is one of the easier ones I got for homework - hoping that I might get the idea and be able to continue on my own.

here it is then :

(pΛ~q)→~(pVr) ≡ p→q
so I did :
~(pΛ~q) V ~(pVr) ≡ p→q
and...I'm stuck :) I tried several other formulas and got nowhere.
I think that one of my biggest problems is that I'm not completely sure how to treat the variables and think of it as an equation instead of whatever it is :D.

If anybody could show me the way to prove it, maybe with a some commentary as well - I would highly appreciate it, cause I'm pretty lost.

Thanks
• Oct 12th 2010, 07:23 PM
tonio
Quote:

Originally Posted by Laban
I've just started a course in logics and set theory with no background whatsoever in this field, and for some reason I'm having problems with proving stuff with identities.

I'll try and give the first problem I'm stuck in, which is one of the easier ones I got for homework - hoping that I might get the idea and be able to continue on my own.

here it is then :

(pΛ~q)→~(pVr) ≡ p→q
so I did :
~(pΛ~q) V ~(pVr) ≡ p→q
and...I'm stuck :) I tried several other formulas and got nowhere.
I think that one of my biggest problems is that I'm not completely sure how to treat the variables and think of it as an equation instead of whatever it is :D.

If anybody could show me the way to prove it, maybe with a some commentary as well - I would highly appreciate it, cause I'm pretty lost.

Thanks

I don't understand how come you changed the --> in the original formula with V in the second....why?!

Anyway, to show logical equivalence you've to build truth tables for both sides and prove that for ANY

given values for p,q you get the same truth value in both tables.

Tonio
• Oct 12th 2010, 11:01 PM
Traveller
Quote:

Originally Posted by Laban
I've just started a course in logics and set theory with no background whatsoever in this field, and for some reason I'm having problems with proving stuff with identities.

I'll try and give the first problem I'm stuck in, which is one of the easier ones I got for homework - hoping that I might get the idea and be able to continue on my own.

here it is then :

(pΛ~q)→~(pVr) ≡ p→q
so I did :
~(pΛ~q) V ~(pVr) ≡ p→q
and...I'm stuck :) I tried several other formulas and got nowhere.
I think that one of my biggest problems is that I'm not completely sure how to treat the variables and think of it as an equation instead of whatever it is :D.

If anybody could show me the way to prove it, maybe with a some commentary as well - I would highly appreciate it, cause I'm pretty lost.

Thanks

Your first step is correct. You have to proceed as follows :

≡ ~(pΛ~q) V ~(pVr)

≡ (~pVq)V(~pΛ~r)

≡ (~pV(~pΛ~r)) V(qV(~pΛ~r))

≡ ~pV((qV~p)Λ(qV~r))

≡ (~pVq)Λ(~pVqV~r)

≡ ~pVq

Some steps as well as the reasoning are not shown. Can you complete the details ?
• Oct 13th 2010, 02:58 PM
Laban
I think I got this part (~pV(~pΛ~r)) V(qV(~pΛ~r)) , though I still find it hard to match it with any of the basic formulas - which is quite important to me here, since obviously, I can't seem to think an inch beyond them - which is really bad.

The part after ~pV((qV~p)Λ(qV~r)) is completely beyond me - so I'd love some details.

Anywise, Thank you.
• Oct 13th 2010, 03:35 PM
Traveller
Quote:

Originally Posted by Laban
I think I got this part (~pV(~pΛ~r)) V(qV(~pΛ~r)) , though I still find it hard to match it with any of the basic formulas - which is quite important to me here, since obviously, I can't seem to think an inch beyond them - which is really bad.

The part after ~pV((qV~p)Λ(qV~r)) is completely beyond me - so I'd love some details.

Anywise, Thank you.

(~pV(~pΛ~r)) V(qV(~pΛ~r)) ≡ ~pV((qV~p)Λ(qV~r)) :

(~pV(~pΛ~r)) ≡ ~p because AV(AΛB) = A, since (AΛB) is a subset of A.

(qV(~pΛ~r)) ≡ (qV~p)Λ(qV~r)) by the distributive laws.

~pV((qV~p)Λ(qV~r)) ≡ (~pVq)Λ(~pVqV~r) :

~pV((qV~p)Λ(qV~r))≡(~pVqV~p) Λ(~pVqV~r)) again, by the distributive laws.

Notice that the first clause becomes (~pVq). Now consider (~pVq) as A and ~r to be B. the expression becomes AΛ(AVB). What does this work out to be ?

Also, I leave it to you to write down the whole thing more formally.
• Oct 15th 2010, 07:55 AM
Laban
Ok thanks, finally got it :D

but while working on it alone (meaning with friends xD) I got this - I'd like it if you could check to see if it makes sense :
starting here :

≡ (~pVq) V (~pΛ~r) ≡ (now I just change the appearance a bit, adding brackets to make it look more organized)

≡ q V [~p V (~pΛr)] ≡ (now using this formula p V (pΛq) ≡ p; just that the p is ~p in this case)

≡ q V ~p

is it good?
• Oct 15th 2010, 08:14 AM
Traveller
Excellent !

I prefer your solution to mine. :)
• Oct 15th 2010, 08:42 AM
Laban
I really can't take much credit for this since I didn't came up with it by myself but thank you.
It is really important for me at this stage to get the "playability" of the formulas and identities, which is still a bit awkward to me.

I'd like to ask another question, if you don't mind :

a,b and c are 3 different numbers.
arrange them by size if you know that :
if a is not the biggest then b is the biggest and if b is not the smallest then c is the biggest.

I don't even know where to start.

p.s - excuse my bad wording - it's freely translated
• Oct 15th 2010, 08:53 AM
Traveller
Quote:

Originally Posted by Laban

a,b and c are 3 different numbers.
arrange them by size if you know that :
if a is not the biggest then b is the biggest and if b is not the smallest then c is the biggest.

Case 1: a is not the biggest .

b is the biggest. So b is not the smallest. So c should be the biggest which is a contradiction.

Case 2: a is the biggest.

c is not the biggest. Therefore b is the smallest. So we have b<c<a.
• Oct 15th 2010, 08:58 AM
Laban
aww...you make it look super easy :D though I still don't quite get it :/

is it possible to display it in identities as well?

thanks a lot for your crazy fast replys as well bb
• Oct 15th 2010, 09:52 AM
MoeBlee
Quote:

Originally Posted by Laban
I still don't quite get it

There are two possible cases: One possible case is where A is not the biggest, and the other possible case is where A is the biggest.

So let's check what happens in either case:

If case one holds, then A is not the biggest, so B is the biggest, so B is not the smallest, so C is the biggest. But it can't be that both B and C are the biggest. So case one is not actually possible. So we can eliminate case one.

So case two holds, so A is the biggest, so C is not the biggest, so B is the smallest (by "modus tollens", since we were told that if B is NOT the smallest then C IS the biggest). So we have B is the smallest and A is the biggest, so C is in between, so we have B, C, A in order from smallest to biggest.

And that's the answer - B, C, A from smallest to biggest - since case one does not hold (it would be a contradiction if it did hold) so only case two can hold.
• Oct 15th 2010, 11:20 AM
Traveller
Quote:

Originally Posted by Laban
aww...you make it look super easy :D though I still don't quite get it :/

is it possible to display it in identities as well?

thanks a lot for your crazy fast replys as well bb

It can work like this:

a is the smallest = a1
a is in the middle = a2
a is the biggest = a3

b is the smallest = b1
b is in the middle = b2
b is the biggest = b3

c is the smallest = c1
c is in the middle = c2
c is the biggest = c3

Observe that a1→~a2Λ~a3Λ~b1Λ~c1. Similar conditions hold true for other variables.

Now the given conditions are :

~a3 → b3
~b1 → c3

Now, any variable is either true or false. So we will have the following cases :

1) ~a3

→ b3
→ ~b1
→ c3

But b3 → ~c3 which is a contradiction.

2) a3

→ ~c3
→ b1
• Oct 18th 2010, 07:13 AM
Laban
thanks all.

Traveller - thanks for putting out with me, I'll probably be back soon with some more problems. :)