GATE IT 2004 | Question: 31

Question

Let $p, q, r$ and $s$ be four primitive statements. Consider the following arguments:

• $P:  [(¬p\vee  q) ∧ (r → s) ∧ (p \vee  r)] → (¬s → q)$
• $Q:  [(¬p ∧q) ∧ [q → (p → r)]] → ¬r$
• $R:  [[(q ∧ r) → p] ∧ (¬q \vee  p)] → r$
• $S:  [p ∧ (p → r) ∧ (q \vee  ¬ r)] → q$

Which of the above arguments are valid?

• A. $P$ and $Q$ only
• B. $P$ and $R$ only
• C. $P$ and $S$ only
• D. $P, Q, R$ and $S$

Comments

Admins, please change the or symbol in expression P look like an OR symbol.It looks more like literal 'v'

---

An implication is false in exactly one situation.
that is for X -> Y, when X: T and Y: F
either you hit a contradiction (valid) or you land on a working assignment (invalid, and that's the counterexample)

Answer 1

An argument form is valid if no matter what propositions are substituted for the propositional
variables in its premises, the conclusion is true if the premises are all true.
i.e. $\left( p_1 \wedge p_2 \wedge \ldots \wedge p_n \right ) \rightarrow q$ is a tautology.

$$\begin{array}{l|l}\hline \text{$P:\large{\neg\color{Red}\not {p}\vee q}$}  & \text{$Q:\large{\neg{p}}$}\\ \text{$\quad \large{\neg\color{Red}\not {r}\vee s}$} & \text{$\large{\quad \quad\color{Red}\not {q}}$}\\ \text{$ \large{\quad  \underline{\color{Red}\not {p}\vee \color{Red}\not {r}}}$}& \text{$\large \quad {\underline {\neg\color{Red}\not {q}\vee(\neg {p}\vee r)}}$}\\ \text{$\large\qquad\;\; s\vee q$   also, $\large\neg s\to q$ $\large\color{Green}\checkmark$} & \text{$\qquad\quad\large\ \neg {p}\vee r$}\\ & \text{$\color{Red} {\large \neq \neg r}$} \\\hline
\text{$R: \large{\neg(q\wedge r)\vee p\\ \neg{q}\vee p}$$\large{ \;\;=\underline{\neg{q}\vee \neg{r}\vee {p}\\ \;\neg {q}\vee p}\\ \qquad  {p}\vee\neg{q}\vee \neg {r}}$} & \text{$S:\large{\color{Red}\not {p}\\\neg\color{Red}\not {p}\;\vee \color{Red}\not {r}\\ \underline{q \vee \neg\color{Red}\not {r}}}$}\\ & \text{$\large\qquad\;\; q$  $\qquad\large\color{Green}\checkmark$}\\ \text{$\color{Red} {\large \neq  r}$}\\\hline   \end{array}$$

Correct Answer: $C$

Comments

Resolution, Kenneth Rosen Section 1.6

---

@Sambhrant Maurya

brackets are not properly defined.

---

got by truth table

Answer 2

P:  [(¬p v q) ∧ (r → s) ∧ (p v r)] → (¬s → q)

This must be valid ( All options contains P) No need to evaluate.

R:  [[(q ∧ r) → p] ∧ (¬q v p)] → r ->

This is invalid, Put q = False, P= True, R = False to derive "False" result !

S:  [p ∧ (p → r] ∧ (q v ¬ r)] → q This is valid !

->

p

P-> r

-------

r

q v ¬ r

----------

q

So Answer ->

3) P and S only

Comments

Good approach of option elimination..👌

Answer 3

According to me, using the rules of inference like resolution principle to come up with valid conclusions is tricky since there can be multiple valid conclusions. Instead, using proof by contradiction would be the most accurate way to tackle this question. To prove that a given statement is valid (i.e. a tautology), assume that it is not a tautology. It can only be possible if the right side is false and left side is true. Using this assumption, try to put truth values of proposition variables so as to make the left side true. If it is impossible to make left side true, then the statement is invalid. Otherwise, it's valid.

Another way is to convert the statement into a combination of negation, conjunction and disjunction operators and then simplify the statement as much as possible so that the end result is no more minimisable. If the result is a T, then it is valid. Else, it is invalid.

One more way is to draw the truth table of the statement. If all the values are true, then the statement is valid. Otherwise, it is not.

The last two methods are time-taking. The first method is the best.

Comments

In simple terms assume conclusion to be false.

Case 1(valid): if conclusion is true and you have assumed it false then atleast one premises will be false.

Case 2 (invalid): If conclusion if false and you assume it's opposite, and still you are able to make all premises true, then it is invalid

---

 If it is impossible to make left side true, then the statement is invalid. Otherwise, it's valid.

this one is wrong  

Answer 4

let p->q is conditional proposition here p and q are compound propositions itself
Arguments to be valid if all combinations have to be tautology ( like T->T, F->T, F->F ) and its invalid if it have fallacy ( T->F )
if we somehow get this fallacy (T->F) then an argument is invalid
for options P and S u don't get any such combinations for T->F so P and S are VALID.
for option Q : if we put p=F,q=T,r=T then we get T->F so it is INVALID
for option R : if we put p=F,q=F,r=F then we get T->F so it is INVALID

so Ans is C.

Answer 5

Answer is option C.

 

Answer 6

Let’s try to make conclusion false and all the premises true of the argument. If it’s not possible then it is a valid argument, otherwise invalid argument.

P : [(¬p v q) ∧ (r → s) ∧ (p v r)] → (¬s → q)  
Conclusion is false when s=F and q=F. Now let’s try to make each premise true. (¬p v q) is true when p=F. (r → s) is true when r=F. But now we can’t make (p v r) = true, because p=F & r=F => (p v r) = F. So, the argument P is valid. (not possible to make conclusion false and all the premises true of the argument)

Q : [(¬p ∧ q) ∧ (q → (p → r))] → (¬r)
Conclusion is false when r=T. Now let’s try to make each premise true. (¬p ∧ q) is true when p=F and q=T. (q → (p → r)) = (q → (p → T)) = (q → T) is true. So, the argument Q is invalid. (possible to make conclusion false and all the premises true of the argument)

R:  [[(q ∧ r) → p] ∧ (¬q v p)] → r 
Conclusion is false when r=F. Now let’s try to make each premise true. [(q ∧ r) → p] = [F → p] is true. (¬q v p) is true for 3 possible combinations of p & q. So, the argument Q is invalid. (possible to make conclusion false and all the premises true of the argument)

S:  [p ∧ (p → r) ∧ (q v ¬ r)] → q 
Conclusion is false when q=F. Now let’s try to make each premise true. (q v ¬ r) is true when r=F. (p) is true when p=T. But now we can’t make (p → r) = true, because p=T & r=F => (p → r) = F. So, the argument P is valid. (not possible to make conclusion false and all the premises true of the argument)

Comments

I was in search for this answer. This should be the best answer.