Prove $(p \lor q) \land (\neg p \lor r) \to (q \lor r)$ is a tautology

74 Views Asked by At

I am looking for a way to prove that the statement,

$$(p \lor q) \land (\neg p \lor r) \to (q \lor r)$$

is a tautology without the help of the truth table, by using only laws and theorems like De Morgan's Law, Domination Law, etc. Also, I can't use the rules of inference. Please help, thank you.

1

There are 1 best solutions below

0
On BEST ANSWER

Start from

$$(p∨q) ∧ (¬p∨r) → (q∨r) $$

Apply $(p\rightarrow q)\Leftrightarrow(\neg p\vee q)$ have

$$(\neg p\wedge q)\vee(p\wedge r)\vee(q\vee r)$$


Notice $(\neg p\wedge q)$ and $(p\wedge r)$ are contradict to each other

That means one of them has to be true, therefore the whole statement will also be true

Which implies it's a tautology


Apply $(p\vee\neg p)\Leftrightarrow\top$ that

$$\top\vee (q\vee r)$$

Apply $(\top\vee p)\Leftrightarrow \top$ we have

$$\top\tag*{$\square$}$$