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

Dark Mode

9,317 views

44 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

0

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

0

2 votes

Let us take each option one by one and examine them,

(Representing in a Boolean Logic for clear understanding)

**Taking Option (A),**

*((P ∨ R) ∧ (Q ∨ ~R)) ⇒ (P ∨ Q)*

≡ ((P + R)(Q + R’))’ + (P + Q)

≡ (PQ + PR’ + QR)’ + P + Q

≡ (P’ + Q’)(P’ + R)(Q’ + R’) + P + Q

≡ (P’ + P’R + P’Q’ + Q’R)(Q’ + R’) + P + Q

≡ (P’ + Q’R)(Q’ + R’) + P + Q

≡ P’Q’ + P’R’ + Q’R + P + Q

≡ P + (Q’ + Q) + (R’ + R)

≡ 1

So, **This statement is Tautology i.e., Logically Valid.**

**Taking Option (B),**

*(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ~R)
≡ *(P + Q)’ + ((P + R).(Q + R’)

≡ P’Q’ + PQ + PR’ + QR

This statement is neither True nor False (can be True or False depending on the values of P, Q and R). So, this is Contingency.

**Hence, definately not a Tautology i.e., Logically Invalid.**

**Taking Option (C),**

*(P ∨ Q) is satisfiable if and only if (P ∨ R) ∨ (Q ∨ ~R) is Satisfiable*

this statement means: (P ∨ Q) ⇔ (P ∨ R) ∨ (Q ∨ ~R)

Now, here both R and R’ can’t be True at the same time. Either one of them may be True.

Let’s assume, R is True. So, R’ must be False.

So, (P ∨ R) is True.

Now, (Q ∨ R’) to become True, Q must be True.

and If Q becomes true, then the L.H.S of the bi-implication i.e., (P ∨ Q) will become true and **hence option (C) is True.**

**Taking Option (D),**

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

P and Q are unsatisfiable means both P and Q are False i.e., Contradiction. So, it is very much clear that if both P = 0 and Q = 0, then (P ∨ Q) = 0 i.e., Contradiction which is Unsatisfiable.

**Hence option (D) is True.
Finally, Answer is Option (B).**