GATE1987-10e

Question

Show that the conclusion $(r \to q)$ follows from the premises:

$p, (p \to q) \vee (p \wedge (r \to q))$

Answer 1

$P_1 :p$

$P_2: (p → q) ∨ (p ∧ (r → q) )$

$P_1 \wedge P_2 \rightarrow   (r \rightarrow q)$

$\equiv [p \wedge [(\neg p \vee q) \vee (p\wedge \neg r \vee (p \wedge q))]  \rightarrow (r \rightarrow q)$
$\equiv [p \wedge [\neg p \vee q \vee  (p\wedge \neg r) \vee  (p\wedge q)]] \rightarrow (r \rightarrow q)$
$\equiv [ (p\wedge \neg r) \vee (p\wedge q)] \rightarrow (r \rightarrow q)$
$\equiv [ (\neg p\vee r )\wedge (\neg p\vee  \neg q)\vee \neg r \vee q] $
$\equiv [ \neg p\vee  (r\wedge \neg q) \vee \neg r \vee q]$
$\equiv [\neg p \vee \neg q \vee \neg r \vee q] $
$\equiv [\neg p \vee  (q \vee \neg q) \vee \neg r] $
$\equiv 1$ (Tautology)

Hence, proved.

Comments

Is it a correct solution ??

---

nice approach @ prashant

---

[P∧[¬P∨Q∨(P∧¬R)∨(P∧Q)]]→(R→Q)

how did this become this [(P∧¬R)∨(P∧Q)]→(R→Q) please explain me this step

As this part P∧[(¬P∨Q) is modus ponens and should reduce to Q but Q is not in the wff

 

---

if i solved this question by making  truth table then all are true only one value is going to false can you explain where i am going to wrong ???

---

you should post your table then anyone can help u

---

this is my solution.

---

in complete table it should have one more column i.e.

[p∧((p→q)∨(p∧(r→q)))]->(r->q) and u will get all T

Answer 2

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

=> (~p V q ) V (p ∧ (~r V q))

=> (~p V q) V ( (p∧ ~r) V (p ∧ q) )

=> ( 0 V q ) V ( (1∧ ~r) V (1 ∧ q))

=> q V ( ~r V q )

=> ( ~r V q )

=> (r->q)

Comments

you have solved it by taking p=1, it is necessary to take p=0 and solve it again after that you can declare it is always true

Answer 3

Using Distributive law, (p→q) ∨ (p ∧ (r→q)) = ((p→q) ∨ p) ∧ ((p→q) ∨ (r→q))

Using Simplification, (p→q) ∨ (r→q) is a conclusion.

(p→q) ∨ (r→q) = (¬p ∨ q) ∨ (¬r ∨ q) = ¬p ∨ q ∨ ¬r = ¬p ∨ (r→q)

Using premises p and ¬p ∨ (r→q) and applying Disjunction Syllogism, the conclusion is (r→q).

Comments

It is Modus Ponens and not disjunctive syllogism

 

$p$

$p\rightarrow \left ( r\rightarrow q \right )$

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

$r\rightarrow q$

Answer 4

If we look at it carefully it is given that if premises are true then if r is true then q must be true.

We have data p is true and r is true(as we  want to prove it)

now we will try to prove that r implies q is not the solution. If you substitute p,r is true then truth value of second premise complete depend upon truth value of q. so it must be true and hence the conclusion.

Answer 5

To derive the conclusion we must assume that the premises are true

 

Answer 6

Some n number of premises implies a conclusion means that, If all the n premises are true then conclusion is true as well.
 p  and (p→q)∨(p∧(r→q)) both premises will be true only for below truth value assignments
(p=T,r=F,q=T), (p=T,r=T,q=T), (p=T,r=F,q=F)

none of the above truth value assignments has r=T,q=F  hence , If both the premises(p  and (p→q)∨(p∧(r→q)) ) are true then  (r→q) is true as well.( Note: (r→q) is false for only r=T,q=F truth value assignment)