Proving each conditional statement is a tautology

Question

I'm having trouble trying to show that each of the conditional statement below is a tautology without using a truth table. I'm assuming you would have to use logical equivalence to figure this out. I know that a tautology is when the truth value of the conditional statements are all true. Can someone help me solve this? Please show me step by step how I would solve this with an explanation so that I can better understand this.

$1.$ $[\neg p \land (p \lor q)] \to q$
$2.$ $[(p \to q) \land (q \to r)] \to (p \to r)$
$3.$ $[p \land (p \to q)] \to q$

Answer 1

My first time posting an answer, pardon my formatting.

1. [¬p∧(p∨q)]→q[¬p∧(p∨q)]→q

2. [(p→q)∧(q→r)]→(p→r)[(p→q)∧(q→r)]→(p→r)

3. [p∧(p→q)]→q

Answer 2

Hint

Rif to :

• Kenneth Rosen, Discrete mathematics and its applications (7th ed), page 35 :

Exercise 10 asked you to show that the above formulae are tautologies using truth tables.

Then :

Exercise 12 : Show that each conditional statement in Exercise 10 is a tautology without using truth tables.

We have to use the logical equivalences listed in page 27 and the method described in Example 8 [page 30], i.e. we have to transform the formula through logical equivalences until we get $T$ (true).

Thus, for :

1. $[¬p∧(p∨q)]→q$

first of all, we have to remove the conditional using Material implication [see Table 7, page 28] :

$\lnot [\lnot p \land (p \lor q)] \lor q$

and then use De Morgan's laws to "move" inside the negation :

$[p \lor (\lnot p \land \lnot q)] \lor q$.

Then we apply Distributive laws :

$([(p \lor \lnot p) \land (p \lor \lnot q)] \lor q) \equiv ([T \land (p \lor \lnot q)] \lor q)$

followed by Identity laws : $T \land a \equiv a$ :

$((p \lor \lnot q) \lor q) \equiv (p \lor (q \lor \lnot q))$

by Associative laws.

Finally, we apply Domination laws : $a \lor T \equiv T$ :

$p \lor T \equiv T$

and we can conclude that formula 1. is a tautology.

---

The same proof can be easily modified in order to solve also 3.

Answer 3

Show that each of these conditional statements is a tautology by using truth tables. (And then without using the truth tables.) a) (p ∧ q) → p b) p → (p ∨ q) c) ￢p → (p → q)