Tautologies

envy1987 · 2014-10-24 02:46:34

I do facing a problem when I solving one of my homework.

The question as below.

Q: If the statement is a tautology, give a proof using the appropriate rules of logic and avoid using truth tables if possible.If it is not a tautology, then justify your answer by giving an appropriate example.

( A→(B→C)) ≡ ((A→B)→C)

Below is my answer

¬A∨(B→C) ≡ ((¬A∨B)→C)
¬A∨(¬B∨C) ≡ ¬(¬A∨B)∨C
(¬A∨¬B)∨C ≡ ¬(¬A∨B)∨C

Then I stuck at here.....please give me some advice pls...

Bob · 2014-10-24 03:48:19

hi envy1987

Although they want you to avoid the truth table, I see no harm in separately trying it, just to see if it is a tautology. (You don't have to submit that as part of your answer.) It looks to me like it isn't, so you need to find an example. Have you been given any examples for other non tautologies so I can get an idea what is expected here?

Bob

Agnishom · 2014-10-24 04:42:48

What does the equivalent symbol mean?

envy1987 · 2014-10-24 15:38:23

bob bundy wrote:

hi envy1987
Although they want you to avoid the truth table, I see no harm in separately trying it, just to see if it is a tautology. (You don't have to submit that as part of your answer.) It looks to me like it isn't, so you need to find an example. Have you been given any examples for other non tautologies so I can get an idea what is expected here?
Bob

Nope....what I post here is the overall of the question.....

Well....according to my lecture....it's not a tautology...

envy1987 · 2014-10-24 15:40:54

Agnishom wrote:

What does the equivalent symbol mean?

you mean this "≡" ?

In my book it's called "Boiconditional Proposition" or " A if and only if B"...

Agnishom · 2014-10-24 17:25:13

That is usually represented by <=>

Bob · 2014-10-24 20:20:20

I have seen both of these symbols used for equivalence.

You wrote:

Well....according to my lecture....it's not a tautology...

I wrote:

It looks to me like it isn't, so you need to find an example.

Ok. So we agree. My problem is, I'm not sure what sort of example is required. Here's a possibility:

A ={he plays football} B = {he plays hockey} C = {he plays tennis}

Now consider the case where he does not play football, does play hockey and does not play tennis.

B => C is False but A => (B => C) is True. (True => False) is False but (False => False) is True.

A => B is True and (A => B) => C is False. (False => True) is True but (True => False) is False.

Thus the two statements give different results in this case.

[note: I identified this case by looking at my truth table. I do not know how I can 'prove' my argument without using the words true and false.]

Bob

anonimnystefy · 2014-10-25 03:20:23

I think want to avoid using a table for proving it's a tautology.

Bob · 2014-10-25 04:28:47

hi Stefy,

If the statement is a tautology, give a proof using the appropriate rules of logic and avoid using truth tables if possible. If it is not a tautology, then justify your answer by giving an appropriate example.

This is from a course on logic so we are entitled to apply that exactly as stated. If a tautology don't use a table. But it isn't. So we must justify by example.

Certainly you wouldn't want me to prove anything that is false. A single counter-example is sufficient. I can get it by any method I like.

Bob

anonimnystefy · 2014-10-25 10:48:12

What I meant is exactly that. They just wanted to say, "if you are proving this to be a tautology, we discourage you from using tables to do so."

envy1987 · 2014-10-25 17:24:01

bob bundy wrote:

I have seen both of these symbols used for equivalence.
You wrote:
Well....according to my lecture....it's not a tautology...
I wrote:
It looks to me like it isn't, so you need to find an example.
Ok. So we agree. My problem is, I'm not sure what sort of example is required. Here's a possibility:
A ={he plays football} B = {he plays hockey} C = {he plays tennis}
Now consider the case where he does not play football, does play hockey and does not play tennis.
B => C is False but A => (B => C) is True. (True => False) is False but (False => False) is True.
A => B is True and (A => B) => C is False. (False => True) is True but (True => False) is False.
Thus the two statements give different results in this case.
[note: I identified this case by looking at my truth table. I do not know how I can 'prove' my argument without using the words true and false.]
Bob

Well.....I try this before....my lecture say I should used formula(logical algebra) to prove it but not example of TRUE or false value..

Now trying to get some tips and example from him....hope they can provide me..

Bob · 2014-10-25 20:21:31

hi envy1987

If that's what your lecturer wants then he should have said so in the question. So what is considered as a proof that something is false?

Would it be acceptable to reduce both the left hand side and the right hand side to expressions of the form

(P ^ q ^ r) V (s ^ t ^ u) V .........

and then observe that these expressions are different?

Bob

anonimnystefy · 2014-10-25 20:45:24

Reducing to DNF would be a sufficient proof, but it's weird because the question clearly asks for an example of when it is false.

Bob · 2014-10-25 21:56:00

hi Stefy,

I thought there were some words for it (disjunctive normal form*) so thanks for that.

I think the lecturer wants the students to practise manipulation using the algebra of logic. So why didn't he say:

"Use the algebra of logic to prove or disprove these possible tautologies."

Anyway, I'll do it but I don't want to play this game:

Label. Me: Here's my answer.
Lecturer: Don't do it like that.
Goto Label

So I await the OP's answer.

Bob

* I remember concepts, not fancy language, so I tried looking it up and couldn't track it down.

btw. b-a

anonimnystefy · 2014-10-25 22:16:00

You're welcome.

You should not use goto. A while loop should suffice.

And, yes, b-a is correct.

Bob · 2014-10-25 22:47:28

Corrections:

WHILE 1 = 0
Me: Here's my answer.
Lecturer: Don't do it like that.
ENDWHILE

Bob

anonimnystefy · 2014-10-25 22:51:25

Hate to say it, but that algorithm can run only a finite number of times.

Bob · 2014-10-25 22:54:03

Why is that? Does your computer get bored after a bit? How about this:

REPEAT
Me: Here's my answer.
Lecturer: Don't do it like that.

UNTIL Hell freezes over

Bob

anonimnystefy · 2014-10-26 07:18:02

It will repeat only as long as both of you are actually able to say that.

Bob · 2014-10-26 20:38:57

Don't want to get into a deep religious discussion on this, but, strictly, it will repeat until the event occurs, irrespective of what either of us says.

Bob

anonimnystefy · 2014-10-27 03:00:22

Well, if either of you are not able to say that, there will be some sort of error when trying to run that loop another time.

Also, I admire your ability to gather new solutions by the millisecond.

SolarDevil · 2014-10-27 10:53:20

Haha... I understand what truth tables are but I don't get what symbols he is using to try to explain a tautology.
¬A∨(B→C) ≡ ((¬A∨B)→C)
¬A∨(¬B∨C) ≡ ¬(¬A∨B)∨C
(¬A∨¬B)∨C ≡ ¬(¬A∨B)∨C

I could write it out by hand but that would v represent?

Bob · 2014-10-27 20:36:15

hi SolarDevil,

Do you want me to reduce both expressions to disjunctive normal form?

Bob

SolarDevil · 2014-10-28 11:41:50

That would be very helpful!

Bob · 2014-10-28 23:14:12

Reduction to DNF. In this case I am trying to put all terms in the form (A^B^C) V etc

Left hand side :

≡ ( A→(B→C)) ≡ ¬A V (B→C) ≡ ¬A V (¬BVC) ≡ (¬A^TRUE) V (A^(¬BVC))

≡ ¬A^[(B^C) V (B^¬C) V (¬B^C) V (¬B^¬C)] V (A ^ [(¬ B^C) V (¬ B^¬ C) V (B ^ C) ]

≡ (¬A^B^C) V (¬A^B^¬C) V (¬A^¬B^C) V (¬A^¬B^¬C) V (A^¬ B^C) V (A^¬ B^¬ C) V (A^B ^ C)

Right hand side :

≡ ((A→B)→C) ≡ ¬(A→B) V C ≡ ¬(¬AVB) V C ≡ (A^¬B) V C

≡ (A^¬ B^C) V (A^¬ B^¬C) V (A^B V C) V (¬A^B ^ C) V (A^¬B ^ C) V (¬A^¬B ^ C)

Remove duplicate and re-order

≡) (¬A^B ^ C) V (¬A^¬B ^ C) V (A^¬B ^ C) V (A^¬ B^¬C) V (A^B V C)

Compare with LHS
≡ (¬A^B^C) V (¬A^B^¬C) V (¬A^¬B^C) V (¬A^¬B^¬C) V (A^¬ B^C) V (A^¬ B^¬ C) V (A^B ^ C)

Clearly, these are not the same.

Here are the truth tables for the same. (It took me a fraction of the time to do it this way. )

Bob

Math Is Fun Forum

#1 2014-10-24 02:46:34

Tautologies

#2 2014-10-24 03:48:19

Re: Tautologies

#3 2014-10-24 04:42:48

Re: Tautologies

#4 2014-10-24 15:38:23

Re: Tautologies

#5 2014-10-24 15:40:54

Re: Tautologies

#6 2014-10-24 17:25:13

Re: Tautologies

#7 2014-10-24 20:20:20

Re: Tautologies

#8 2014-10-25 03:20:23

Re: Tautologies

#9 2014-10-25 04:28:47

Re: Tautologies

#10 2014-10-25 10:48:12

Re: Tautologies

#11 2014-10-25 17:24:01

Re: Tautologies

#12 2014-10-25 20:21:31

Re: Tautologies

#13 2014-10-25 20:45:24

Re: Tautologies

#14 2014-10-25 21:56:00

Re: Tautologies

#15 2014-10-25 22:16:00

Re: Tautologies

#16 2014-10-25 22:47:28

Re: Tautologies

#17 2014-10-25 22:51:25

Re: Tautologies

#18 2014-10-25 22:54:03

Re: Tautologies

#19 2014-10-26 07:18:02

Re: Tautologies

#20 2014-10-26 20:38:57

Re: Tautologies

#21 2014-10-27 03:00:22

Re: Tautologies

#22 2014-10-27 10:53:20

Re: Tautologies

#23 2014-10-27 20:36:15

Re: Tautologies

#24 2014-10-28 11:41:50

Re: Tautologies

#25 2014-10-28 23:14:12

Re: Tautologies

Board footer