Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Propositional logic proof

  1. Feb 8, 2005 #1
    I want to prove [itex](A \supset B) \wedge (B \supset C) \wedge (D \supset \neg C) \wedge (A \vee D) \equiv (B \vee \neg C)
    so I have to show that [itex]\neg ( ((A \supset B) \wedge (B \supset C) \wedge (D \supset \neg C) \wedge (A \vee D)) \supset (B \vee \neg C))[/itex]
    is inconsistent, and I proceed as follows:

    [tex]\begin{array}{ccccccccccc}\neg ( ((A \supset B) &\wedge &(B \supset C) &\wedge &(D \supset \neg C) &\wedge &(A \vee D)) &\supset (B \vee \neg C))\\

    \neg ( \neg((A \supset B) &\wedge &(B \supset C) &\wedge &(D \supset \neg C) &\wedge &(A \vee D)) &\vee &(B \vee \neg C))\\

    ((A \supset B) &, &(B \supset C) &, &(D \supset \neg C) &, &(A \vee D)) &, &\neg (B \vee \neg C))\\

    (\neg A \vee B) &, &(\neg B \vee C) &, &(\neg D \vee \neg C) &, &(A \vee D) &, &\neg B&, &C))\\

    \text{contradiction}&, &\neg B &, &\neg D&, &A &, &\neg B &, &C


    so I end up with a contradiction showing that the original statement is correct.

    Question: is there a "better", more formal way to present this proof?
    Last edited: Feb 8, 2005
  2. jcsd
  3. Feb 10, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    You seem to have that screwed up. for instance in case A is false but B is true, then the left side is false but the right side is true, so they are not equivalent.

    Maybe instead of the last two operational symbols being "and" , then "equivalence", they should be the opposite order, "equivalence", then "and".

    i.e. the following two statements might be equivalent:

    I. C implies B and B implies A, and notC implies D,

    II. [either B or notC], and[ either A or D].

    at least I implies II. let see... no that doesn't work either. then if B is true and A is true, but D is false, one side is true and the other is false.
  4. Feb 10, 2005 #3


    User Avatar
    Science Advisor
    Homework Helper

    Assuming I didn't make a mistake, it seems to me that what you're trying to prove is false (so you can't prove it). Make a truth table, the two sentences aren't "nearly" equivalent.
  5. Feb 10, 2005 #4
    So sorry. I meant to write:

    [itex](A \supset B) \wedge (B \supset C) \wedge (D \supset \neg C) \wedge (A \vee D) \models (B \vee \neg C)

    as the first line.
  6. Feb 10, 2005 #5


    User Avatar
    Science Advisor
    Homework Helper

    what do the symbols mean? especially that one that now replaces equivalence?
  7. Feb 10, 2005 #6
    I believe it is read "yields" if it is the same as |-

    I've seen it used in place of the logical implication symbol so I guess they are the same thing.
  8. Feb 10, 2005 #7
    The meanings are similar but not exactly the same.

    According to what I've read so far, the first one, [itex]\models[/itex], is called the "semantic turnstile".
    [tex]\begin{array}{lll} \text{if} \;&\{a_1, a_2, ..., a_n\} &\models A\\
    \text{then} \; &\{a_1, a_2, ..., a_n\} &\supset A \; \text{is a tautology}\end{array}[/tex]
    or we can say that A is a logical consequence of {a_1, a_2, ..., a_n}.

    The other one, [itex] \vdash[/itex], I think is called the "syntactic turnstile". and
    [tex]\{a_1, a_2, ..., a_n\} &\vdash A[/tex]
    means that A can be proved from [itex]\{a_1, a_2, ..., a_n\}[/itex] by using a set of syntactic rules.

    But frankly, I can't say that I'm clear about exactly what the difference is between those two statements, so I'd love to hear a better explanation from someone who knows. :smile: :smile:
    Last edited: Feb 11, 2005
  9. Feb 11, 2005 #8


    User Avatar
    Science Advisor
    Homework Helper

    This is easy to prove. As far as I know, it should technically be written as:

    [tex]\{(A \supset B) \wedge (B \supset C) \wedge (D \supset \neg C) \wedge (A \vee D)\} \models (B \vee \neg C)[/tex]

    since it is a set of sentences which are said to entail a conclusion sentence. I'm not sure what system of deduction you're using. The only one I'm familiar with is SD. Let's replace the premise by *.
    Code (Text):

    1  | *                             Assumption
    2  | | A                           Assumption
       | |----------------------------
    3  | | A > B                       1 conjunction elimination
    4  | | B                           2-3 conditional elimination
    5  | | B v ~C                      4 disjunction introduction
    6  | | D                           Assumption
       | |----------------------------
    7  | | D > ~C                      1 conjunction elimination
    8  | | ~C                          6-7 conditional elimination
    9  | | B v ~C                      8 disjunction introduction
    10 | A v D                         1 conjunction elimination
    11 | B v ~C                        10, 2-5, 6-9 disjunction elimination
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook