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

The given relation is nothing but symmetry. We have both symmetric relations possible as well as anti-symmetric but neither always holds for all sets. So they both are not valid but are satisfiable. (B) option.

Comments

@Deepak Poonia sir plz correct me ,if I go somewhere wrong.

What is model?

→ Model means an Interpretation which makes your formula True.

    Interpretation means (Domain + Predicate). 

What is satisfiable?

→ If there exist atleast one model means if there exist atleast one domain for which my statement is true.

What is valid?

→ If we consider every domain(finite domain and infinite domain) and for every domain my statement is true.Then we can say that this is valid

Now, R(x,y) : x divides y.

So,R(y,x): y divides x. 

Let consider my domain , D = {2}

∀x∀y(R(x, y) ⟹ R(y, x)) 

→ R(2,2) will be true as 2 divides 2. So,there exist a model.So, this is satisfiable.

1. Let consider my domain , D = {2}

            R(2,2) is true and ~R(2,2) will be false.

            Now the negation of ( ∀x∀y(R(x, y) ⟹ R(y, x)) )  will be  ∃x∃y(R(x,y)Λ~ R(y,x)) 

            And so obvious that the expression will be false for this domain D. So the negation is surely not valid.

2.  Let consider my domain , D = {2,4}. R(2,4) is true and R(4,2) will be false. So ~R(4,2) will be true. ∃x∃y(R(x,y)Λ~ R(y,x)) this expression will be model.

So the negation will never be unsatisfiable for this expression.

We can conclude answer is option B.

---

@samarpita,

Your understanding is all correct Except the definition of Model that you wrote. 

A model of a formula is an interpretation in which it is true.

A model of a quantificational formula(First Order Logic Formula) is analogous to a satisfying truth assignment
of a propositional formula, so a satisfiable formula of quantificational logic is one that has a model.

A valid formula, also known as a theorem, is a formula that is true under every interpretation.

Valid formulas are the quantificational analogs of tautologies in propositional logic.

Model means an Interpretation which makes your formula True.

Interpretation means Domain + Predicate.

You are only considering Domain in the definition of Model, not the predicate. BUT you are applying it all correctly.

$\color{red}{\text{Detailed Video Solution} }$ with COMPLETE Analysis is here: Video Solution with Complete Analysis

---

Watch @GO Classes Discrete mathematics 2023 course, First order logic, Lectures 17, 18, 19, which cover Model concept in First order logic, as well as in propositional logic. Watch these 3 lectures. It will help you understand many concepts very clearly.

https://www.goclasses.in/s/store/courses/description/2023-Discrete-Mathematics

---

For people who didn’t get the anti symmetric part:

~ [∀x y(R(x, y) ⟹ R(y, x))]    =   ∃x∃y(R(x,y)Λ~ R(y,x))

In ∃x∃y(R(x,y) Λ~ R(y,x)) we are only excluding R(y,x) not R(x,x) therefore this relation is anti symmetric not asymmetric

Answer 2

x: boy,   y: girl
R(x,y) means x loves y.

Ok. Question says
For all boys & girls in the world, a boy loves a girl means that girl loves him too.. 
It is true sometimes too.
Hence satisfiable.
Negation of it is also satisfiable.
think logically or negate it mathematically then put this example.. In some cases these will be true.
Hence B is the answer.

Comments

Ok. sorry.  @Puja Mishra

---

For Q1 the answer will be B)

For Q2 the answer will be D)

---

@Ahwan

but here , 

∀x∀y(R(x,y)⟹R(y,x)) for all x,y we need to check.and atleast one is flase then answer is false.as for all.

then it should be not satisfiable. 

I know I am wrong but but i don't know where i am wrong.

Answer 3

By using Truth table and predicate formulas, this could also be another version of the answer.

Answer 4

Whenever a Predicate is satisfiable then it's negation is also satisfiable. So option B is correct.

Comments

Any valid statement is satisfiable but negation of valid is not satisfiable.