Thread: Prove a tautology

1. 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

2. 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.}$

3. 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$

4. 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$

,

,

,

,

,

,

,

,

,

,

,

,

,

,

prove a tautol

Click on a term to search for related topics.