The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2.1k 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
asked in Mathematical Logic by Veteran (59.6k points)
edited by | 2.1k 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.
+4
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.
0
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.

 

How c is correct?
0

thanks @ Rupendra Choudhary , it cleared all doubts :)

5 Answers

+15 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.
answered by Veteran (61k points)
selected 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.

+7 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 (55.3k points)
edited by
+3

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

+2
"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??
+1
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?
+5 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 Boss (13.8k points)
edited by
0
@Ayush Bi implication means if LHS nad RHS have same truth values then it is true. Now when R is false and if I take P as true and Q as false then LHS is true and RHS is false making bi conditional as false.
0
for which option are you talking tushar?
0
option c
0
@tusharp-No.When you make R as false, the R.H.S of implication is like this

$(T \lor F) \land (F \lor T) \equiv T$

The reason is $\lnot R$ is taking care for the other case.
0
sorry.. misread it :(
+1
It's okay.Make all such mistakes before gate exam.But not on the exam day :)
+1

@ayush one doubt in option c

(P ⋁ Q) ↔ (P V R) ∧ (Q V ~R)
 

 if we say biconditional p<-->q,than it means p->q and q->p

but p->q is not valid so how are we saying it as correct...as in option B we have said p-->q is not valid.?clarify please.?? 

 

 

 

+2
@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.
0
ok ayush yeah i was thinking same its due to satisfiable thing thank you
+4 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.8k 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

please sir correct me if i am wrong any were

answered by Junior (619 points)
0
Ur handwriting .... very hard to understand ...
0
Sorry @Puja mishra
+3
It is understandable!
0
can I please know why option B is not valid ?
Answer:

Related questions



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

40,748 questions
47,471 answers
145,586 comments
62,234 users