Page 2 of 2 FirstFirst 12
Results 16 to 18 of 18

Math Help - Conditional Propositions & Logical Equivalence

  1. #16
    Banned
    Joined
    Aug 2008
    Posts
    42
    Here now is a syntactical proof that p^(qvr) ====> (p^q)v(p^r) i.e p^(qvr) logically implies (p^q)v(p^r) or [p^(qvr) -----> (p^q)v(p^r)] is a tautology.

    LETS do it in steps:

    1)p^(qvr)......................................... ..................asumption

    2) p...........................................from 1 and using addition elimination

    3) qvr.........................................from 1 and using addition elimination

    4) q................................................. .....................assuption

    5) p^q........................................from 2 and 4 and using addition introduction

    6) (p^q)v(p^r).............................from 5 and using disjunction introduction

    7) q-----> (p^q)v(p^r).................. from 4 to 6 and using the conditional proof rule

    8) r................................................. .......................assumption

    9) p^r.........................................from 2 and 8 and using addition introduction

    10) (p^q)v(p^r)...........................from 9 and using disjunction introduction

    11) r------> (p^q)v(p^r)...............from 8 to 10 and using the conditional proof rule

    12) (p^q)v(p^r).............................from 3,7,11 and using proof by cases or (another name) disjunction elimination

    Hence we have proved : p^(qvr) ====> (p^q)v(p^r)

    NOW the laws of logic used here are:
    a) addition elimination.............P,Q =====> P^Q
    b) addition introduction...........P^Q======> P, or..P^Q====.> Q
    c) disjunction introduction...........P=======> PvQ
    d) disjunction elimination...............{ (PvQ) ^[ (P---->R) ^(Q---->R)] }=====>R. This law is also called proof by cases and

    Many times is completely destroyed in mathematical proofs particularly those in mathematical analysis.

    There may be other interesting proofs for the above,and the converse can be done in a similar way
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Banned
    Joined
    Aug 2008
    Posts
    42
    Here is a semantical proof of p^(qvr) ===> (p^q)v(p^r)............................1

    without using the true table

    we know that p^(qvr) ------> (p^q)v(p^r) is a tautology for all the values of p,q,r .

    Suppose now that the above is not a tautology ,then there exist values of p,q,r for which the above is false:

    Then by the definition of '------>',conditional , p^(qvr) must be true and

    (p^q)v(p^r) false .

    Now by the definition of '^' p must be true, and (qvr) true....................

    Also by the definition of 'v' ,since (p^q)v(p^r) is false ,(p^q) must be false and (q^r) false.

    Since p^q is false by the definition again of '^' p must be false and q the same.

    So far we have proved that p is true and also p is false.

    ...............................a contradiction..................................... ..........

    Thus ...........p^(qvr) ------> (p^q)v(p^r) is a tautology...................

    and...........p^(qvr) ===> (p^q)v(p^r) i.e p^(qvr) logically implies

    (p^q)v(p^r)

    For the converse i.e (p^q)v(p^r)====>p^(qvr) a similar processes is applicable.
    That law of logic is used very often in set theory particularly in proving

    ............... A\cap (BUC) = ( A \cap B )U ( A\cap C )................................

    In every day life the law is used very often as the following example shows:

    We say : if i go to the movies i will buy a coca cola or beer which means that :i go to the movies and buy a coca cola or i go to the movies and buy a beer
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Banned
    Joined
    Aug 2008
    Posts
    42
    Let me now give asyntactical proof of IxI<y<===> --y<x<y in steps
    All proofs in mathematics are syntacical

    NOTE (L) will mean law of logic ,(T) A theorem,(D) a definition,(A) an axiom

    So
    1) IxI<y............................................. ......... an assumption
    2) \forall{x}( x≥0 or x< 0)................................... (A)
    3) x≥0 or x<0 ..............................................from line2 and using Universal elimination (L)
    4) x≥0 .................................................. ......A hypothesis
    5) \forall{x} ( x≥0 \longrightarrowIxI=x )..........................(D) in apsolute values
    6) x≥0 \longrightarrow IxI=x .....................................from 5 and Univ. elimin. (L)
    7) IxI=x .................................................. .....from 4 and 6 and using M.Ponens (L)
    8) x<y .................................................. .......By substituting 7 into 1 (L)
    9) \forall{a}\forall{b}\forall{c} (a≤b and b<c \longrightarrowa<c) .............(T) or a result coming out from iniqalities
    10) 0≤x and x<y \longrightarrow0<y .............................from 9 and Univ.Elim.where we put a=0,b=x,c=y (L)
    11) 0≤x and x<y ............................................from 4 and 8 and using Conjuction Introduction (L)
    12) 0<y .................................................. ......from 10 and 11 and using M.Ponens (L)
    13) \forall{a}\forall{b} (a<b<----->-a>-b) .............................(T)
    14) 0<y<-----> 0>-y ......................................from 13 and Univ. Elim. where a=0,b=y (L)
    15) -y<0 .................................................. .....from 12 and 14 and using M.Ponens (L)
    16) \forall{a}\forall{b}\forall{c} (a<b and b≤c \longrightarrow a<c) ....................(T)
    17) -y<0 and 0≤x - \longrightarrowy<x ..........................from 16 and Univ. Elim.where we put a=-y,b=0,c=x (L)
    18) -y<0 and 0≤x ...........................................from15 and 4 and using conjuction introduction (L)
    19) -y<x .................................................. .....from 17 and 18 and using M.Ponens (L)
    20) -y<x and x<y ( -y<x<y) ..............................from 8 and 19 and conjuction introduction (L)
    21) x≥0 \longrightarrow -y<x<y .....................................from steps 4 to 21 and using the rule of conditional proof (L)

    Now in a similar way and using the definition of apsolute values x<0 \longrightarrow IxI=-x we will come to the result x<0 \longrightarrowy<x<y ( 1a)

    22) -y<x<y .................................................. ..from 2, (1a),21 and Disjuction Elimination (L)
    23) IXI<y \longrightarrowy<x<y ....................................from steps 1 to 23 and using the rule of conditinal proof (L)

    the converse i,e -y<x<y I \longrightarrowxI<y can be done in a similar way
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Logical equivalence
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 12th 2011, 06:22 PM
  2. Logical Equivalence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2010, 02:43 AM
  3. Replies: 3
    Last Post: September 17th 2010, 10:46 AM
  4. Logical Equivalence Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 2nd 2010, 02:06 PM
  5. Logical Equivalence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 23rd 2008, 09:17 PM

Search Tags


/mathhelpforum @mathhelpforum