math

269 readers

2 users here now

Interesting news and discussion centered around Mathematics

founded 1 year ago

MODERATORS

[email protected]

Interesting logic proof: (a OR b) -> c = (a -> c) AND (b -> c) (mathb.in)

submitted 1 year ago* (last edited 1 year ago) by [email protected] to c/[email protected]

13 comments fedilink hide all child comments

(a OR b) -> c

= ~(a OR b) OR c

= (~a AND ~b) OR c

= (~a OR c) AND (~b OR c)

= (a -> c) AND (b -> c) as required

I haven’t formally learnt logic so I’m not sure if my proof is what you’d call rigorous, but the result is pretty useful for splitting up conditionals in proofs like some of the number theory proofs I’ve been trying. E.g.

Show that if a is greater than 2 and a^m + 1 is prime, then a is even and m is a power of 2

In symbolic form this is:

∀a >= 2 ( a^m + 1 is prime -> a is even AND m is a power of 2 )

The contrapositive is:

∀a >= 2 ( a is odd OR m is NOT a power of 2 -> a^m + 1 is composite )

and due to the result above, this becomes

∀a >= 2 ( a is odd -> a^m + 1 is composite ) AND ( m is NOT a power of 2 -> a^m + 1 is composite )

so you can just prove two simpler conditionals instead of one more complicated one.

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 1 points 1 year ago

Oh I think I'm starting to get it. You're converting whether or not the proposition is true into a conditional, not the proposition itself. I don't think (a OR b) -> c = ~(a OR b) OR c is valid, I think it needs to be written such that it communicates The proposition (a OR b) -> c is true if the following conditional ~(a OR b) OR c is true. It would be more clear in the opposite order too, If the conditional ~(a OR b) OR c is true, then the proposition (a OR b) -> c is also true.

Without a set of data, you have my first truth table, so you can't actually say whether or not (a OR b) -> c is true. However, the conditional has an associated complete truth table. They're not equivalent. I can prove that they're not equivalent by giving you another conditional that satisfies (a OR b) -> c: ~(A or B or C) or C which simplifies to C. The truth tables are different, so c != ~(a OR b) OR c however in your notation, (a OR b) -> c = ~(a OR b) OR c, which means the way I solved it would be written (a OR b) -> c = c. I'm going to switch to double equals for clarity:

1) (a OR b) -> c == ~(a OR b) OR c.
2) (a OR b) -> c == c.
3) If 1 is true, and 2 is true, then ~(a OR b) OR c == c. (Transitive property: “things which are equal to the same thing are also equal to each other.”)
4) ~(a OR b) OR c != c, therefore 1 and 2 can't both be true

A B C    C     (A OR B) -> C
00 0      0              1    <- This line is where the difference is
00 1      1              1
01 0      0              0
01 1      1              1
10 0      0              0
10 1      1              1
11 0      0              0
11 1      1              1