The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.8k views

The following resolution rule is used in logic programming.
Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬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) ⇒ FALSE if and only if both P and Q are unsatisfiable
asked in Mathematical Logic by Veteran (59.4k points)
edited by | 1.8k views
0

update the option (c) as 

(C) (P ∨ Q) is satisfiable if and only if (P ∨ R) ⋀ (Q ∨ ¬R) is satisfiable.

source @ http://gateforum.com/wp-content/uploads/2013/01/CS-2003.pdf

+4

Hi , can you please explain the reason why (a) is correct .

Here , I have made the truth table for the option (a) .

The LHS here becomes : (P+R).(Q+~R)  and RHS becomes : (P+Q)

So , if we make truth table it becomes :

P Q R LHS RHS
0 0 0 0 0
0 0 1 0 0
0 1 0 0 1
0 1 1 1 1
1 0 0 1 1
1 0 1 0 1
1 1 0 1 1
1 1 1 1 1

 

So , here for all values of LHS , there is NOT 1->0 in RHS. Is this the reason why this is valid ?

 

@Arjun sir can you please clear this doubt ?

 

+1
Yes. That is the only reason for it..
0
Thank you @Arjun sir :)
0
Can you please solve it using boolean algebra
0
Someone plz explain the method of interpreting c) and d) by boolean algebra.
+3
a) When there is "implication($P\Rightarrow Q$)" try to make P as True and Q as false , if it can't possible , the formula will always be valid.

like in option 'a' we have to make P$\vee$Q false , and for this both P and Q must have to false. but when P and Q are both false left side becomes R$\wedge$R' , which is equal to False so eventually we failed to make $T\Rightarrow F$ , hence this formula becomes this way Valid

b) Apply same logic.If you can succeed making $T\Rightarrow F$ it won't be valid then.

c) Here as implication is bidirectional , so rather than talking about satiafiability , we will talk about unsatisfiability , as in that case we only have to make formula 'False'

Take it this way P$\vee$Q is unsatiafiable $\Leftrightarrow$ $(P\vee R)\wedge (Q\vee R')$ is unsatisfiable. to make P$\vee$Q  unsatisfiable means both P and Q must be False. and in that case RHS will become $(F\vee R)\wedge (F\vee R')$ which is R$\wedge$R' , which will also False so in that way option C is correct.

d) $(P\vee Q)\Rightarrow FALSE \Leftrightarrow$ P ia false and Q is false.

RHS will be True when both P and Q are False and in that way LHS will be $F\Rightarrow F$ , that is True so both LHS and RHS are same means both becomes equivalent.

5 Answers

+14 votes
TAKING OPTION (A)

((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid.

((P + R) . (Q + ¬R))' + (P + Q)

((P' R') + (Q' R)) + (P + Q)

P + R' + Q + R

= 1 + P + Q = 1 SO TAUTOLOGY MEANS VALID. True

Option B

(P ∨ Q) ⇒ ((P ∨ R)) ∧ (Q ∨ ¬R)) is logically valid

(P  + Q)' + ((P + R)) .  (Q + ¬R))

P'Q' + PQ + PR' +QR WHICH IS CONTINGENCY SO ONLY SATISFIABLE.

So option B is false.
answered by Veteran (59.6k points)
edited by
0
What is the meaning of 3rd statement..
After making the truth table how to conclude that it is a wrong/right statement?
0
which 3rd
0
(P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable.
0

(P ∨ Q) $\leftrightarrow$ (P ∨ R) ∧ (Q ∨ ¬R) [ a  $\leftrightarrow$ b $\equiv$ a'b' +ab]

[(P ∨ Q)'[(P ∨ R) ∧ (Q ∨ ¬R)]' ]+ (P ∨ Q)(P ∨ R) ∧ (Q ∨ ¬R)

[ p'q' + p'r'+ q'r] + (p+q)(p + r)(q + ¬r)

[ p'q' + p'r'+ q'r] + [(pq+ pr+ +p+ qr )(q + ¬r)]

[ p'q' + p'r'+ q'r] + [pq+pqr'+pqr+pr']

= 1 so tautology so satisfiable. [ (ab)' +ab= 1]

 

0
(P ∨ Q) is satisfiable if and only if (P ∨ R) ∧ (Q ∨ ¬R) is satisfiable.
does it mean
(P ∨ Q) ↔↔ (P ∨ R) ∧ (Q ∨ ¬R)  ???
@anirudh sir
0

[ p'q' + p'r'+ q'r] + [pq+pqr'+pqr+pr']

= 1 so tautology so satisfiable. [ (ab)' +ab= 1]

$(pq)'=(p'+q') \ not \ p'q'$ 

it is contingency instead of tautology but it is satisfiable, that is correct.

+6 votes
Option B is false...
   ((P ∨ R)) ∧ (Q ∨ ¬R))
=  (P∧ ¬R) ∨ (Q ∧ R)
(P∨Q) doesn't imply (P∧ ¬R) ∨ (Q ∧ R)
answered by Veteran (54.8k points)
edited by
+2

typo in option (c) ,
   (P ∨ Q) is satisfiable if and only if (P ∨ R) ⋀ (Q ∨ ¬R) is satisfiable

.for (P V Q) satisficable , if R is true then Q should be true , otherwise P should be true .... 

therefore (P ∨ Q) is satisfiable if and only if (P ∨ R) ⋀ (Q ∨ ¬R) is satisfiable

+1
"if" side is fine. But how did you conclude "only if" part?
0
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.
0
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??
0
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?
+3 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.

answered by Boss (30.6k points)
0
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?
0
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?
+2 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)

answered by Loyal (7.9k points)
edited by
+1 vote

please sir correct me if i am wrong any were

answered by Junior (521 points)
0
Ur handwriting .... very hard to understand ...
0
Sorry @Puja mishra
0
It is understandable!


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,526 questions
42,802 answers
121,614 comments
42,165 users