## Tautology question

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.
tonyc1970
Posts: 13
Joined: Fri Aug 02, 2013 4:58 pm
Contact:

### Tautology question

Hi,

I am working on a tautology question and understand most of the answer except for one part. I need to show that the following is a tautology:

<=> means equivalent

Code: Select all

p -> [(~p) -> q)] <=> ~p v [~(~p v q)] <- this line - why the first ~? How do I get it? Is it because of the already existing ~p? <=> ~p v [ p v q] <=> (~p v p) v q <=> T v q <=> t
I don't understand the reason for the first ~, the one in in this line "<=> ~p v [~(~p v q)]". I realize I need it to complete the exercise but I don't understand how I get it. Can someone please help me to understand this?

Thanks for any help,

Tony

maggiemagnet
Posts: 358
Joined: Mon Dec 08, 2008 12:32 am
Contact:

### Re: Tautology question

I need to show that the following is a tautology:
<=> means equivalent

Code: Select all

p -> [(~p) -> q)] <=> ~p v [~(~p v q)] <- this line - why the first ~? How do I get it? Is it because of the already existing ~p?
I think they skipped a few steps, plus they made a typo. The logical equivalent of "if p, then q" is "not-p or q". So the equivalent of "if p, then [stuff in brackets]" is "not-p or [stuff in brackets]". But the [stuff in brackets] is an if-then, too. The equivalent of "if not-p, then q" is "not(not-p) or q". But they wrote it as "not(not-p or q)". They put the end-parentheses in the wrong spot. You can see this in the next line, where they go from "not(not-p or q)" to "p or q". The right way was "not(not-p) or q", and "not(not-p)" does go to "p".

tonyc1970
Posts: 13
Joined: Fri Aug 02, 2013 4:58 pm
Contact:

### Re: Tautology question

Thanks for the reply, maggiemagnet. I believe I understand it now. I appreciate the help.