edited by
13,947 views
57 votes
57 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?

  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
edited by

6 Answers

3 votes
3 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).

2 votes
2 votes

please sir correct me if i am wrong any were

Answer:

Related questions