Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

envy1987
Member
Registered: 2014-09-25
Posts: 6

Tautologies

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

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Tautologies

What does the equivalent symbol mean?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

envy1987
Member
Registered: 2014-09-25
Posts: 6

Re: Tautologies

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

Offline

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

envy1987
Member
Registered: 2014-09-25
Posts: 6

Re: Tautologies

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

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Tautologies

That is usually represented by <=>


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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.  smile  A single counter-example is sufficient.  I can get it by any method I like.  smile

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

envy1987
Member
Registered: 2014-09-25
Posts: 6

Re: Tautologies

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

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

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.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

You're welcome.

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

And, yes, b-a is correct. smile


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

Corrections:

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

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Tautologies

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

SolarDevil
Member
Registered: 2014-09-14
Posts: 37

Re: Tautologies

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?


Herro! Sycamore School will win National Science Bowl this year!!! big_smile

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

hi SolarDevil,

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

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

SolarDevil
Member
Registered: 2014-09-14
Posts: 37

Re: Tautologies

That would be very helpful!


Herro! Sycamore School will win National Science Bowl this year!!! big_smile

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,052

Re: Tautologies

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.  smile )

zPLAFVY.gif

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

Board footer

Powered by FluxBB