GATE IT 2006 | Question: 21

Question

Consider the following first order logic formula in which $R$ is a binary relation symbol.

$∀x∀y (R(x, y) \implies R(y, x))$

The formula is

• A. satisfiable and valid
• B. satisfiable and so is its negation
• C. unsatisfiable but its negation is valid
• D. satisfiable but its negation is unsatisfiable

Comments

@rawan here is also a good link to understand the meaning before looking into the answer 

https://math.stackexchange.com/questions/258602/what-is-validity-and-satisfiability-in-a-propositional-statement

 

---

Detailed Video Solution with COMPLETE Analysis is here: Video Solution with Complete Analysis

---

@donnie According to asymmetric relation, for every pair (x,y) in R, if x is related to y, then y cannot be related to x. But here according to its negation ∃x∃y(R(x,y)Λ~ R(y,x)) it says, there exists only some pair (x,y) for which it is the case, it is not mentioned for all. So this will be anti-symmetric, not asymmteric.

Answer 1

short trick

valid means always true ...as we know that every relation is not symmetry so it is not valid.

satisfiable means given relation is sometimes true ...as we know that given relation is symmetry and The negation of given predicate formulae is ∃x∃y[R(x,y) and ~R(y,x)]

so it is satisfiable and so its a negation.

 

hope my answer helps u a lot

Answer 2

Simplest Approach! 

Comments

@sidelewis
How do you know it is satisfoable by taking example of X lives Y.I don't get it.

Answer 3

You can easily understand by this example:

let R(x,y) be x is greater than y.

then R(y,x) will be y is greater than x.

 

now for all x for all y (R(x,y) -> R(y,x))

can be proved to be false if we can come up with the case as "T->F". This can be easily done by taking value of x as 6 and value of y as 2.

so 6>2 is true and 2>6 is false. Therefore the value is false.

Since we have proved for some variables that the implied predicate is giving us false, therefore the given statement is definitely not valid.

But it is also not satisfiable till now. To make it satisfiable we must find at least one case for which we can get result as true.

This is also simple as take x = 2 and y = 6, so 2>6 is false and F implied anything is true. Therefore with x = 2 and y = 6 we made our predicate as True.

Since we got a true case therefore the predicate is "Satisfiable"

 

Now let's check for the negation.

the negation of predicate will be,

there exist x there exist y (R(x,y) ^ not of R(y,x))

not of R(y,x) means y is not greater than x.

 

let's take again x = 2 and y = 6, now this will make predicate false as F^anything is false.

therefore clearly negation of the given predicate is definitely not valid.

 

can we make it true for atleast a case?

let's check:

take x = 6 and y = 2

now 6>2 and also 2 is not greater than 6 

therefore the given predicate is true.

this means we have atleast a case for which negation is true. Therefore the negation is satisfiable.

 

so the answer is option b. "satisfiable and so is it's negation".