Prove this argument with rules of inference

Posted on 2009-04-25
Last Modified: 2016-02-10
How do I use the rules of inference to show that the following is logically valid?

[(~p V q) -> r] /\ [s V ~q] /\ [~t] /\ [p -> t] /\ [(~p /\ r) -> ~s] => ~q

I've used Matlab to check that it is actually valid, but I need to show a proof using the rules of inference.
Question by:rhianwen
    LVL 84

    Accepted Solution

    [(~p V q) -> r] /\ [s V ~q] /\ [~t] /\ [p -> t] /\ [(~p /\ r) -> ~s]  /\ q

    [(~p V true) -> r] /\ [s V false] /\ [~t] /\ [p -> t] /\ [(~p /\ r) -> ~s]
    [ r] /\ [s] /\ ~p /\ [(~p /\ r) -> ~s]
    [s] /\ [~s]
    is a contradiction

    Author Comment

    Why can you put the q on the end there? Also if its a contradiction doesn't that prove the argument invalid? I know the argument is valid because I used Matlab to construct a truth table to check it.
    LVL 84

    Expert Comment

    [(~p V q) -> r] /\ [s V ~q] /\ [~t] /\ [p -> t] /\ [(~p /\ r) -> ~s]  /\ q
    is invalid, so
    [(~p V q) -> r] /\ [s V ~q] /\ [~t] /\ [p -> t] /\ [(~p /\ r) -> ~s] => ~q
    is valid

    Author Comment

    So using the rules of inference I can say

    H1     (~p V q) -> r
    H2     s V ~q
    H3     ~t
    H4     p -> t
    H5     (~p /\ r) -> ~s


    H3 & H4
                 ~t /\ p -> t
                  => ~p            (6)  (modus tollens)

    H5 & (6)
               ~p /\ (~p /\ r) -> ~s
                => ~p /\ ~p -> (r -> ~s)               (exportation)
                =>  ~p -> (r -> ~s)
                 => r -> ~s                (7)

    this is where I get stuck. In my head I can do the proof in like 4 steps but I'm having trouble laying it out in terms of the rules.

    LVL 84

    Expert Comment

    6 & 1
    => r  (8)

    8 & 7
    => ~s  (9)

    9 & 2
    => ~q


    Author Comment

    Ahh awesome thankyou!

    For some reason I was thinking I could only use each statement once so I was getting stuck with the 6 & 1 bit.

    Featured Post

    Highfive + Dolby Voice = No More Audio Complaints!

    Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

    Join & Write a Comment

    Suggested Solutions

    Introduction HTML checkboxes provide the perfect way for a web developer to receive client input when the client's options might be none, one or many.  But the PHP code for processing the checkboxes can be confusing at first.  What if a checkbox is…
    Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! How to Know You are Making a Difference at EE In August, 2013, one …
    Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…
    This tutorial will teach you the core code needed to finalize the addition of a watermark to your image. The viewer will use a small PHP class to learn and create a watermark.

    728 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    17 Experts available now in Live!

    Get 1:1 Help Now