GATE CSE 2004 | Question: 70

Question

The following propositional statement is  $\left(P \implies \left(Q \vee R\right)\right) \implies \left(\left(P \wedge Q \right)\implies R\right)$

• A.    satisfiable but not valid
• B.    valid
• C.    a contradiction
• D.    None of the above

Answer 1

Answer a

It is false when P = T, Q = T, R = F and hence cannot be valid.

It is true (satisfiable) when P = T, Q = T, R = T

Comments

what does it means '' not valid '' in option a ?????

---

Tautology: A tautology is a proposition that is always ture. 

ex: (p  v ~p)= T

Contradiction: A contradiction is a proposition that is always false.

ex: (p ^ ~p)=F

Contigency: A contigency is a proposition that is neither a tautology nor a contradiction.

ex: (p v q)----> ~r

* A propositional logic is said to be satisfiable if it is either a tautology or contigency.

* If logic is contradiction then it is said to be unsatisfiable.

* By contigency we means the logic can be ture or false.

* Contradiction is the unsatisfiable function.

* Statement is valid means tautology.

* Statement is not valid means not tautology.

---

You can reduce the equation to $P' + Q' + R$ by using $A \rightarrow B \equiv A' + B$

Answer 2

Given statement  $(P \Rightarrow (Q \vee R)) \Rightarrow ((P \wedge Q) \Rightarrow R)$ can be simplified as follows

  $ \equiv (\neg P \vee (Q \vee R) ) \Rightarrow (\neg (P \wedge Q) \vee R) \\ \equiv (\neg P \vee R \vee Q ) \Rightarrow (\neg P \vee \neg Q \vee R) \\ \equiv ((\neg P \vee R )\vee Q ) \Rightarrow ((\neg P \vee R) \vee \neg Q)  \\ $

Let $(\neg P \vee R ) = A $, then $(A \vee Q ) \Rightarrow (A \vee \neg Q) $  [simplifying this further]

$ \neg(A \vee Q ) \vee (A \vee \neg Q) $

$ (\neg A \wedge \neg Q)  \vee (A \vee \neg Q) $

$[(\neg A \wedge \neg Q)  \vee A] \vee \neg Q $     [As, $ X \vee (\neg X \wedge Y) = X \vee Y  $ ]

$  (\neg Q \vee A) \vee \neg Q $

$  (\neg Q \vee A) $

$  (\neg Q \vee (\neg P \vee R ) ) $

For $Q=F$, result is True

For $Q=T, P=T, R=F$, result is False

Hence, Satisfiable(true atleast once) but not valid

Comments

≡ ((¬P∨R)∨Q) ⇒ ((¬P∨R)∨¬Q)

≡ Q⇒¬Q

Please, explain this step.

---

@rajankakaniya when I tried to prove that equivalence, I got to know that I was ignoring some cases, ultimately proving that they are not equivalent. I have edited my answer now you can take a look at that.

---

Thanks ! @taran97

correct now and understood.

Answer 3

Check for validity by making given implication $false$

Option $\large A$

---

 THE BELOW ANSWER IS WRONG

---

By  Exportation Law,

$P \implies Q \implies R \equiv (P\land Q ) \implies R$

applying it to given proposition

$\left(P \implies \left(Q \vee R\right)\right) \implies \left(\left(P \wedge Q \right)\implies R\right) \equiv \left( P \land \left( Q \lor R\right) \land \left( P \land Q\right)  \implies R \right)$

checking validity first

 

Comments

(P⟹(Q∨R))⟹((P∧Q)⟹R)

≡ (P∧(Q∨R)∧(P∧Q)⟹R)

As per my understanding, we can not write as per above using that exportation law.

@subbus

 

Because in question brackets are given as below

 

(P⟹(Q∨R))  ⟹  ((P∧Q)⟹R)

≡   ( (P⟹(Q∨R)) ∧ (P∧Q) )   ⟹  R.

 

(A → B) → (C → D) this is in question.

 

You have taken this as

A → (B → (C → D))

≡ (A ^ B) → (C → D)

≡ ((A ^ B) ^ C) →  D

this differs from original question.

Please, check and correct me if wrong.

---

you are right @rajankakaniya.

My mistake is that I thought the implication like other logical connectives is associative but it turns out that implication is only right-associative.

Thank you for commenting :). I shall correct my answer now

 

---

Understood your updated answer. Thanks !

It is difficult to write symbols in normal text. Which tool are you using ?

---

I had felt the same and switched to a Wacom pen tablet with the OneNote application.

Answer 4

Applying by case method,

case: Let P = T,

(Q V R) → (Q → R)

(Q V R) → (Q’ V R)

(Q V R)’ + (Q’ V R)

Q’R’ + Q’ + R

Q’(1+R’) + R = Q’+R

Here, Q’+R is satisfiable but not valid.