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

submitted 1 year ago* (last edited 1 year ago) by parsnip283874 to c/math

7 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

[-] CanadaPlus 1 points 1 year ago* (last edited 1 year ago)

So observing that this looks true because a OR b only fails when both a and b do, here's an alternative:

a OR b -> c

Conditional contraposition:

~c -> ~(a OR b)

De Morgan's law 1:

~c -> ~a AND ~b

I'm not actually sure what this kind of distribution is called, but it makes sense:

(~c -> ~a) AND (~c -> ~b)

Two more contrapositions:

(a -> c) AND (b -> c)

this post was submitted on 23 Jul 2023

9 points (100.0% liked)

math

268 readers

2 users here now

Interesting news and discussion centered around Mathematics

founded 1 year ago

MODERATORS

goosethe