3,918 views
2 votes
2 votes
1.$ [(p\to q)\wedge (q\to r)]\to (p\to r)$

2. $[(p \vee q) \wedge (p \to r) \wedge (q \to r)] \to r$

2 Answers

Best answer
4 votes
4 votes
1. $[(p\to q)\wedge (q\to r)]\to (p\to r)$

If p, then q AND if q then r would mean if p, then r which is exactly what the RHS is. So, the implication is true. (But RHS implies LHS is not true here as RHS does not say that p should imply q or q should imply r)

2. $[(p \vee q) \wedge (p \to r) \wedge (q \to r)] \to r$

Either p or q is true; if p then r; if q then r. So, either way we have r and RHS is r only. So, again this implication is true.

So, both are tautologies.
selected by
1 votes
1 votes

Here is another approach...

problem 1 solution: $[(p\to q)\wedge (q\to r)]\to (p\to r)$

 

The expression is not a tautology if we find any 1 case when it is false.

As it's an implication, it is false IFF  ( LHS = T and RHS = F )

Let's check if it's possible.

consider RHS. We have to make it False.

p-->r is FALSE only when ( p = T AND r = F )

So fix the values as p=T and r=F

-------------------------------------------------------------

Now consider LHS. We have to make it TRUE

LHS is true only when both the terms of the ( ^ ) are TRUE

So check if it is possible.

(q-->r) is NOT TRUE IFF q=T and r=F

r = F from out assumption. So, q cannot be T (because we want the whole term to be TRUE) So, q=F

Thus far we have, p=T, r=F,q=F

--------------------------------------------

Now, consider the first term of ( ^ ).

p-->q should be TRUE (because we want to make the entire LHS TRUE)

This is possible IFF p is NOT TRUE WHILE q IS FALSE

but our assumption is p=T, r=F,q=F.

Therefore, p-->q is FALSE.

Which makes LHS False. 

Hence, we cannot make RHS=F and LHS=T at the same time. Which means the given expression can never be false == > tautology.


problem 2 solution:  $[(p \vee q) \wedge (p \to r) \wedge (q \to r)] \to r$

 

Again using the same approach,

This is an implication which can be False IFF ( LHS =T AND RHS = F )

Make RHS False. i.e. r = F

Now consider LHS. We have to make LHS =TRUE

Which is possible only when all the 3 terms in LHS are TRUE (as they are ANDed)

Now take q-->r is LHS.

r = F from our assumptionTherefore q cannot be T. Which means q is F.

So far we have r = F, q = F

Now take p-->r

again r=F. Therefore p cannot be T. Which means p is False.

So far we have, q=F, r=F, p=F

Now take p ∨ q

We already have p=F, q=F

Which means p ∨ q  cannot be True.

Hence, the LHS != True

 

Which means, we can never make LHS=T and RHS=F 

in the given expression. So it can never be False

==> it is a tautology

edited by

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
1 answer
2
1 votes
1 votes
2 answers
4