Results 1 to 4 of 4

Thread: 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

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

    $\displaystyle \textbf{Proof.}$

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

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

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

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

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

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

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

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


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

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

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

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

    $\displaystyle \equiv 1$


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

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

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

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

    $\displaystyle \equiv 1$


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

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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

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

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848

    Re: Prove a tautology

    Hello, aflaco!

    This is a variation of dgomes' proof.


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

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

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

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

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

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

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

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

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

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

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

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

    . . $\displaystyle \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: Sep 7th 2010, 06:37 AM
  2. tautology
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 6th 2010, 09:24 AM
  3. Replies: 1
    Last Post: Mar 27th 2009, 06:43 AM
  4. Tautology
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Oct 1st 2008, 06:17 AM
  5. tautology
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 19th 2007, 06:17 PM

Search tags for this page


/mathhelpforum @mathhelpforum