Results 1 to 14 of 14

Math Help - Proof for Tautologies uisng equations

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Proof for Tautologies uisng equations

    Hi all,

    I looking for some explanation on how to prove a equation a tautolgies. I can quite easl do this using turth table. But when i try to do this using equation i get a bit stuck.

    So for example if i had a problem like as follow

    (r ⇒ (p ∧ q)) ⇔ ((r ⇒ p) ∧ (r ⇒ q))

    I know this is not tautology but what am i suppose to prove to be tautoloy. Should the end verdict be

    (r ⇒ (p ∧ q)) ⇔ ((r ⇒ p) ∧ (r ⇒ q)) <-> TRUE.

    Is this is what am i need to show using rule of inference? Please point me to the right direction.

    thanks

    ssharish
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Proof for Tautologies uisng equations

    Since (r ⇒ (p ∧ q)) ⇔ ((r ⇒ p) ∧ (r ⇒ q)) is a biconditional (i.e., equivalence), one way is to rewrite (r ⇒ (p ∧ q)) until you get ((r ⇒ p) ∧ (r ⇒ q)), or vice versa. This is because A ⇔ A is a tautology for any formula A. Alternatively, which also works not only for biconditionals, you can rewrite the formula until you get TRUE.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Re: Proof for Tautologies uisng equations

    Hey many thanks for the reply. So what your saying is, if take the LHS of the expression and try work my way through until i get to RHS using rule of inference I should prove that the whole expression is tautology as A<=>B is nothing but tautology?

    I also understand your senond approch and I quite find it hard to prove until i get true, for such a huge expression. It might take few pages before i can prove the whole expression is TRUE? Isn't it?

    Thanks very much

    ssharish
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Proof for Tautologies uisng equations

    If you rewrite the left-hand side so that it coincides with the right-hand side, you have A ⇔ A, and

    (A ⇔ A) ⇔
    (A ⇒ A) ∧ (A ⇒ A) ⇔
    (A ∨ A) ∧ (A ∨ A) ⇔
    TRUE ∧ TRUE ⇔
    TRUE
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Re: Proof for Tautologies uisng equations

    Hey thanks very much for that. And can you also clarify is this is true. If I do the following?

    ( (P ^ Q) => (P ^ R) )
    <=> ( (P ^ Q) v (P ^ R) )
    <=> ( (P ^ (Q v R) ) << Can I do this using associative?
    <=> ( p v (Q v R)

    Thanks

    Harish
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Proof for Tautologies uisng equations

    Quote Originally Posted by ssharish View Post
    <=> ( (P ^ Q) v (P ^ R) )
    <=> ( (P ^ (Q v R) ) << Can I do this using associative?
    No, because P ∧ Q is under negation. This is equivalent to P v Q v (P ∧ R).

    You can use LaTeX, e.g., [TEX]\neg P\lor\neg Q\lor (P\land Q)[/TEX] gives \neg P\lor\neg Q\lor (P\land Q), but be sure to use [TEX] and not [tex] tags. Above the edit text box, this is the second icon with the emblem \TeX.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Re: Proof for Tautologies uisng equations

    Hey thanks very emakarov and i'm sorry about the post on not using latex i'm still a newbie and trying to lean. I understand your approch and I hence i asked if i was doing that right. If that is the case I feel like i'm stuck a bit. So for exaple

    ( ( A ^ B ) => ( A ^ C ) <=> ( ( A ^ B ) => C )
    > ( ( A ^ B ) v ( A ^ C ) )
    > ( A v B v ( A ^ C ) ) << I'm actually bit stuck here and i'm no where near to proofing its <=>

    Do you suggest using an associative rule on B v (A ^ C) or anything esle?

    Thanks very much!

    ssharish
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Re: Proof for Tautologies uisng equations

    ok i got this now

    \\((A \land B) \Rightarrow (A \land C)) \Longleftrightarrow ((A \land B) \Rightarrow C)\\\Longleftrightarrow \neg(A \land B) \lor (A \land C)\\\Longleftrightarrow \neg A \lor \neg B \lor (A \land C)\\\Longleftrightarrow \neg A \lor (\neg B \lor A) \land (\neg B \lor C)\\\Longleftrightarrow (\neg A \lor (\neg B \lor A)) \land (\neg A \lor (\neg B \lor C))\\\Longleftrightarrow (\neg A \lor\neg B \lor A) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\neg A \lor A \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\mbox{True} \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow \mbox{True} \land ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow \neg(A \land B) \lor C\\\Longleftrightarrow (A \land B) \Rightarrow C\\

    Do you think my approch is right?

    Thanks

    ssharish
    Last edited by ssharish; October 10th 2011 at 09:25 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    630

    Re: Proof for Tautologies uisng equations

    Hello, ssharish!

    [r \to (p \wedge  q)]\;\Longleftrightarrow\:[(r \to p) \wedge (r \to q)]
    . . \begin{array}{cccccccccc} &\text{Left side} &&&  \\ \hline 1. & r \to (p \wedge q) && 1. & \text{Given} \\ 2. & \sim\!r \vee (p \wedge q) && 2. & \text{Def. impl'n} \\ \\ \end{array} \quad\begin{array}{ccccccc}&\text{Right side} & & & \\ \hline 1. & (r\to p) \wedge (r \to q) && 1. & \text{Given} \\ 2. & (\sim\!r \vee p) \wedge (\sim\!r \vee q) && 2. & \text{Def. impl'n} \\ 3. & \sim\!r \vee (p \wedge q) && 3. & \text{Distr.} \end{array}
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Proof for Tautologies uisng equations

    Quote Originally Posted by ssharish View Post
    Do you think my approch is right?
    Yes. It would be easier to read if you omit some parentheses, in particular, those in \neg(B) and in A\lor(B\lor C) (since disjunction is associative).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Re: Proof for Tautologies uisng equations

    Hey thanks very much for Emakarov and Soroban, I've made the changes as per lex to look better now. Whats do you think of my reasoing now?

    \\((A \land B) \Rightarrow (A \land C)) \Longleftrightarrow ((A \land B) \Rightarrow C)\\\Longleftrightarrow \neg(A \land B) \lor (A \land C)\\\Longleftrightarrow \neg A \lor \neg B \lor (A \land C)\\\Longleftrightarrow \neg A \lor (\neg B \lor A) \land (\neg B \lor C)\\\Longleftrightarrow (\neg A \lor (\neg B \lor A)) \land (\neg A \lor (\neg B \lor C))\\\Longleftrightarrow (\neg A \lor\neg B \lor A) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\neg A \lor A \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow (\mbox{True} \lor\neg B) \land (\neg A \lor\neg B \lor C)\\\Longleftrightarrow \mbox{True} \land ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow ((\neg A \lor\neg B) \lor C)\\\Longleftrightarrow \neg(A \land B) \lor C\\\Longleftrightarrow (A \land B) \Rightarrow C\\

    I'm more quite interested in Step 2 and 3 as i wanted to make sure if I'm using assosiative at the right place and in a right way?

    Thanks a lot for all your guidence.

    ssharish
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Proof for Tautologies uisng equations

    Do you mean associativity or distributivity? If the former, then the third and fourth line should be

    (\neg A\lor\neg B)\lor(A\land C)
    \Leftrightarrow\neg A\lor(\neg B\lor(A\land C))

    However, I think it is better to omit associativity and commutativity steps; otherwise, derivations would be too long.

    I would also make clear that you are rewriting the left-hand side. Currently, the relation between the first and second line is not absolutely clear.

    All this are minor quibbles. Your derivation looks pretty good.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Oct 2011
    Posts
    27

    Re: Proof for Tautologies uisng equations

    Thanks emakarov, sorry i meant associativity there. Perhaps the associativity and distributivity means the same aren't they? But from your expression I see that you put few extra brackets to make things clear which kind of make sense.

    Although Im not quite sure what you mean in the second statement though. Do you mean that I got to show I'm taking the LHS expression to derive the RHS expression? How could i explicitly show that? In addition Im also gonna show the inference rule used at the each step to make things clear Didnt know how to do that using LeTex apart from using \mbox{...}

    Thanks

    ssharish
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: Proof for Tautologies uisng equations

    Quote Originally Posted by ssharish View Post
    Perhaps the associativity and distributivity means the same aren't they?
    No, associativity is (A\lor B)\lor C\Leftrightarrow A\lor(B\lor C), and distributivity is A\lor(B\land C)\Leftrightarrow(A\lor B)\land(A\lor C).

    Quote Originally Posted by ssharish View Post
    Although Im not quite sure what you mean in the second statement though. Do you mean that I got to show I'm taking the LHS expression to derive the RHS expression?
    Yes. Currently, the first line has two formulas connected by \Leftrightarrow. The formula on next line is claimed to be derived from one these two (left or right) by some equivalence, but it is not clear whether you rewrite the left- or right-hand side, or maybe the whole equivalence, on the first line. You could start with the left-hand side only and gradually rewrite it until you get to the right-hand side, or you could explain your intentions with words.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 8
    Last Post: July 6th 2011, 01:47 PM
  2. Tautologies
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 13th 2010, 01:26 PM
  3. Proof using frenet equations
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 9th 2010, 02:32 AM
  4. Proof In a System of Equations
    Posted in the Algebra Forum
    Replies: 9
    Last Post: December 28th 2008, 12:40 AM
  5. Tautologies
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 10th 2007, 03:38 AM

Search Tags


/mathhelpforum @mathhelpforum