Results 1 to 5 of 5

Math Help - Showing a formula is a tautology

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Showing a formula is a tautology

    I'm currently enrolled in a introductory course on logic and I'm until now everything has been going great. I'm having some trouble with applying monotonicity and the strengthening/weakening of propositions.

    The general of concept of strengthening/weakening seems clear; I understand P \land Q is a stronger proposition than P \lor Q, so: P \land Q \models P \lor Q, since the former has 'less 1s' in its truth table it's a stronger/more restrictive proposition.

    Monotonicity is a bit foggier. How I see it, is that it's basically a form of substitution if we have P \models Q, then P \land R \models Q \land R. If we substitute the left hand side with the 'same thing' we substitute the right hand side with, the relation with respect to stronger/weaker holds. Any more clarification on this subject is more than welcome.

    So much for theory. Now I'm asked to show via a calculation that (R \land (P \Rightarrow Q)) \Rightarrow ((R \Rightarrow P) \Rightarrow Q) is a tautology. To do this I have to show that (R \land (P \Rightarrow Q)) \equiv((R \Rightarrow P) \Rightarrow Q).

    Using some basic calculation/rewriting rules for implication, de Morgan and double negation, I ended up here:
    (R \land (\lnot P \lor Q)) \equiv (Q \lor (R \land \lnot P))

    Now it gets messy, but by applying distribution to the left hand side twice I end up with this:
    ((R \land \lnot P) \lor R) \land ((R \land \lnot P) \lor Q) \equiv (Q \lor (R \land \lnot P))

    Since the basic rules of strengthening\weakening tell us that P \land Q \models P, we also have that ((R \land \lnot P) \lor R) \land ((R \land \lnot P) \lor Q) \models (Q \lor (R \land \lnot P)).

    By applying weakening to: ((R \land \lnot P) \lor R) \land ((R \land \lnot P) \lor Q) \equiv (Q \lor (R \land \lnot P)), we have that: ((R \land \lnot P) \lor Q) \equiv (Q \lor (R \land \lnot P)), which is what we wanted.

    Now, for me this makes sense, but is this actually correct?

    Edit: I'd like to add another exercise I'm not quite sure of, since it seems to be a bit harder.

    Show that: ((P \Rightarrow (Q \lor R)) \land (Q \Rightarrow R)) \Rightarrow (P \Rightarrow R) is a tautology. Again, to show this the left hand side should equal the right hand side.

    First step is rewriting the implications:
    ((\lnot P \lor (Q \lor R)) \land (\lnot Q \lor R)) \equiv (\lnot P \lor R)

    By weakening we now have:
    (\lnot P \lor (Q \lor R) \equiv (\lnot P \lor R)

    But I'm kind of stuck here.
    I could distribute and apply strengthening, but I'm not sure that would be legal. Any help would be welcome!
    Last edited by Diligo; October 7th 2012 at 12:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,560
    Thanks
    785

    Re: Showing a formula is a tautology

    Quote Originally Posted by Diligo View Post
    So much for theory. Now I'm asked to show via a calculation that (R \land (P \Rightarrow Q)) \Rightarrow ((R \Rightarrow P) \Rightarrow Q) is a tautology. To do this I have to show that (R \land (P \Rightarrow Q)) \equiv((R \Rightarrow P) \Rightarrow Q).
    The implication is a tautology, but the biconditional is not: consider R = False and Q = True.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Re: Showing a formula is a tautology

    I've made an error while typing this, wherever you see \equiv it should read \models. But I'm unable to edit my post
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,560
    Thanks
    785

    Re: Showing a formula is a tautology

    In calculus, a function f is called monotonic if x <= y implies f(x) <= f(y) for all x, y. Monotonicity in Boolean logic is the same as monotonicity of functions when Boolean formulas are considered as expressions defining function from {0, 1} to {0, 1}, where 0 represents False and 1 represents True. For example, P /\ R defines the function min(P, R). If we keep R constant, this function is monotonic in P, i.e., if P <= Q, then min(P, R) <= min(Q, R).

    I believe your solution to the first problem makes sense. However, your method is a curious mix of using equivalences and logical implications. Why do you convert some => into disjunctions but other => into |=? Are you required to use this method?

    I personally try not to convert P => Q into ~P \/ Q. Here is how to show R /\ (P => Q) => (R => P) => Q treating implication as "if ... then ...". Assume (1) R, (2) P => Q and (3) R => P. From (3) and (1) we get P, and from it and (2) we get Q, as required. The second formula can be proved in a similar way.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2012
    From
    Earth
    Posts
    9

    Re: Showing a formula is a tautology

    Well basically in this part of the course we are required to use these steps, the second part is more about reasoning, more in line with your method

    We're using this book Logical Reasoning: A First Course: R Nederpelt,F Kamareddine: 9780954300678: Amazon.com: Books the methods it teaches seem to be pretty tied to Dijkstra's/specific methods.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Showing that the formula is correct.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 7th 2011, 12:23 PM
  2. tautology help
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 17th 2008, 10:09 AM
  3. Tautology
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 1st 2008, 07:17 AM
  4. Tautology
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 1st 2007, 04:02 PM
  5. tautology
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 19th 2007, 07:17 PM

Search Tags


/mathhelpforum @mathhelpforum