Logic: Prove that, if p => q or s, then -q and -s => -p

[Fisk92]

Hi, there were no logic forums or something that looked like it, so I didn't know where to put this.

Anyway, I got the problem that I need to prove an example of the logic that: If p => q or s, then -q and -s => -p Where the - stands for "not".
So here is the example:

If x+y is not even, then x is even or y is not even. I found no problem here, because if x is even and y is not even, then x+y is not even.

Because if x = 2q (even number) and y = 2k + 1 (not even number),
then x + y = 2q + 2k + 1
which is equal to x + y = 2(q + k) + 1. Which is not an even number. And I belive that in logic, the or goes for if either p or q is true or both are true. So statement should be true.

Now I try to reverse with the: If p => q or s, then -q and -s => -p

I believe p is "x+y is not even" and then q is "x is even" and s is "y is not even"

So I think the next sentence must be:

-q (x is not even) and -s (y is even) then -p (x+y is even)

So if x is not even and y is even then x+y is even.

But that doesn't make sense?

x is not even, x = 2k + 1.
y is even, y = 2q

x + y = 2k + 2q + 1
x + y = 2(k + q) + 1
x + y = not even.

But the first statement was true, then the second should also according to, If p => q or s, then -q and -s => -p

So the first statement is true, and the second is false shouldn't be happening?

What am I doing wrong?

 

[ksdhart2]

How you'd go about it depends entirely on where the grouping symbols are at in the logical statement. Is the left-hand side:

\(\displaystyle P \implies \left( Q \vee S \right)\)

or

\(\displaystyle \left( P \implies Q \right) \vee S\)

Similarly, is the right-hand side:

\(\displaystyle \left( \neg Q \wedge \neg S \right) \implies \neg P\)

or

\(\displaystyle \neg Q \wedge \left( \neg S \implies \neg P \right)\)?

Or are they something else altogether?

 

[Fisk92]

I use the form of, P => (Q or S), (-Q and -S) => -P

 

[ksdhart2]

Ah, okay. Thanks for the information. Based on this, I believe where you're going wrong is that the statements you're picking for P, Q, and S are incompatible with the given logical statements. Let statement P be "The sum of X and Y is odd [not even]." Now, if P is true (i.e. X + Y is odd), we know that exactly one of X and Y must be even and the other odd. The first logical implication tells us that:

\(\displaystyle P \implies \left( Q \vee S \right)\)

Accordingly, to have this implication always hold, Q must be the statement "X is even and Y is odd" and S must be "X is odd and Y is even." Alternatively, you can flip-flop those two statements without changing anything. So now it's a question of, does the second logical implication hold?

\(\displaystyle \left(\neg Q \wedge \neg S \right) \implies \neg P\)

Based on the above, Not Q would be the statement "X is odd [not even] or Y is even [not odd]" and Not S would be the statement "X is even [not odd] or Y is odd [not even]." The hypothesis we're testing is that if both of those are true, then Not P ("The sum of X and Y is even") is true.

If we let R be the statement "X is odd" and T be the statement "Y is even," then [Not Q and Not S] becomes [(R or T) and (Not R or Not T)]. That's logically equivalent to [R xor T] (xor is exclusive or, i.e. exactly one but not both is true). So, now, the question is: does [R xor T] imply Not P?

We can rewrite [R xor T] as [(R and not T) or (Not R and T)]. That's the same as [(X is odd and Y is odd) or (X is even and Y is even)]. So, what happens when X and Y have the same "evenness?" Well, we know that means that X + Y will be even. This is the same as Not P, so we've proved what we set out to prove.

This all goes to show that it's very important to be sure you're picking the proper statements, and sometimes it might just be easier to work with abstract conditionals than get bogged down in making sure we pick statements that are compatible.

 

[Fisk92]

Okay, thank you very much. I'm still a bit confused about the switching out Not Q with R. So Not Q = R? If that's the case, if I needed to built a truth table over that, should I also include things like R and T, or just explain down with words following the truth table?

 

[ksdhart2]

Okay, thank you very much. I'm still a bit confused about the switching out Not Q with R. So Not Q = R? If that's the case, if I needed to built a truth table over that, should I also include things like R and T, or just explain down with words following the truth table?

That's partially correct. The statement [R] is part of [Not Q], but the two aren't the same. Remember that I had defined [Q] with two parts, as "X is even and Y is odd." Accordingly, we could rewrite that as [Not R ("X is even") and Not T ("Y is odd")]. Then, to find [Not Q], we negate that statement and get [R or T]. So, you can't replace with [Not Q] with [R], but you can replace it with [R or T], because the two statements are logically equivalent. For the same reason, you could replace [Q] with [Not R and Not T].

 

[Fisk92]

Alright, got it. Thanks.