8,992 views

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?

1. $((P ∨ R)∧(Q ∨ ¬R))⇒(P ∨ Q)$ is logically valid
2. $(P ∨ Q)⇒((P ∨ R))∧(Q ∨ ¬R))$ is logically valid
3. $(P ∨ Q)$ is satisfiable if and only if $(P ∨ R)∧(Q ∨ ¬R)$ is satisfiable
4. $(P ∨ Q)⇒ \text{FALSE}$ if and only if both $P$ and $Q$ are unsatisfiable

Condition in option c can be violated if either of them is unsatisfiable and other is satisfiable. If p= true,Q = false and R is true then LHS will be (True V False) and RHS will be (true or true) AND (False OR False) and thus LHS will be true and RHS will be false for the bi conditional making it false.

i am having also the same doubt. can anyone explain?
reshown

@tusharp @newdreamz a1-z0  there exist at least one combination of values for which it results in True.

Option C is not valid but satisfiable. (Contingency)

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

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.

If and only if means bi-implication.

For option C check this video

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.

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

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

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?

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.

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?