# Math Help - Proving logic propositions

1. ## Proving logic propositions

I'm a little lost with this, can you guys provide full solutions?

The following propositions are tautologies, prove each one of them without truth table.

1) $p \Rightarrow (p \vee q).$

This is $\sim p \vee (p \vee q) \equiv ( \sim p \vee p) \vee q \equiv T \vee q \equiv T.$ (Where $T$ is a tautology.) Is this right? When can I apply $\sim p \vee (p \vee q) \equiv ( \sim p \vee p) \vee q$? Only when having all $\vee$ or $\wedge$?

2) $(p \Leftrightarrow q) \Leftrightarrow (p \wedge q) \vee ( \sim p \,\wedge \sim q).$ I dunno how to solve this one.

3) $\left[ {(p \Leftrightarrow q) \wedge (q \Leftrightarrow r)} \right] \Rightarrow (p \iff q).$ I dunno how to solve this one either.

4) $\left[ {(p \wedge \sim q) \Rightarrow \sim p} \right] \Rightarrow (p \Rightarrow q).$

This would be $\left[ { \sim (p \wedge \sim q) \vee \sim p} \right] \Rightarrow (p \Rightarrow q) \equiv ( \sim p \vee q \vee \sim p) \Rightarrow (p \Rightarrow q).$ How do I proceed there?

5) $\sim (p \Leftrightarrow q) \Leftrightarrow ( \sim p \Leftrightarrow q).$ Help here too.

6) $\left[ {(p \Rightarrow \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow \sim p.$ Another help here.

7) $\left[ {p \wedge (p \Rightarrow q)} \right] \Rightarrow q.$

We have $\left[ {p \wedge ( \sim p \vee q)} \right] \Rightarrow q \equiv (p \wedge \sim p) \vee (p \wedge q) \Rightarrow q.$ What's next?

8) $(p \wedge q) \Leftrightarrow \left[ {(p \vee q) \wedge (p \Leftrightarrow q)} \right].$ Help here again

9) $(p \wedge q \Rightarrow r) \Leftrightarrow (p \wedge \sim r \Rightarrow \sim q).$ Need help here too.

That's it, I'm lost with this, I hope you can help me.

2. By in large, this list of equivalences is asking you to reinvent the wheel.
It is my impression that you have access to a reasonable Library.
You need to get yourself a good basic symbolic logic textbook.
I like the books by I.M.Copi. There are others: look for Michael Resnik or Benson Mates.

Your problem #1 is simply known as Addition in the rules of inference.

3. What is the Biconditional equivalence that they have allowed you to use? For example, my book has a list of 4:

$p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$ This is #3

$p \leftrightarrow q \equiv \sim p \leftrightarrow \sim q$

$p \leftrightarrow q \equiv (p \wedge q) \vee (\sim p \wedge \sim q)$ This is #2

$\sim (p \leftrightarrow q) \equiv p \leftrightarrow \sim q$

I doubt they want you to just say that they are equal. So they must have one of these in particular that they want you to use when doing proofs. (sort of like how if you need to find a the derivative of x^2 with limits, you would need lim_(h -> 0) [f(x+h) -f(x)]/h. And you would get into trouble if you used the power rule to just say 2x. I get the feeling that using these methods is like the power rule, but we are supposed to use the limit definition, but unfortunately I'm not sure how it is defined for you, so if you can tell me how you were told to convert biconditional statements, I'll take another look)
Originally Posted by Krizalid
1) $p \Rightarrow (p \vee q).$
~p V (p V q) ...By Implication

= (~p V p) V q ...By Associative laws

= T V q ...By Negation laws

= T ...By Domination laws

Originally Posted by Krizalid
When can I apply $\sim p \vee (p \vee q) \equiv ( \sim p \vee p) \vee q$? Only when having all $\vee$ or $\wedge$?
My Discrete Mathematics book has two examples for Associative laws:
(p V q) V r = p V (q V r)
(p ^ q) ^ r = p ^ (q ^ r)

You could probably think of them as addition and multiplication:
(a*b)*c = a*(b*c)
(a+b)+c = a+(b+c)
But you cannot mix them together.

Originally Posted by Krizalid
4) $\left[ {(p \wedge \sim q) \Rightarrow \sim p} \right] \Rightarrow (p \Rightarrow q).$

This would be $\left[ { \sim (p \wedge \sim q) \vee \sim p} \right] \Rightarrow (p \Rightarrow q) \equiv ( \sim p \vee q \vee \sim p) \Rightarrow (p \Rightarrow q).$ How do I proceed there?
from
$\equiv ( (\sim p \vee q) \vee \sim p) \Rightarrow (p \Rightarrow q)$

$\equiv ( (\sim p \vee \sim p)\vee q) \Rightarrow (p \Rightarrow q)$ ...By associative laws

$\equiv ( \sim p \vee q) \Rightarrow (p \Rightarrow q)$ ...By Idempotent laws

$\equiv (p \Rightarrow q) \Rightarrow (p \Rightarrow q)$ ...By Implication

$\equiv \sim (p \Rightarrow q) \vee (p \Rightarrow q)$ ...By Implication Edit: I accidentally typed a tilde instead of \sim on this, this step should be ~(p->q) V (p->q)

$\equiv$ T ...By Negation laws

Originally Posted by Krizalid
6) $\left[ {(p \Rightarrow \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow \sim p.$ Another help here.
$\left[ {(p \Rightarrow \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow \sim p.$ ...premise

$\equiv \left[ {(q \Rightarrow \sim p) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow \sim p.$ ...By contraposition

$\equiv \left[ {(q \Rightarrow \sim p) \wedge ( r \Rightarrow q) \wedge r} \right] \Rightarrow \sim p.$ ...By implication

$\equiv \left[ {(q \Rightarrow \sim p) \wedge q} \right] \Rightarrow \sim p.$ ...By Modus Ponens of "r" and "r->q"

$\equiv \sim p \Rightarrow \sim p.$ ...By Modus Ponens of "q" and "q->~p"

$\equiv p \vee \sim p.$ ...By implication

=T ...By Negation laws

Edit theres actually an easier way for this one:
$\left[ {(p \Rightarrow \sim q) \wedge ( \sim r \vee q) \wedge r} \right] \Rightarrow \sim p.$ ...premise

$\left[ {(p \Rightarrow \sim q) \wedge q} \right] \Rightarrow \sim p.$ ...disjunctive syllogism of "r" and "~r V q"

$\sim p \Rightarrow \sim p.$ ...modus tollens of "p->q" and "~q"

and now we're on the second to last step of the above proof

One thing about these, is we didn't do them in this format, we would be given several premises and have to take them to a conclusion. So the steps were not sequential like this, I guess I'm improvising a bit. For example, in this last proof as I didn't need steps any more I took them out (ie making "(p->q)^~q" into "~p") But really, taking them out should have been it's own step called "simplification" But I just wasn't sure how to do that in the format that I was working with, so I kind of improvised. I'm not sure if that will be acceptable for your instructor.