Question

If x^2 is divisible by 4 then x is eve. How are we supposed to prove this implication in Discrete Mathematics? Using truth tables? or by some other way?

Answer 1

*even

Answer 2

try proving the contrapositive

Answer 3

how?

Answer 4

whats the contrapositive of given conditional statement ?

Answer 5

If x is not even the x^2 is not divisible by 4

Answer 6

yes, `not even` can be replaced by `odd`

Answer 7

statement : `if x^2 is divisible by 4, then x is even`
contrapositive : `if x id odd, then x^2 is not divisible by 4`

Answer 8

since the original statement and contrapositive follow the same truth values, proving contrapositive is same as proving the original statement

Answer 9

`if x id odd, then x^2 is not divisible by 4`

Proof :
say x = 2k + 1
x^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2q+1 = odd number
an odd number is not divisible by 4

Answer 10

If we are given the postulate that p implies q = not q implies not p
and q implies p = not p implies not q

Answer 11

then can we use truth tables to prove these two and conclude that since these are true our initial implication is true. would that be correct?

Answer 12

is that another question ?

Answer 13

no no. I'm asking if we do it like this would that be correct. I actually asked can this be proved using truth tables in any way?

Answer 14

never seen anything like that before, but my knowledge in math so tiny so...

Answer 15

like this :p

Answer 16

nice :) but why are you doing both :
1) p->q and
2) q->p

?

Answer 17

you just need to prove it in one direction right ?

Answer 18

Yea. just for the sake of it. Because we did both in class and the assignment is related to that.

Answer 19

how does showing that an original statements truth value is equal to its contrapositive; and the converse of the original is equal to its own contrapositive .... prove that the original statement is true?

the original statement

if the cow is alive, then the cow is sleeping has the same truth value as: if the cow is not sleeping, then the cow is not alive.

the converse statement:

if the cow is sleeping, then the cow is alive. has the same truth value as : if the cow is not alive then the cow is not sleeping

i cant see how this proves the original statement, without knowing if P and Q share the same truth value to start with.

is there an error in my thinking?

Answer 20

I'm not sure I know the reason. I just know that that is how we prove an impilcation and that if the contra-positive is true, the implication is true. It's a rule or something.

Answer 21

but how do we show that its true to start with?

Answer 22

in a lot of statements, its easier to show that the contrapositive is true, rather than the original statements original structure.

Answer 23

I honestly have no idea. I'm just a student. I wouldn't be asking if I knew :p

Answer 24

If x^2 is divisible by 4 then x is even

contraP

If x is odd, then x^2 is not divisible by 4

let x be an odd number: x = 2n+1

square it: (2n+1)^2 = 4n^2 +2n + 1

factor out a 4: 4 (n^2 +n/2 + 1/4)

and when we divide by 4, we get: n^2 +n/2 + 1/4

showing that the results is never an integer .... just a thought

Answer 25

how does that prove our implication or it's contra-positive?

Answer 26

trying to recall if there is a suitable way to approach it from there ....

Answer 27

There might be. But it eludes me :p

Answer 28

4n^2 +2n + 1 = 4k, for some integer k

4n^2 +2n + 1-4k = 0 is a quadratic, that we can solve for n

\[n=\frac{-2\pm\sqrt{4-4(4)(1-4k)}}{2(4)}\]
\[n=\frac{-2\pm\sqrt{4(1-4(1-4k))}}{2(4)}\]
\[n=\frac{-2\pm2\sqrt{1-4+16k}}{2(4)}\]
\[n=\frac{-1\pm\sqrt{16k-3}}{4}\]
got to her elol

Answer 29

16k-3 >= 0

16k >= 3

k>= 3/16 so k has to be at best be an integer that is greater or equal to 1

but im prolly overthinking stuff ...

Answer 30

yea you are.

Answer 31

:) good luck with it then

Answer 32

Thanks. Thankyou for your time too :)

Answer 33

If x^2 is divisible by 4 then x is even

contraP

If x is odd, then x^2 is not divisible by 4

let x be an odd number: x = 2n+1, for some integer n

square it: (2n+1)^2 = 4n^2 +2n + 1

this is where i started overthinking it .... so to get it back on track:


factor it like this: 2(2n^2 +n) + 1

now n^2 + n is an integer since the set of integers is closed under addition and multiplication

let k = n^2 + n to clean this up to see that the results of squaring is just another odd number: 2k + 1

if it is divisible by 4 then for some integer, m ...
2k + 1 = 4m

2k - 4m + 1 = 0

2(k-2m) + 1 = 0

again because of closure, k-2m is just some integer and what we have shown is that in order for the square of an odd number to be divisible by 4, then 0 must be an odd number.

0 is not an odd number, so we have proven our contrapositive to be true, namely:
If x is odd, then x^2 is not divisible by 4 is true