Prove a tautology

aflaco · January 13th 2008, 06:41 AM

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

**dgomes** · August 21st 2011, 01:30 PM

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

**emakarov** · August 21st 2011, 05:53 PM

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$

**Soroban** · August 21st 2011, 08:40 PM

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$

Thread: Prove a tautology

LinkBack

Thread Tools

Display

Prove a tautology

Re: Prove a tautology

Re: Prove a tautology

Re: Prove a tautology

Similar Math Help Forum Discussions

Prove a tautology without truth tables.

tautology

How can I prove that this propositional logic statement a tautology is?

Tautology

tautology