Results 1 to 4 of 4

Math Help - Prove a tautology

  1. #1
    aflaco
    Guest

    Prove a tautology

    I have an exam coming up where I have to be able to prove certain conditions are tautologies, however I am having a very difficult time using logical equivalences to do so.

    Can any one help me to prove the following to be a tautology using logical equivalences?

    [(p v q) ^ (~p v r) -> (q v r)]


    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2011
    Posts
    10

    Re: Prove a tautology

    \text{I will use the following convention: }TRUE=1 \text{ and } FALSE=0 \text{.}

    \textbf{Proof.}

    ((p \vee q) \wedge (\sim p \vee r)) \rightarrow (q \vee r)

    \equiv \sim ((p \vee q) \wedge (\sim p \vee r)) \vee  (q \vee r)

    \equiv  \sim(p \vee q) \vee \sim(\sim p \vee r) \vee  (q \vee r)

    \equiv  (\sim p \wedge \sim q) \vee (p \wedge \sim r) \vee  q \vee r

    \equiv  (\sim p \wedge \sim q) \vee  q \vee (p \wedge \sim r) \vee r

    \equiv ((\sim p \vee q) \wedge (\sim q \vee q)) \vee ((p \vee r) \wedge (\sim r \vee r))

    \equiv ((\sim p \vee q) \wedge 1) \vee ((p \vee r) \wedge 1)

    \equiv (\sim p \wedge 1) \vee (q \wedge 1) \vee (p \wedge 1) \vee (r \wedge 1)


    \text{i) Suppose that } p=1 \text{. Then:}

    ((p \vee q) \wedge (\sim p \vee r)) \rightarrow (q \vee r)

    \equiv (0 \wedge 1) \vee (q \wedge 1) \vee (1 \wedge 1) \vee (r \wedge 1)

    \equiv 0 \vee (q \wedge 1) \vee 1 \vee (r \wedge 1)

    \equiv 1


    \text{ii) Suppose that } p=0 \text{. Then:}

    ((p \vee q) \wedge (\sim p \vee r)) \rightarrow (q \vee r)

    \equiv (1 \wedge 1) \vee (q \wedge 1) \vee (0 \wedge 1) \vee (r \wedge 1)

    \equiv 1 \vee (q \wedge 1) \vee 0 \vee (r \wedge 1)

    \equiv 1


    \text{Hence, the expression is always true, i.e., is a tautology.}
    \text{Q.E.D.}
    Last edited by dgomes; August 21st 2011 at 02:38 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Prove a tautology

    There is no need to consider p = 0 and p = 1. This mixes truth tables into a purely syntactic argument. There are equivalences p /\ 1 = p, p \/ 1 = 1 and p \/ ~p = 1. So, we have

    ((\neg p \vee q) \wedge 1) \vee ((p \vee r) \wedge 1)
    \equiv \neg p\lor q\lor p\lor r
    \equiv 1\lor q\lor q
    \equiv 1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,716
    Thanks
    634

    Re: Prove a tautology

    Hello, aflaco!

    This is a variation of dgomes' proof.


    \text{Prove: }\:\bigg[(p \vee q) \;\wedge ( \sim p \vee r)\bigg] \to (q \vee r)

    \bigg[(p \vee q) \wedge (\sim p \vee r)\bigg] \rightarrow (q \vee r)

    . . \equiv\;\sim \bigg[(p \vee q) \wedge (\sim p \vee r)\bigg] \vee  (q \vee r)

    . . \equiv\;  \sim(p \vee q)\: \vee \sim(\sim p \vee r) \vee  (q \vee r)

    . . \equiv\;  (\sim p\: \wedge \sim q) \vee (p\: \wedge \sim r) \vee  q \vee r

    . . \equiv\;  (\sim p\: \wedge \sim q) \vee  q \vee (p\:  \wedge \sim r) \vee r

    . . \equiv\; \bigg[(\sim p \vee q) \wedge (\sim q \vee q)\bigg] \vee \bigg[(p \vee r) \wedge (\sim r \vee r)\bigg]

    . . \equiv\; \bigg[(\sim p \vee q) \wedge T\bigg] \vee \bigg[(p \vee r) \wedge T\bigg]

    . . \equiv \; (\sim p \vee q) \vee (p \vee r)

    . . \equiv\; \sim p \vee q \vee p \vee r

    . . \equiv\; (p\: \vee \sim p) \vee (q \vee r)

    . . \equiv\; T \vee (q \vee r)

    . . \equiv\;\;\;T

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a tautology without truth tables.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 7th 2010, 06:37 AM
  2. tautology
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 6th 2010, 09:24 AM
  3. Replies: 1
    Last Post: March 27th 2009, 06:43 AM
  4. Tautology
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 1st 2008, 06:17 AM
  5. tautology
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 19th 2007, 06:17 PM

/mathhelpforum @mathhelpforum