if AB is odd, then a is odd or b is even?

[adam2016]

So this comes from a book I'm currently reading,the chapter is on proof by contrapositive.

but that statement (if ab is odd then a is odd or b is even ) seems pretty wrong to me and sometimes is redundant, in order to get an odd number a and b must both be odd.

if AB is odd then yes I do agree a has to be odd that part of the statement is correct and since it's an or statement we only need one or the other to be true.

from that statement let a = 2 and b = 6 => 6 * 2 = 12

so the statement if ab is odd then a is odd or b is even is wrong because 6 is even and we have one more test case which is b must be even, and b is even but still the answer is even.

The author later goes onto to say : To justify this claim, consider the contrapositive (to the above statement ), "If a is even and b is odd, then ab is even." so, suppose a = 2i, for some integer i. then ab = (2i)b = 2(ib); hence, ab is even.

[2z0kLyTq]

it doesn't say "if ab is odd then a is odd and b is even"?

Not that I know anything about this subject other than what I just read on Wikipedia.

[helios]

from that statement let a = 2 and b = 6 => 6 * 2 = 12

so the statement if ab is odd then a is odd or b is even is wrong because 6 is even and we have one more test case which is b must be even, and b is even but still the answer is even.

You're misunderstanding the statement.
The statement is if (AB is odd) then ((A is odd) or (B is even)). A = 2, B = 6 is not a counterexample, because 12 is not odd.

What the statement is saying is that an odd product's factors are either both odd, or one of them is even.

Case 1: odd(A) && odd(B)
odd(AB) => odd(A) || even(B)
T => T || F
T => T
T

Case 2: odd(A) && even(B)
odd(AB) => odd(A) || even(B)
T => T || T
T => T
T

Case 3: even(A) && odd(B)
(Case 3 is equivalent to case 2 (AB == BA))

Case 4: even(A) && even(B)
odd(AB) => odd(A) || even(B)
F => F || T
F => T
T
(Note: if the left side of the material implication is false, the value of the material implication is true regardless of what's on the right side.)

So for all possible evenness values of A or B, the statement is true, therefore the statement is true.

[adam2016]

What the statement is saying is that an odd product's factors are either both odd, or one of them is even.

Case 1: odd(A) && odd(B)
odd(AB) => odd(A) || even(B)
T => T || F
T => T
T

Case 2: odd(A) && even(B)
odd(AB) => odd(A) || even(B)
T => T || T
T => T
T

but for the product of two numbers to be odd I thought both numbers have to be odd?

test case 1:
if both numbers are odd this will return true 3 * 3 = 9 = true


test case 2:

lets say A is 3 and B is 6, A is odd that is true so we don't even have to check for the second condition, so this equals true? but 3 x 6 = 18 and 18 is not odd?

[helios]

lets say A is 3 and B is 6, A is odd that is true so we don't even have to check for the second condition, so this equals true? but 3 x 6 = 18 and 18 is not odd?

Again, you're inverting the material implication. (P => Q) =/=> (Q => P).

but for the product of two numbers to be odd I thought both numbers have to be odd?

I made a mistake in my previous post, in case 2.

Case 2: odd(A) && even(B)
odd(AB) => odd(A) || even(B)
F => T || T
F => T
T

You're correct. I don't know what I was thinking. (2 * a + 1)*(2 * b) = 2 * (b * (2 * a + 1)) = 2 * c, so odd times even is even.
The statement is confusing because it added a vacuous condition.
We know that odd(AB) => odd(A) && odd(B) (i.e. "both factors of an odd product have to be odd"), but we can make a weaker statement*: odd(AB) => odd(A) || odd(B) ("at least one of the factors must be odd"). Because AB = BA, odd(A) || odd(B) can be simplified to odd(A), so we get odd(AB) => odd(A).
Now, the thing about Boolean algebra is that if you have a valid expression x, you can OR it by a contradiction without changing its value. x == (x || false). So if we have

odd(AB) => odd(A)

we can change that to

odd(AB) => odd(A) || false

and since any false statement is equal to any other false statement, we can replace the "false" with anything we want, such as

odd(AB) => odd(A) || even(B)

If odd(AB) then we know that both A and B have to be odd, so even(B) is necessarily false. We could also have written, say

odd(AB) => odd(A) || even(AB)

or even

odd(AB) => odd(A) || "there are finitely-many prime numbers"

I don't know what the author was trying to accomplish, but this is a seriously roundabout way to make a point.




* If P => Q but Q =/=> P then Q is a logically weaker statement than P.

[adam2016]

We know that odd(AB) => odd(A) && odd(B) (i.e. "both factors of an odd product have to be odd"), but we can make a weaker statement*: odd(AB) => odd(A) || odd(B) ("at least one of the factors must be odd"). Because AB = BA, odd(A) || odd(B) can be simplified to odd(A), so we get odd(AB) => odd(A).

How is it that we can make 1: odd(AB) => odd(A) || odd(B)?

going back to normal math -> 2: odd(AB) => odd(A) && odd(B) but both the former(1) and latter(2) are much different?

I know in boolean algebra that AB + A will give A as A(B+1) = A(1) = A, but how does odd(AB) or odd(BA) simplify to odd(A)?

[helios]

How is it that we can make 1: odd(AB) => odd(A) || odd(B)?

going back to normal math -> 2: odd(AB) => odd(A) && odd(B) but both the former(1) and latter(2) are much different?

I already explained every step of the way.

odd(AB) => odd(A) && odd(B)

implies

odd(AB) => odd(A) || odd(B)

is equivalent to

odd(AB) => odd(A)

is equivalent to

odd(AB) => odd(A) || false

is equivalent to

odd(AB) => odd(A) || even(B)

I know in boolean algebra that AB + A will give A as A(B+1) = A(1) = A, but how does odd(AB) or odd(BA) simplify to odd(A)?

I don't know what this question has to do with anything, but alright.

odd(AB) || odd(BA)

is equivalent to

odd(AB) || odd(AB)

is equivalent to

odd(AB)

implies

odd(A) && odd(B)

implies

odd(A)

[adam2016]

I already explained every step of the way.

odd(AB) => odd(A) && odd(B)

implies

odd(AB) => odd(A) || odd(B)

is equivalent to

odd(AB) => odd(A)

is equivalent to

odd(AB) => odd(A) || false

is equivalent to

odd(AB) => odd(A) || even(B)

My logic is awful :o, I understand odd(AB) => odd(A) && odd(B)

but how does this imply odd(AB) => odd(A) || odd(B)?

lets say that A is odd and B is even, so odd(A) could hold true, since we have hit true for odd(A) we don't need to check the second condition. but still in this example that would mean odd(AB) => odd(A) && odd(even) but this isn't true right?

lets say we have the product of two numbers 5 * 2 = 10, 5 satisfies the first condition, so we don't check for the second condition so odd && even => even?

[helios]

Dude, you keep doing it. You hear "P implies Q", and come back with "but here's a case where Q is true but P is false!"
Material implication is not logical equivalence! (P => Q) =/=> (Q => P). All P => Q says is that whenever P is true, Q is true. If P is false you know nothing about Q, and if Q is true, you know nothing about P.

Consider this statement: "if n is prime and not 2, then n is odd". Is 9 a counterexample?

I understand odd(AB) => odd(A) && odd(B)

but how does this imply odd(AB) => odd(A) || odd(B)?

#include <iostream>

bool implies(bool a, bool b){
    return !(a && !b);
}

int main(){
    for (int i = 0; i < 4; i++){
        bool a_is_odd = i % 2 != 0;
        bool b_is_odd = i / 2 % 2 != 0;
        bool ab_is_odd = a_is_odd && b_is_odd;

        std::cout << "case " << i + 1 << " (" << a_is_odd << ", " << b_is_odd << "): " << implies(implies(ab_is_odd, a_is_odd && b_is_odd), implies(ab_is_odd, a_is_odd || b_is_odd)) << std::endl;
    }
}

[adam2016]

if n is prime and not 2, then n is odd". Is 9 a counterexample?

I would say no it's not a counterexample? as 9 is not a prime number?

[TwilightSpectre]

Adam, here's a way of thinking about it. What you're basically asking is something like this:

We have "Human(X) ⇒ Creature(X) or ChuckNorris(X)". But you're coming and saying well, my dog is a creature, so we don't need to check if my dog is Chuck Norris or not, so therefore my dog is human?

Implication "⇒" is one-way. Being either an Creature or being Chuck Norris is not sufficient to say that this is human. However, if you are a human, you must be a creature — you can't be human and not a creature (or, well, Chuck Norris, but that's also implied by being a Creature and thus is pointless extra information).

[adam2016]

Oh yes so I think I misunderstood what => really means, so let me take a better guess

Consider this statement: "if n is prime and not 2, then n is odd". Is 9 a counterexample?

P: if n is prime and not 2 = True
Q: then n is odd = True

P -> Q

9 is not a prime number and not 2 = False
then n is odd = True

although the premise here is false this still isn't enough information to tell us that the implication is False, right?

so I would say no , 9 is not a counterexample?

[jonnin]

A counter example is just an example that shows the proposed theory to be false.
its really simple.
if I say X*Y s always odd.
you say 2*4 = 8, the above is BS (insert weird symbol that means BS here in serious papers).

[adam2016]

sorry I should have said

P: if n is prime and not 2
Q: then n is odd

P -> Q

9 is not a prime number and not 2 = False
then n is odd = False

so this would still be P -> Q

so then 9 is a counterexample? but wouldn't false and false be vacuously true ? so 9 would not be a counterexample?

[helios]

insert weird symbol that means BS here in serious papers

"1=0"?

9 is not a prime number and not 2 = False
then n is odd = False

Is 9 even?

so this would still be P -> Q

so then 9 is a counterexample?

Dude, it's really simple. Either 9 is a counterexample of "if n is prime and not 2, then n is odd" or it isn't. Stop making questatements and just definitively answer the question: is it a counterexample or isn't it? If it helps, try answering this: exactly what conditions should a counterexample number meet?

[adam2016]

9 is not a prime number and not 2 = False
then n is odd = False

sorry my bad the conclusion is still true in that case.


a counterexample number of "if n is prime and not 2, then n is odd" should be odd and also not be a prime number.

so yes 9 is a counterexample

I already explained every step of the way.

odd(AB) => odd(A) && odd(B)

implies

odd(AB) => odd(A) || odd(B)

The main mistake was that I assumed => or the implication operator meant that if A is True B is True and that if B is True A is True, but that is not the case ,

A -> B

if B is true and A is false this is still vacuously true, I understand that but what I don't get is this

but we can make a weaker statement

odd(AB) => odd(A) && odd(B)

implies

odd(AB) => odd(A) || odd(B)

We know that odd(AB) => odd(A) && odd(B) (i.e. "both factors of an odd product have to be odd"), but we can make a weaker statement*: odd(AB) => odd(A) || odd(B) ("at least one of the factors must be odd"). Because AB = BA, odd(A) || odd(B) can be simplified to odd(A), so we get odd(AB) => odd(A).

how does odd(AB) => odd(A) && odd(B) imply odd(AB) => odd(A) || odd(B) ?

these statements are very different :/, I'm assuming something wrong here

** edit apologies on my logic, still working on it, I've only been studying discrete mathematics directly for 2 days now, thanks for sticking with me :)


- page 205/738 - 4.3.2 contra attack
although that is the second edition of the book and the example is a bit different, the example in my book is - To justify this claim, consider the contrapositive (to the above statement ), "If a is even and b is odd, then ab is even." so, suppose a = 2i, for some integer i. then ab = (2i)b = 2(ib); hence, ab is even.

[helios]

should be odd and also not be a prime number.

so yes 9 is a counterexample

No, incorrect. Both examples and counterexamples must meet the antecedent of the statement. Suppose for a moment that that wasn't true, and I say "all mammals are descended of synapsids" (i.e. "mammal(x) => descendant_of_synapsid(x)"). If a counterexample was allowed to not meed the antecedent then you could pose a non-mammal non-synapsid-descendant as a counterexample: the fact that plants don't descend from synapsids would support the notion that not all mammals descend from synapsids.

how does odd(AB) => odd(A) && odd(B) imply odd(AB) => odd(A) || odd(B) ?

Let's start from something simpler: is there a pair of booleans x and y such that (x && y) && !(x || y)? If there's not, then (x && y) => (x || y). That's what material implication is; P => Q means that under no circumstances P && !Q (i.e. !(P && !Q) is a tautology).

To restate: (P => Q) <=> !(P && !Q)

[adam2016]

in this case "if n is prime and not 2, then n is odd". Is 9 a counterexample"

I mean if I was to look at this objectively, the only even prime number is 2 so therefore if n is odd but looking at it from the point of material implication it's not so clear cut.

lets say we use 9, n <=> 9

so if n is prime and not 2 = False, then n is odd = vacuously true ?

F && F = T( vacuously )

with this statement so if n is prime and not 2 = False, then n is odd = vacuously true that means that 9 is not a counterexample?

I'm probably making little sense :/

[helios]

It's really not complicated. If you have a statement of the form "if P(x) then Q", and an object y such that P(y) is false, then y is neither an example nor a counterexample of the statement. The statement says nothing about y.

Example: "If x is a man then x is mortal". If y is not a man then you know nothing about its mortality. If z is mortal then you know nothing about its humanity.

[adam2016]

Example: "If x is a man then x is mortal". If y is not a man then you know nothing about its mortality. If z is mortal then you know nothing about its humanity.

that makes sense,

so 9 would not be a counterexample?


I could be wrong but no from what I can tell (x && y) && !(x || y) will always be false.