# Math Help - 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

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

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

$((\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$

4. ## 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$
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 39, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9027044773101807, "perplexity": 801.8288474779929}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-48/segments/1448398444138.33/warc/CC-MAIN-20151124205404-00267-ip-10-71-132-137.ec2.internal.warc.gz"}