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

@Ayush Bi implication means if LHS nad RHS have same truth values then it is true. Now when R is false and if I take P as true and Q as false then LHS is true and RHS is false making bi conditional as false.

---

for which option are you talking tushar?

---

option c

---

@tusharp-No.When you make R as false, the R.H.S of implication is like this

$(T \lor F) \land (F \lor T) \equiv T$

The reason is $\lnot R$ is taking care for the other case.

---

sorry.. misread it :(

---

It's okay.Make all such mistakes before gate exam.But not on the exam day :)

---

@ayush one doubt in option c

(P ⋁ Q) ↔ (P V R) ∧ (Q V ~R)
 

 if we say biconditional p<-->q,than it means p->q and q->p

but p->q is not valid so how are we saying it as correct...as in option B we have said p-->q is not valid.?clarify please.?? 

 

 

 

---

@Shubham Shukla-Yes I got you.

When we talk about satisfiability, we generally look only for just single combination of values of variables, that can make our expression true.

So, even if under one case, option (c) fails, you cannot say that it is wrong because $\exists P, \exists Q, \exists R$ such that both $(P \lor Q)$ and $(P \lor R) \land (Q \lor \lnot R)$ is satisfiable.

You take it in this way,

$(P \lor Q)$ is unsatisfiable if and only if $(P \lor R) \land (Q \lor \lnot R)$ is unsatisfiable.

Now, $P \lor Q$ is unsatisfiable means $P=F,Q=F$

so, R.H.S. becomes $(F \lor R) \land (F \lor \lnot R)=R \land \lnot R=F$

Hence, option (c) is valid.

but in case of validity, your expression MUST be true under all combinations of truth table values.

---

ok ayush yeah i was thinking same its due to satisfiable thing thank you

---

@Ayush Upadhyaya I have a doubt on option d it says that (pvq)-> F if and only if both p and q is unsatisfiable , means if pand q are false then f->f there it is true ,but since here it is mentioned if and only if so we have to look the reverse way also ,so in that case since pvq is false then p can be false and q can be true also i.e. one of them can be satisfiable also ?  Is this approach right here?

---

@Arjun @gatecse @Abhrajyoti00 

for option c , if we use p = 0 q = 1 r = 0

then 

P v Q = 1

(P v R) and ( Q V R`) = 0

Here  P VQ   become 1 and other part is 0.   

Then how it is satisfiable.

---

@GateOverflow04 Satisfiable means atleast one value must be true.

If we make $(P \lor Q)$ as satisfiable, we can see that it becomes $T$ at $3$ conditions: $(T,F),(F,T),(T,T)$

Now can we make $(P \lor R) \land (Q \lor \lnot R)$ satisfiable for all of the 3 cases? Yes. We need to chooose the value of $R$ carefully to make it satisfiable.

$\implies (P\lor R) \land  (Q \lor R’)$

take $(P,Q,R)$ values as : $(T,F,F) \ or \ (F,T, T) \ or \ (T,T, any  \ value)$

You can even show unsatisfiablity by taking $(P,Q,R) = (F,F, any \ value)$

---

@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?