Question

Verify that the following are tautologies by citing the appropriate previous result. Do not make truth tables.

Answer 1

Target: P -> Q <=> (~Q -> ~P)

Answer 2

For convenience, can we use small letters here?

Answer 3

this is the previous page

Answer 4

I guess so but I'll have a hard time seeing them

Answer 5

Ok, capital letter then. We need not use the previous page.

Answer 6

ok...so we use demorgan's law on really everything in the exercise right?

Answer 7

Not really.. You'll see.
We'll work from the left.
P -> Q
<=> ~ (~ P -> Q) (from a)

Do you agree with this step?

Answer 8

double negation...

Answer 9

but ok a is ~(~P) <-> P

Answer 10

so it appears that I am applying A to whatever problem we are working on ?

Answer 11

Hmm, at least to this problem. I think it is one of the fundamental rules, if I remember correctly.

Answer 12

what letter are we doing? G?

Answer 13

G.

Answer 14

hmmm... so ~(~P) <-> P from A
(P ->Q)<->(~Q -> ~P) is G

Answer 15

We are going to show this (P ->Q)<->(~Q -> ~P), which is your part (g). The first step we do is to use the result from a. Is that clear?

Answer 16

yes
so...
~(~P->Q) <-> (~Q->~P)

Answer 17

oh just the left side...
~(~P->Q) <->

Answer 18

No... We take (P -> Q) in (g) as P in (a)

Answer 19

It should be ~ ( ~ (P -> Q) )

Answer 20

(~(~(P->Q) )

Answer 21

(~(~(P->Q) ) )

Answer 22

ok

Answer 23

So far, we get
P -> Q
<=> ~ ( ~ (P-> Q) )
Agree?

Answer 24

yes :)

Answer 25

Now, we apply the result from (f) in ~ (P -> Q) part.

Answer 26

so we're getting the info from f and putting it into the ~(P->Q)?

Answer 27

Yes. What do you get?

Answer 28

ok so f is ~(P->Q) <-> P^ ~Q

ummm
~(~(~P->Q)) ?

Answer 29

Nooooooo
Just replace "~ (P-> Q) " by "P ∧ (~Q)" in the first bracket.

We'll get
P -> Q
<=> ~ ( ~ (P-> Q) ) from (a)
<=> ~ ( P ∧ (~Q) ) from (f)

So far so good?

Answer 30

OH! so after we have ~(~(P->Q) from a we use the result from f and plug it in there.
Since f is ~(P->Q) <-> P^ ~Q
we plug in P^~Q in the ~(P->Q)) part which results in
~(P ^(~Q))

Answer 31

was the ~ from ~ ( ~ (P-> Q) ) distributed or we just plug in the result from F in its entirety

Answer 32

oh no it was just replaced.

Answer 33

I CAN'T VIEW DRAWINGS D:

Answer 34

What about LaTeX?

Answer 35

can't view it on os.

Answer 36

equation and draw don't work

Answer 37

P -> Q
<=> ~ ( ~ (P-> Q) ) from (a)
|_________|
l
V
|-------|
<=> ~ ( P ∧ (~Q) ) from (f)

Get it?

Answer 38

yeah......

Answer 39

Good.
Next, from c, we can replace " P ∧ (~Q) " by " ~ P V ~(~Q) "
So, we get
P -> Q
<=> ~ ( ~ (P-> Q) ) from (a)
<=> ~ ( P ∧ (~Q) ) from (f)
<=> ~ ( ~ P V ~ (~ Q) ) from (c)

So far so good?

Answer 40

well c is ~(P^Q) <-> ~P V ~Q

Answer 41

Yes. But now, you have ~Q on the left instead of Q, So...

Answer 42

this is where I am starting to feel lost here.

Answer 43

from what I'm reading....
<=> ~ ( P ∧ (~Q) ) from (f)
and then since C is ~(P^Q) <-> ~P V ~Q
one of them is going to be replaced

Answer 44

~( P ∧ Q ) <=> ~ P V ~ (Q) from (c)

Substitute Q by ~Q, we get
So, we get
~ ( P ∧ (~Q) ) ( ~ P V ~ (~ Q) )

Does that look good?

Answer 45

The fourth line should be
~ ( P ∧ (~Q) ) <=> ( ~ P V ~ (~ Q) )

Answer 46

so P ∧ (~Q) is being replaced by ~P V ~Q... however it needs to be placed properly... like
(~P V~(~Q))

Answer 47

Not really.
From (c), we have
~( P ∧ Q ) <=> ~ P V ~ (Q)
Now, replace Q from the above tautology by ~Q, we get
~ ( P ∧ (~Q) ) <=> ( ~ P V ~ (~ Q) )

Answer 48

o-0

Answer 49

replace the Q from ~ P V ~ (Q) ?

Answer 50

From both left and right side of the tautology you get in (c)

Answer 51

and then the tautology appears or?

Answer 52

And then you will get "~ ( P ∧ (~Q) ) <=> ( ~ P V ~ (~ Q) )"

The left side is exactly the things in the first bracket in the last line of what we just got:
P -> Q
<=> ~ ( ~ (P-> Q) ) from (a)
<=> ~ ( P ∧ (~Q) ) from (f)

Answer 53

and then there's more stuff I think...

Answer 54

We replace "~ ( P ∧ (~Q) )" by " ( ~ P V ~ (~ Q) )"
in the line "<=> ~ ( P ∧ (~Q) ) from (f) ". Then, we'll get
P -> Q
<=> ~ ( ~ (P-> Q) ) from (a)
<=> ~ ( P ∧ (~Q) ) from (f)
<=> ~ ( ~ P V ~ (~Q) ) from (c)

Answer 55

and then test for tautology... see if it produces an all T column

Answer 56

and if not go further?

Answer 57

I don't think you can use truth table?!

Answer 58

then how would we know when we reach tautology

Answer 59

If you can get the right side from the left side

Answer 60

With correct steps.

Answer 61

is the result the same or?

Answer 62

like the left side = right side?

Answer 63

Yes.

Answer 64

hmmm...I think that a through e are one liners since they represent either one part of the law or the law as a whole. like for a . ~(~P) <-> P is the double negation. so if I replace ~(~P) with P I have P<->P. I have done the truth table even though I'm not allowed to and I do see a T column

Answer 65

maybe that's how to approach a...which is the first one.

Answer 66

?

Answer 67

this is what I wrote for b earlier
~( P V Q) <-> ~P ^ ~Q
maybe it's equilvalent to

~P ^ ~Q <-> ~P ^ ~Q
and ~( P V Q) <-> ~( P V Q)

Answer 68

c is ~(P ^ Q) <-> ~P V ~Q which is the other demorgan...

Answer 69

won't I get a tautology if I apply b to c and c to b?

Answer 70

http://assets.openstudy.com/updates/attachments/52db5f51e4b05a53debcfc5a-usukidoll-1390108788693-tautologyverification.png

Answer 71

Is what this link shows a part of your book?

Answer 72

no it's from another book

Answer 73

I need to see what have been mentioned in your textbook. :(

Answer 74

I think a-e are one liners for this
http://assets.openstudy.com/updates/attachments/52db9a37e4b05a53debd0b77-usukidoll-1390123624453-scan1401170001.jpg

Answer 75

because b and c are demorgans already
d and e are distributive
a is double negation.
won't proving those 5 be easier than the last two?

Answer 76

If your book has mentioned De Morgan's law, double negation, and distributive laws, then yes - you can simply say they are tautology since it has been mentioned in your book.

Answer 77

so they are indeed one liners...
so for a ~(~P) <-> P
if I replace ~(~P) with P
I get P<-> P and that does produce a tautology

Answer 78

~(~P) <=> P LOL

Answer 79

eh?

Answer 80

hmmm... ~(~P) <=> ~(~P)

Answer 81

P <=> P or ~(~P) <=> ~(~P) is silly though :\

Answer 82

why is it silly?

Answer 83

Because obviously, P is same as P, and ~(~P) is the same as ~(~P). It's like we won't say 1=1 :|

Answer 84

*Not necessary to say 1=1

Answer 85

that's like the first problem of 1.4.15 XD

Answer 86

super short...so maybe that's it?

Answer 87

That is it.

Answer 88

woo .... so b and c which are both demorgans would also be short too right? because they seem to be related.

Answer 89

How are you going to verify (b)?

Answer 90

hmmm b is a demorgan in a nutshell same as c

Answer 91

Ok, then just name the rule, both as "De Morgan's rule".

Answer 92

wow typical troll ^

Answer 93

no. get out of my thread. You do realize that there's a mod on my thread helping me figure this out right? I can just print screen this, submit it to a mod, and you're out for thread crashing.

Answer 94

i have no idea what you just said

Answer 95

anyway moving that aside... d and e are distributive laws so do I just state the laws for d and e?

Answer 96

and then F was done earlier, so all there is ... is the rest of G in this?!