# Thread: Having problem with these 2 Tautology? (This is due today at 9am)

1. ## Having problem with these 2 Tautology? (This is due today at 9am)

Q: Show that each condition statement is a tautology without using a truth table?
a.)

b.)

Heres the laws that I have to use:

http://www.plu.edu/~sklarjk/245s07/logequiv.pdf

2. Originally Posted by Grillakis
Q: Show that each condition statement is a tautology without using a truth table?
a.)

b.)

Heres the laws that I have to use:

http://www.plu.edu/~sklarjk/245s07/logequiv.pdf
a) By the Distributive Law (number 3 on the list):

$\neg p \wedge (p\wedge q)$

Becomes:

$(\neg p \wedge p)\vee(\neg p \wedge q)$

$(\neg p \wedge p)$ is always false! They can't both be true simultaneously. Hence for the entire statement to be true, the $(\neg p \wedge q)$ part must be true. If this is true, then it says that $\neg p$ is true, and so is $q$. Which certainly implies that $q$ is true.

3. Originally Posted by Mush
a) By the Distributive Law (number 3 on the list):

$\neg p \wedge (p\wedge q)$

Becomes:

$(\neg p \wedge p)\vee(\neg p \wedge q)$

$(\neg p \wedge p)$ is always false! They can't both be true simultaneously. Hence for the entire statement to be true, the $(\neg p \wedge q)$ part must be true. If this is true, then it says that $\neg p$ is true, and so is $q$. Which certainly implies that $q$ is true.
ok I see what you talking about for part a. But what about part b b/c you have implication (-->) in the equations?

4. Originally Posted by Grillakis
ok I see what you talking about for part a. But what about part b b/c you have implication (-->) in the equations?
$p \to q$ is the same as saying $\neg p \vee q$.

So you can write it as :

$(\neg p \vee q)\wedge(\neg q \vee r )$

5. Originally Posted by Mush
$p \to q$ is the same as saying $\neg p \vee q$.

So you can write it as :

$(\neg p \vee q)\wedge(\neg q \vee r )$
I see.....

I have one last question and was wondering if you can tell me if I used the right law for this.

Q: Show that ( p → q ) ^ ( p → r ) and p → ( q ^ r ) are logically equivalent?
A:
( p → q ) ^ ( p → r ) ≡ ( ¬p v q ) ^ ( ¬p v r ) Implication
≡ ¬p v ( q ^ r ) 1st Distributive Law
p → (q ^ r ) Double Negation

6. Originally Posted by Grillakis
I see.....

I have one last question and was wondering if you can tell me if I used the right law for this.

Q: Show that ( p → q ) ^ ( p → r ) and p → ( q ^ r ) are logically equivalent?
A:
( p → q ) ^ ( p → r ) ≡ ( ¬p v q ) ^ ( ¬p v r ) Implication
≡ ¬p v ( q ^ r ) 1st Distributive Law
p → (q ^ r ) Double Negation
Yes that's fine.

7. awesome....thank you Mush

8. Originally Posted by Grillakis
Q: Show that each condition statement is a tautology without using a truth table?
a.)

b.)

Heres the laws that I have to use:

http://www.plu.edu/~sklarjk/245s07/logequiv.pdf
Grillakis here is aproof based on the rules you where given ,apart the law material implication .

[~p^(pvq)] ------->q <=====>(is equivalent) ~[~p^(pvq)]vq, using material implication law.

~[~p^(pvq)]vq <=====> [pv~(pvq)]vq ,by using De Morgan

[pv~(pvq)]vq <======> qv[pv~(qvp)] ,by using commutativity twice

qv[pv~(qvp)] <======> (qvp)v~(qvp), by using associativity

(qvp)v~(qvp) <======> t , by using negation laws

I am sorry i have not figured out yet question (b)

9. Originally Posted by archidi
Grillakis here is aproof based on the rules you where given ,apart the law material implication .

[~p^(pvq)] ------->q <=====>(is equivalent) ~[~p^(pvq)]vq, using material implication law.

~[~p^(pvq)]vq <=====> [pv~(pvq)]vq ,by using De Morgan

[pv~(pvq)]vq <======> qv[pv~(qvp)] ,by using commutativity twice

qv[pv~(qvp)] <======> (qvp)v~(qvp), by using associativity

(qvp)v~(qvp) <======> t , by using negation laws

I am sorry i have not figured out yet question (b)
thats alright Archidi....thanks for your guys is help. I tried to figure this out and I handed in the paper.