Thread: 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 .

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

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 .

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

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 .

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 ?

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.

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.

Ok thanks, finally got it

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?

Excellent !

I prefer your solution to mine.

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

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.

aww...you make it look super easy 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

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.

Originally Posted by Laban

aww...you make it look super easy 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

thanks all.

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