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

Dark Mode

8,992 views

42 votes

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?

- $((P ∨ R)∧(Q ∨ ¬R))⇒(P ∨ Q)$ is logically valid
- $(P ∨ Q)⇒((P ∨ R))∧(Q ∨ ¬R))$ is logically valid
- $(P ∨ Q)$ is satisfiable if and only if $(P ∨ R)∧(Q ∨ ¬R)$ is satisfiable
- $(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?

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

0

reshown
Jan 16, 2019
by Verma Ashish

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

1

21 votes

Best answer

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.

$((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.

20 votes

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)**

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

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.

7

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

0

7 votes

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.

0