(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.

  • Shikadi@lemmy.sdf.org
    link
    fedilink
    arrow-up
    3
    ·
    1 year ago

    Maybe I’m dumb, but the first line reads to me as “if a or b then c” and the second one reads as “not a or b, otherwise c” and those two aren’t equivalent. One is a condition for C, and the other is a condition in general. But it’s been a while, so maybe that’s an okay thing to do?

    • Parsnip@lemmy.sdf.orgOP
      link
      fedilink
      arrow-up
      1
      ·
      1 year ago

      Afaik they are equivalent since using the truth table of a conditional A->B, it’s false when A is true but B is false (like how a philosophical argument is invalid if the premise A is true yet the conclusion B is false) so ~(A->B) = A and ~B and A->B = ~A or B. Were you asking about something else?

      • Shikadi@lemmy.sdf.org
        link
        fedilink
        arrow-up
        1
        ·
        edit-2
        1 year ago

        Yes, something else. you went from (a OR b) -> c to ~(a OR b) OR c.

        The first one you are stating that C will be true if A or B is true But in the second one, there is no ->, so how can they be equivalent? The first line has a truth table of

         A  B
        00: X 
        01: 1 
        10: 1 
        11: 1 
        

        where X 1 1 1 are the values of C

        but the second line has a truth table of

         A  B  C
        000: 1
        001: 1
        010: 0
        011: 1
        100: 0
        101: 1
        110: 0
        111: 1
        

        where 1 1 0 1 0 1 0 1 are values of truth

        so I don’t understand how you can compare them

        • Parsnip@lemmy.sdf.orgOP
          link
          fedilink
          arrow-up
          1
          ·
          edit-2
          1 year ago

          I’m not sure but could it be because, in your first truth table, you assumed the truth value of (a OR b) -> c to be true and you are finding the truth values of c that correspond with pairs of values of a and b?

          However, in the second table you are finding the truth values of ~(a OR b) OR c that correspond with truth values of c as well as a and b so just like you said, you cannot compare the two tables you present above.

          To get the truth table for the proposition (a OR b) -> c, you would find the corresponding truth values to those of a, b and c (like you did in the first table). Something like this:

          A B C   A OR B   (A OR B) -> C
          000       0             1
          001       0             1
          010       1             0
          011       1             1
          100       1             0
          101       1             1
          110       1             0
          111       1             1
          

          since it’s possible for the conditional proposition to be false (i.e. if either A or B are true yet C is false)

          • Shikadi@lemmy.sdf.org
            link
            fedilink
            arrow-up
            1
            ·
            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
            
  • CanadaPlus@lemmy.sdf.org
    link
    fedilink
    arrow-up
    1
    ·
    edit-2
    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)