GATE CSE 2003 | Question: 72

Question

The following resolution rule is used in logic programming.
Derive clause $(P \vee Q)$ from clauses $(P\vee R),(Q \vee ¬R)$
Which of the following statements related to this rule is FALSE?

• A. $((P ∨ R)∧(Q ∨ ¬R))⇒(P ∨ Q)$ is logically valid
• B. $(P ∨ Q)⇒((P ∨ R)∧(Q ∨ ¬R))$ is logically valid
• C. $(P ∨ Q)$ is satisfiable if and only if $(P ∨ R)∧(Q ∨ ¬R)$ is satisfiable
• D. $(P ∨ Q)⇒ \text{FALSE}$ if and only if both $P$ and $Q$ are unsatisfiable

Comments

@Verma Ashish I think your explanation will be correct if the option was (P∨Q) if and only if (P∨R)∧(Q∨¬R) is satisfiable but the option is (P∨Q) is satisfiable if and only if (P∨R)∧(Q∨¬R) is satisfiable.

Please correct me if I am wrong.

---

IN gateoverflow book
In option B there is a mistake in brackets

---

Option A: $(P + R)(Q + R’) \rightarrow (P + Q)$  is valid, since this is the resolution principle

 

Option B: $(P + Q) \rightarrow (P + R)(Q + R') = P’Q’ + PQ + PR’ + QR$ is NOT valid (resolution principle does not work in the converse case)

 

Option C:

Let, $\alpha: P + Q$ and $\beta: (P + R)(Q + R')$

A formula is satisfiable if there exists atleast one true in its truth table.

$A:$ If, $\alpha$ is satisfiable $(P=1, Q=1)$, then $\beta$ is also satisfiable.

$B:$ If, $\beta$ is satisfiable $(P=1, Q=0, R=0)$, then $\alpha$ is also satisfiable.

i.e., the statement is valid.

 

Option D:

Let, $\alpha : (P + Q) \rightarrow false$

and, $\beta :$ both $P$ and $Q$ are unsatisfiable.

$\alpha$ is true when $P=false$ and $Q=false$, and false otherwise

$\beta:$ is true when $P=false$ and $Q=false$, and false otherwise

$\therefore \alpha \equiv \beta$

i.e., the statement is valid.

Answer 1

Taking option $(A)$
$((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q)$ is logically valid.

$((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q)$
$\equiv \neg((P \vee R) \wedge (Q \vee ¬R)) \vee (P \vee Q)$
$\equiv ((\neg P\wedge \neg R) \vee (\neg Q \wedge R)) \vee (P \vee Q)$
$\equiv P \vee \neg R \vee Q \vee R$
$\equiv 1 \vee P \vee Q$
$\equiv  1.$

So, Tautology  (Logically VALID). True

Option $B$
$(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R))$ is logically valid

$(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R))$
$\equiv \neg(P \vee  Q) \vee ((P\vee R) \wedge  (Q \vee ¬R))$
$\equiv (\neg P\wedge \neg Q) \vee (P\wedge Q) \vee (P \wedge \neg R) \vee (Q \wedge R)$

which is a contingency $($can be TRUE or FALSE depending on values of $P,Q$ and $R)$ and hence not logically valid.

Answer B.

Comments

@Deepak Poonia sir I also have exactly the same doubt.
in these two cases:
P: False, Q: True, R: False. We get True ↔ False, which is false.

P: True, Q: False, R: True. We get True ↔ False, which is false.

but, in these two cases:
P: False, Q: True, R: True. We get True ↔ True, which is true.

P: True, Q: False, R: False. We get True ↔ True, which is true.

considering all these cases. Is this what they mean in option (C) “(P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable”?

---

I second @Jay Patel 009. I too have found the exact case where PVR is satisfiable but RHS of bi-implication is not. @GO Classes Please look into this. I think B and C both should be answers.

---

@Shubhamishere Option C is valid. Hence as per the question it's an incorrect option.  

Here is why. Satisfiable means atleast in once case the truth value needs to be true.

So, when  P: False, Q: True, R: True. We get True ↔ True, which is true. This is one of the case where it has become true so it doesn't matter if for the same P and Q when R is False and finally it yields false (i.e. P: False, Q: True, R: False. We get True ↔ False, which is false). We already have one case where it yields true. 

Same goes for the other case (P: True, Q: False, R: True. We get True ↔ False, which is false and P: True, Q: False, R: False. We get True ↔ True, which is true.)  

Answer 2

Let us Consider the options one by one :

(a) ((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) This option is clearly true as this is well known rule for Resolution.

Consider option (c)

(P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable

which means  

(P ⋁ Q) ↔ (P V R) $\wedge$ (Q V ~R)

So it means (P V Q) is true if and only is (P V R) ^ (Q V ~R) is true

Let's suppose assume 
(P V R) $\wedge$ (Q V ~R) is true

So Either of R or ~R can be true at a time.

Say, R is true so

(P V R) term becomes true

Now for the (P V R) $\wedge$ (Q V ~R) to become true
Q must be true

and If Q becomes true, then the LHS of bi-implication i.e. P V Q will become true hence making option (C) as true.

Now consider option (d)

(P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable

Yes this is very obvious as when both P and Q are FALSE, P V Q will result in FALSE, making the above implication true.

Being P and Q unsatisfiable means they are FALSE or a Contradiction.

So, this option is also TRUE.

Remaining option is Option (b)

(P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R)) is logically valid

For the above to be logically valid, it must be a tautology.

Let's check

(P+Q) -> ((P+R).(Q +~R))

~(P+Q) + (PQ + P~R + QR)

~P~Q + PQ + P~R + QR 
and this is definitely not a tautology.

Hence, answer option (B)

Comments

@Abhrajyoti00

thank you.

What does if and only if means here:

(Here what I understood finally):→

whenever (P v R) and ( Q V R`) is true then  (P v Q) must be true but vise versa might not be true.

Please confirm me.

---

@GateOverflow04 Iff (if and only if) means both side it must be true. LHS → RHS and RHS → LHS both.

It’s also called Bi-implication $(<->)$

---

@Abhrajyoti00

It’s mean if  on any one particular truth table value if both side satisfy then it is satisfiable.

Answer 3

Option B is false...
   ((P ∨ R)) ∧ (Q ∨ ¬R))
=  (P∧ ¬R) ∨ (Q ∧ R)
(P∨Q) doesn't imply (P∧ ¬R) ∨ (Q ∧ R)

Comments

B is false.

when P is true , Q false and R is true.

True -> False = false.

valid means it should be true for every value of truth assignment.

---

in option c can we apply resolution principle?? I mean here arguments are satisfiable and not valid. Isnt that resolution can be applied only when we have valid arguments??

---

In option c:-

(P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable

If P=1,Q=0,R=1

LHS is 1 and RHS is 0

So how this is true?

Answer 4

answer = option B

option A : follows from the correct definition of Resolution principle, hence this option is true.

option B : does not follow from resolution principle, + it's not logically valid. It can also be verified using truth table. Hence, this option is false.

option C : this entire statement becomes true as both $P \vee Q$ and $(P \vee R) \wedge (Q \vee \neg R)$ are individually satisfiable.

option D : is always true as LHS remains false.

Comments

in (c) it is given that " (P ∨ Q) is satisfiable IF AND ONLY IF (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable. "

but here they are individually satisfiable..how come this statement is true?

---

In option D ,if both p and q are unsatisfiable,then LHS becomes false,but RHS must be true,but here they have given RHS as false,how is this valid?