Proofs...

lost1 · #1 $Old$ November 7th, 2009, 10:28 PM

Hey I need help with some proving questions....

Q1) Prove the following statement, then write down its converse. Is the converse true or false? Prove
your answer.
“For all x 2 Z, if x ≡ −1 (mod 7) then x^3 ≡ −1 (mod 7).”

For the first part I just sub x into the second congruence. But to how do i do the second part. The answer is that the converse is false, so i guess i just need to find a counter example for that. But how am i meant to know that it is false? also how would i go about finding a counter example.

thanks and im sure ill be posting more of these proving questions soon...

Drexel28 · #2 $Old$ November 7th, 2009, 11:43 PM

Quote:

Originally Posted by lost1 $View Post$

Hey I need help with some proving questions....

Q1) Prove the following statement, then write down its converse. Is the converse true or false? Prove
your answer.
“For all x 2 Z, if x ≡ −1 (mod 7) then x^3 ≡ −1 (mod 7).”

For the first part I just sub x into the second congruence. But to how do i do the second part. The answer is that the converse is false, so i guess i just need to find a counter example for that. But how am i meant to know that it is false? also how would i go about finding a counter example.

thanks and im sure ill be posting more of these proving questions soon...

Let's think about number two logically. What we basically want to do is find a number $n^3$ such that $n^3-6=7m$ and that $n$ is not congruent to mod 7. Well, let's think of the first couple numbers. $1^3=1,2^3=8,3^3=27$ . Well only one of these really looks promising. Clearly $27-6=21$ satisfies our first condition and $3$ is clearly not congruent to 6 mod 7. A lot of times, when a counter example is to be found it is the first couple cases.

lost1 · #3 $Old$ November 8th, 2009, 06:22 AM

Hey thanks again been a great help! Iv got this logical equivalence qs i cant seem to do:

Simplify the following...

2) (p <-> q) V (~ p ^ q)

I i expand the (p <-> q) <=> (~p V q) ^ (~q V p) but dont realy know where to go from there. Thanks for the help again really appreciate it.

Also have another question which i simplify to this: p ^ r ^ q ^ (p V ~q)
and answer is: p ^ r ^ q

Im not sure how that last step is done and if there are any of the 'laws' that i should state for that step.

Thanks

Grandad · #4 $Old$ November 8th, 2009, 09:38 AM

Hello lost1

Quote:

Originally Posted by lost1 $View Post$

Hey thanks again been a great help! Iv got this logical equivalence qs i cant seem to do:

Simplify the following...

2) (p <-> q) V (~ p ^ q)

I i expand the (p <-> q) <=> (~p V q) ^ (~q V p) but dont realy know where to go from there. Thanks for the help again really appreciate it.

Also have another question which i simplify to this: p ^ r ^ q ^ (p V ~q)
and answer is: p ^ r ^ q

Im not sure how that last step is done and if there are any of the 'laws' that i should state for that step.

Thanks

For the first question, I think the easiest method is to use a Truth Table - see the attached diagram. This shows in the result column, that the proposition is true except where $p$ is $T$ and $q$ is $F$ . So it's equivalent to $\sim(p\,\, \land \sim q)$ , or (using De Morgan) $\sim p\,\,\lor q$

The second one is quite straightforward, if you use the Distributive Law on the last two terms:

$q \land (p \,\,\lor\sim q) \equiv (q\land p) \lor (q \,\,\land \sim q)$

$\equiv (q\land p)\lor F$

$\equiv q \land p$

So the whole expression is equivalent to

$p \land r \land (q \land p)$

$\equiv p \land r \land q$

Grandad

lost1 · #5 $Old$ November 8th, 2009, 09:00 PM

Hey thanks for the explanation. However for that first question it asks to do it by using 'standard logical equivalences'. Infact all the questions seem to ask to use logical equivalences to simplify and only use truth tables to show that two given propositions are equal. =/

Grandad · #6 $Old$ November 9th, 2009, 12:05 AM

Hello lost1

Quote:

Originally Posted by lost1 $View Post$

Hey thanks for the explanation. However for that first question it asks to do it by using 'standard logical equivalences'. Infact all the questions seem to ask to use logical equivalences to simplify and only use truth tables to show that two given propositions are equal. =/

OK. How's this?

Expand $p \leftrightarrow q$ as $(p \land q) \lor (\sim p\,\, \land \sim q)$ , then use the Distributive Law to 'factorise' the last two terms; thus:

$(p \leftrightarrow q) \lor (\sim p\,\,\land q)$

$\equiv (p \land q) \lor (\sim p\,\, \land \sim q)\lor (\sim p\,\,\land q)$

$\equiv (p \land q) \lor \Big(\sim p\,\, \land (\sim q \lor \,\, q)\Big)$

$\equiv (p \land q) \lor (\sim p\,\, \land T)$

$\equiv (p \land q) \lor \sim p$

$\equiv (p\,\, \lor \sim p) \land (q\,\, \lor \sim p)$

$\equiv T\land (q\,\, \lor \sim p)$

$\equiv q\,\, \lor \sim p$

Grandad