Results 1 to 4 of 4

Math Help - Proving rule of inference

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    92

    Proving rule of inference

    Prove or disprove that the following rule of inference is sound:
    Hint: You can use a truth table, but a careful logical
    argument will also do it.

    (p \/ q \/ r)
    (~p \/ s)
    ---------------
    (q \/ r \/ s)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    This inference rule is called resolution. The programming language Prolog has it; in fact, Prolog programs run by doing resolution.

    So what it is the difficulty with this problem? To show that the rule is sound one has to show that: for any interpretation, or model, M, if all premise formulas are true in M, then the conclusion is also true in M. An interpretation is a function from propositional letters to the set {True, False}. By considering different interpretations and computing the truth value of each formula, you can say whether this is correct.

    Well, it's not wise to consider all possible interpretations, because there are 2^(2^4) = 2^16 of them. Hint: when dealing with formulas that have a lot of disjunctions, it is often easier to find interpretations where formulas are false. So here, assume that the conclusion is false, and...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    92
    Can you elaborate your answer in an easy way so that I can understand, because I am new to this and I don't want my teacher to think that I have cheated.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    There are two ways to approach this problem, as the hint says: a formal proof and a common-sense argument.

    If you want to solve this problem in a precise mathematical way, you need to know and be able to use the following concepts:

    (1) Propositional variables, connectives and formulas;

    (2) Interpretation, or model: a function from prop. variables to {T, F};

    (3) Boolean functions of one or two arguments and using truth tables to specify them, e.g.:
    Code:
    f(F, F) = F
    f(F, T) = F
    f(T, F) = F
    F(T, T) = T
    (4) Boolean functions and their truth tables corresponding to propositional connectives: /\, \/, etc.;

    (5) Truth value of a propositional formula in a given interpretation;

    (6) Rule of inference; when it is sound;

    (7) Probably the most important: how to make mathematical argument. E.g., how to prove statements of the form "For all such-and-such objects, the following holds: ...", "If ..., then ..."; what are proofs by contradiction, counterexamples, etc.

    If you know these concepts and how to apply them, it should not be too difficult to solve the problem. If you still can't figure it out, post here the description of where exactly you are stuck. E.g.: I assumed that the premises are true in M, but there are too many such M's, so I can't go over all of them and verify if the conclusion is true in M.

    There is no easier way to come up with a formal proof; you need to know the concepts and have some experience in using them.

    If you can't spare the efforts to learn all this, you can give a less precise explanation that any reasonable person would understand. You are asked to show that if the first two formulas are true, then the third one is true as well. Another way to say this is: If the third formula is false, then at least one of the first two is false as well.

    Assume that the third formula is false. Then all of q, r, and s are ... . We play the devil's advocate: let's assume that both formulas on top are true. Since s is ... and the second formula is true, this implies that p is ... . But then how can the first formula be true? So we showed the last sentence of the previous paragraph is correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: March 4th 2011, 08:27 AM
  2. Replies: 1
    Last Post: November 25th 2010, 03:33 PM
  3. Replies: 0
    Last Post: October 22nd 2010, 11:19 AM
  4. [SOLVED] Proving the rule of sum of sets.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 10th 2009, 01:36 PM
  5. Proving L'Hopital's (Bernoulli's) Rule
    Posted in the Calculus Forum
    Replies: 1
    Last Post: August 8th 2009, 10:42 AM

Search Tags


/mathhelpforum @mathhelpforum