1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Propositional logic proof
  1. Logic proof (Replies: 2)

  2. Propositional Logic (Replies: 3)